复杂网络可控性-鲁富荣

汇报人：鲁富荣2016.11.27复杂网络可控性content复杂网络的可控性ContentOutline复杂网络的目标可控复杂网络的结构可控未来智能网络可控性研究随着智能网络研究的深入，人们越来越关注如何对网络施加控制从而使其运行至我们所期望的目标态，即整个网络中每个节点的状态能够被我们完全控制。因而智能网络可控性问题成为最近复杂网络研究的热点。未来智能网络可控性研究要实现对智能网络的全面控制，首先我们需要判定该网络系统是否可控或者如何通过外界输入使其实现完全可控以及我们所需要控制的最少节点数目。这一问题研究的意义非常明显，因为我们对智能网络研究的终极目标是如何控制它们。虽然传统的控制理论关于线性系统控制问题的研究已经非常成熟，

但是由于复杂网络的规模庞大，传统控制的理论方法并不能直接适用于对复杂网络系统中控制问题的研究。为邻接矩阵二阶阻容电路：R1R2II1I2C1C2E(t)x(t)令x1(t)和x2(t)分别表示电容C1,C2上的电势降，则有电容C=Q/U=E(t)表示电源电势

ControllabilityControllable:thesystemcanbedrivenfromanyinitialstatetoanydesiredfinalstateinfinitetime.

ControllabilityKalman’s

rank

condition考察一个单输入的离散时间动力系统（N=3):X(t+1)=AX(t)+bu(t)

ControllableExample设X(t=0)=0,则状态序列可得如下的结果：x(0)x(1)x(2)x(3)可控性矩阵C=[b,Ab,A2b]满秩，适当选择输入信号，节点可取到状态空间的所有值。考察一个单输入的离散时间动力系统（N=3):X(t+1)=AX(t)+bu(t)

ControllableExample设X(t=0)=0,则状态序列可得如下的结果：x(0)x(1)x(2)x(3)可控性矩阵C=[b,Ab,A2b]不满秩，无论怎么调整输入信号，节点都不可能取到状态空间的所有值。考察一个单输入的离散时间动力系统（N=3):X(t+1)=AX(t)+bu(t)设X(t=0)=0,则状态序列可得如下的结果：SolutionStructuralControllabilityMaxmiumMatching原始包含N个节点的网络记为G(A),在此基础上构造一个包含N+M个节点的被控网络，记为G(A,B)。称为状态节点；

一个状态节点称之为被控节点，如果至少存在一条从某个节点指向该状态节点的边。同时我们把不具有共同输入节点的被控节点称为驱动节点。VA={v1,v2,…,vN}为原来网络中的N个节点，M个输入，称为输入节点。VB={vN+1,vN+2,…,vN+M}对应状态节点输入节点驱动节点我们将矩阵A和B中的非零元素设为独立的自由参数，如果这些非零元素有一组取值使得网络满足Kalman可控性，则网络被称为是结构可控的。如果对非零元素的任意一组取值，网络都是可控的，则称系统是强结构可控的。一个系统是可控的当且仅当一、Structuralcontrollabilityrank(C)=3,可控rank(C)=2,不可控rank(C)=3,可控

rank(C)=？可控？如果Rank(C)=2<3,则可推出网络不可控，然而这种情况测度为零的，因此大多数情况还是可控的扩张：有向图G(A,B)包含一个扩张当且仅当存在一个子集

使得所有指向集合S的节点的数目小于集合S中的节点的数目，也即集合S的邻居集合T(S)是指直接有边指向S的所有节点的集合。定理1（结构可控性定理）

（1）线性控制系统G（A，B）是结构可控的。

（2）有向图G（A，B）既不包含不可达节点也不包含扩张。

（3）有向图G（A，B）是由掌生成的。1、定理内容

除个别情况外，一个结构可控的网络总是可控的。结构可控性定理有效地解决了现实世界中无法准确度量边的权重的问题，极大的推动了可控性的应用研究。然而，通过Kalman矩阵来得到控制矩阵所需要的最少输入信号个数的时间复杂度是

Liu[1]等通过引入图的匹配理论和方法并结合结构可控性理论[3]提出了一个基于最大匹配方法求解最小驱动节点集的复杂网络可控性分析框架，并给出了最小输入定理，从理论上证明了满足网络结构可控性需要独立控制的节点集合为网络中的非最大匹配节点的集合,时间复杂度是O(N1/2M)。匹配无向网络匹配最大匹配有向网络的匹配匹配：没有共同的head节点也没有共同的tail节点匹配：没有共同的head节点也没有共同的tail节点有向网络最大匹配匹配节点非匹配节点Nl=ND=1,并可以可选取任一状态节点为Nl=ND=N-|M*|，即为定理2

（最小输入定理）G（A）所需要的最小输入数目(Nl)或者说驱动节点数目（ND）为Nl=ND=max{N-|M*|,1}其中|M*|为网络G(A)的最大匹配所对应的匹配节点数。具体地说，如果网络G(A)存在完美匹配，那么驱动节点。如果网络G(A)不存在完美匹配，那么网络的任一最大匹配所对应的未匹配的节点数，此时驱动节点就是未匹配节点。（匹配节点：若一个节点是匹配中某条边的终点。）注：（1）要完全控制一个网络，每一个都应该有指向它的“上级节点”。因此，输入节点数应该不少于网络中不存在“上级节点”的节点数，说明定理的结论是最优性。（2）定理给出了系统可控条件下的最少驱动结点的个数及识别驱动结点的具体方法。求解二分图最大匹配的算法：算法原理

复杂度匈牙利算法搜索单个非匹配节点的可扩路并替换O(MN)或O(N3)Hop-croft算法同时搜索多个非匹配节点的可扩路并替换O(MN1/2)或O(N5/2)算法

（1）构造一个二部图β，二部图的右侧集合R包含所有的节点，左侧集合L包含所有节点。如果uϵL,vϵR在有图中有链接u→v，则在二部图中u，v之间有链接。（2）寻找二部图β的最大匹配，则右侧R中的非匹配节点恰为驱动结点。（3）若最大匹配为完全匹配，则任选一个节点作为驱动节点。少驱动节点的比例nD=ND/N。结果表明：对于基因调控网络，nD~0.8.另一方面反而一些通常认为难以控制的社会网络具有最小的nD。考虑12个不同领域的37个网络，计算完全控制每个网络所需要的最为进一步刻画网络可控性的拓扑性质，在保持网络节点数和边数不变的前提下，构造如下的随机化网络：（1）零阶零模型：每次随机选择一条边，将它的两个端点变为网络中随机选取的两个节点。模型记为rand-ER（2）一阶零模型：每次随机选择两条边，保持始点不变，交换着两条边的终点。从而保证每个节点的出度和入度不变。记为rand-Degree.图3图2上表给出了每一个实际网络对应的两种随机化网络的nD值，可以看到nDrand-ER与nD相差较大，而nDrand-Degree与nD在很多例子中较为接近。进进一步，图2表明NDrand-ER与ND没有显著的相关性，图3表明NDrand-Degree与ND存在显著的正相关。因此可以推论，对于不少的实际网络，系统的可控性主要是由网络的度分布P(kin,kout)决定的。基于统计物理的空穴场方法可以对一些网络模型给出通过度分布近似计算nD的解析公式。例如对于有向ER随即图，在平均度<k>很大而节点数目N趋向无穷时，有nD=e-<k>/2对于幂指数为γin=γout=γ的幂律度分布网络，在平均度<k>很大而节点数目N趋向于无穷时，有nD=exp[-1/2(1-(γ-1)-1)<k>]为了验证上述公式的有效性，图4显示了ER随即图和具有不同幂指数的幂律度分布网络对应的最少控制节点比例nD和平均度<k>之间的关系。实线是使用N趋向于无穷时的期望度分布而通过空穴场方法计算的解析结果，圆圈表示由最大匹配方法得到的精确结果，加号表示是基于所构造网络的精确度序列的空穴场方法计算得到的解析结果。图4图5图5表明在固定<k>的情况下，nD与幂律度分布网络的幂指数之间的关系表明越是均匀的网络所需的驱动节点比例就越小，反之，需要越多的控制节点。Summary1.Theminimumsetofdrivernodescanbeefficientlyidentified,with2.NDismainlydeterminedbythedegreedistribution二、基于网络的目标可控性

对于庞大而且复杂的社会网络、生物及技术网络,控制整个网络的状态既不可行也不必要.而根据特定的任务控制部分节点才是现实可行的。蛋白质互作用网络分别表示状态，输入和输出矩阵A描述了系统的耦合情况;B表示了被外部节点所直接控制的节点

u表示时变的输入.C表示由目标节点组成的输出矩阵。对于目标节点{C1,C2,...,Cs},C=[I(C1),I(C2),...,I(Cs)].系统简记为（A,B,C）表示状态，输入和输出向量考察线性时不变系统目标可控：对于目标节点集C，如果存在时变输入向量u(t)=(u1(t),u2(t),...,uM(t)T

使得C的状态在有限时间内到达任意期望的状态。目标可控可以看做是一种特殊的输出可控。系统（A,B,C）是目标可控的充要条件是输出空间的维数d(A,B,C)满足S是目标节点的数目.K-游走先考察网络的简单情形：有向外向树状络K-游走算法（1）计算有向树中节点i到其他所有节点j的距离dij。

该算法旨在寻找有向树中某个节点i的所有可控子集。（2）根据到节点i的距离对其他节点进行分类，到i距离相同的节点分为一类（3）假设有P个不同的距离类D1,D2,...Dp,从每一类中选取一个节点，则得到一个可控子集，所有可控子集的个数为D1×D2×…×Dp。虽然k-游走算法有一定优势，但仅适用于单输入的情形，对需要多个控制输入的网络，对于目标可控问题，提出了基于图论的GA算法，该算法给出了充分控制目标节点所需的最少输入的一种较好的近似。算法1：（1）根据最小输入定理，我们至少可以找到一个驱动整个网络的最小输入集，每个驱动结点与一个掌集的根节点相连。（2）计算需要控制所有目标节点的最小掌集的个数。

算法2：（1）构造一个二部图β，二部图的右侧集合R包含所有的目标节点，左侧集合L包含所有能到达目标节点的节点。如果uϵL,vϵR在有图中有链u→v，则在二部图中u，v之间有链接。（2）寻找二部图β的最大匹配，则R中的非匹配节点恰为驱动结点。(1)第1步，利用算法2找出控制目标节点的下界，也即二部图右侧的非匹配节点，记为D0.然后找出所有匹配边的左侧节点作为新的目标节点C1.(2)若C1=Φ，则停止，我们得到的驱动结点集D0,驱动结点的数目PD=|D0|,如果C1≠Φ，则转入（3）.(3)在t≥1步，利用算法2找出新的目标节点集Ct的驱动节点的下界,右侧的非匹配节点集即驱动节点集Dt

然后找到匹配边的左侧节点作为新的目标节点Ct+1,转入(4).

(4)若Ct+1=Φ。则停止，我们可得到驱动节点集为驱动节点数为.若，转入(3).GA算法实验及分析为进一步量化对指定比例的节点的目标控制的效率，定义了如下的参数PD表示控制目标节点所需要的最少驱动节点数（目标控制）ND表示控制全部节点所需的最少驱动结点数（最小输入定理）f表示目标节点占全部节点的比例。则认为方法有效。反之，认为无效。目标节点的选择：（1）随机机制：随机选择特定比例的节点；（2）局部机制：在连通子网络中选择的节点。Figure4bER网络的随机控制的结果.GA曲线在

中心线的上方(αD>f),说明目标控制比一般情形下控制效率低，Figure4cSF网络的随机控制的结果，GA曲线

在中心线附近

(αD≈f),说明目标控制和一般情形下控制效果相当.对ER网络施加局部的目标控制,

当f<0.5时，效率较低(Fig.4e标号为负)and当f>0.5时，效率较高(Fig.4e标号为正).Figure4f显示了SF网络的局部控制的结果,目标控制的效率较高(αD<f).思考：（1）什么类型的网络更适用于目标控制？

（2）随机和局部那种机制更利于进行目标控制？我们定义了如下指标：表示目标控制的效率，表示随机目标控制的效率，表示局部目标控制的效率，Fig.5显示了两种网络(ERandSF)的总的目标控制效率

.(a)在随机机制下，以SF网络度指数为自变量，得到的不同的平均度<k>的总的控制效率曲线(b)在随机机制下，以SF网络和ER网络平均度<k>为自变量，得到的不同的度指数

的总的控制效率曲线。(c)、(d)类似于(a)、(b)的局部控制的情形.

γγ

平均度<k>或者度指数

γ大的网络,并没有很高的控制效率.

然而,当控制整个网络时，2≤γ≤3的SF网络比ER网络难控制,但有很高的随机目标控制效率(Fig.5c).与ER网络相比,当平均度较小时，SF网络有比较低的局部目标控制效率

，但是当平均度大时却具有较高的局部目标控制效率(Fig.5d).Figure5d也说明了

一个关键值<k>c得存在性，

当<k>><k>c时，SF网络

比ER网络在目标控制上更有效.

综上所述,稀疏而且均匀的网络有较高的目标控制效率,