节点分类及失效对网络能控性的影响

孔 芝 袁 航 王立夫 郭 戈

近年来,随着科学技术的发展,人们已经认识到各种复杂系统是由相互作用和相互依赖的若干部分组成的具有特定功能的有机整体.而网络是由节点和连接节点的边所组成的.如果用节点表示系统的各个组成部分,两节点之间的边表示各个组成部分之间的相互作用,那么网络就为研究复杂系统提供了一种新的描述方式[1-5].例如神经系统可以看作是由神经细胞通过神经纤维相互连接形成的网络[2];计算机网络可以看作是自主工作的计算机通过通信介质(如光缆、同轴电缆等)相互连接形成的网络[3];人际关系网是将每一个人作为一个节点,如果两个人之间存在某种关系(比如相识)就连一条边[4];类似的还有电力网络和交通网络等.

复杂网络研究的近年来受到了许多关注,其最终目标是寻找有效的策略来控制网络的行为使其为人类服务[6-7].许多学者对复杂网络的控制算法进行了研究,并取得了丰硕的成果,如牵制控制[8-11],自适应控制[12-13],同步控制及存在延时的网络系统同步[14-19],最优滤波[20]等方法都已应用于网络中.然而对网络进行控制算法应用的前提条件是此网络系统必须是能控的.另外,现实世界中很多复杂的系统问题也可以抽象为网络能控性问题.例如,在错综复杂的基因调控网络中,如何选择最有效的基因节点作为药物的靶标,使得整个生物体网络系统朝着预期的良好状态发展;在电力网络中,如何优化网络的拓扑结构使得可以用最少的变电站就能够控制整个地区的电力供应;在计算机网络中,当部分计算机遭遇黑客袭击后,如何重新选择控制节点保证整个计算机系统的正常运转.对于线性系统能控性的基础理论已较为成熟,并广泛应用于工程中.然而,要把传统的线性系统结构能控性理论直接应用到复杂系统或者复杂网络中却存在诸多困难.如何选择一部分节点控制整个复杂网络,首要问题是需要多少外界输入信号才能使网络达到期望状态,也就是满足能控性条件的控制器的最少个数是多少.2011 年,Liu 等[21]在Nature上发表了关于复杂网络结构能控性的论文通过引入图论中的匹配理论得到了求解最少输入信号和驱动节点的最少(最小)输入定理,建立复杂网络能控性研究框架.Yuan等[22]从PBH 能控性判据出发提出了求解网络严格能控性的理论框架,可用于求解具有确定性边权和任意结构的网络的能控性.许多学者在这两个框架下研究了时变网络的能控性[23]、深度耦合动态网络的能控性[24]、对称网络结构能控性[25]、具有对抗相互作用的多智能体网络的能控性[26]和多层网络的能控性[27]等问题,这些研究大大提高了人们对网络能控性问题的认识.

现实生活中,网络某些节点遭到攻击或发生故障失效,可能会导致整个网络失控,例如互联网络中某个计算机或服务器发生故障可能导致互联网络瘫痪;电力网络中某个电站或变压器发生故障可能会导致电力系统瘫痪等.网络中不同节点失效时,对整个网络功能的影响是不同的.Pu 等[28]研究了单一节点攻击和级联失效两种攻击模式下网络可控性的影响,结果表明基于度的攻击方式都比随机攻击对网络能控性的影响更大.Liu 等[29]提出了一种随机上游攻击策略来破坏有向网络的结构能控性,该策略移除随机选择的点的上游节点,相较于依据节点度的攻击策略,该策略不需要知道网络全局的拓扑结构信息.Lu 等[30]研究了边失效对网络能控性的影响,Pu 等[31]研究了最长简单路径失效时网络能控性的影响,以上研究说明当失效边介数越大或失效时简单路径越长,对网络能控性的影响更大.

综上所述,可以发现当前节点失效对网络能控性的影响的研究主要集中在部分节点或者边失效对网络能控性的影响上,主要针对具有某种结构特征的节点或边通过实验和仿真等手段给出结论,并未从理论层面给出节点失效对网络能控性的影响.对于整个网络而言,不同类型的节点对网络能控性的影响也不相同:有些节点失效网络能控性会增加,有些节点失效网络的能控性保持不变,有些节点失效网络能控性会降低.哪些节点失效对网络能控性有何影响,至今未有明确结论.因此,本文为了研究此问题将网络节点进行分类,并从理论层面给出不同类型的节点对网络能控性影响的确切结论.首先根据边的方向和匹配关系提出一种网络节点的分类方式,将网络中的节点分成九种类型,并给出了辨识节点类型的算法,然后研究了复杂网络中某类节点失效对网络能控性有何影响,给出了节点失效后网络能控性的变化规律,最后通过仿真实验验证上述规律的有效性.

1 复杂网络能控性

考虑一个具有N个节点的复杂网络,其动力学方程表示为

其中x(t)=[x1,x2,···,xN]T表示网络中节点的状态,xj(t) 表示第j个节点在t时刻时的状态;A=[aij]∈RN×N为网络邻接矩阵,其中aij代表节点j影响节点i的强度,aij ＞0 表示这种影响是积极,aij ＜0 表示这种影响是消极的,若aij=0 表示从节点j到节点i没有连接关系,即节点j不影响节点i;u(t)=[u1,u2,···,uM] 表示M个输入控制信号在t时刻的输入量;B∈RN×M称为输入矩阵,表示外部输入节点与内部节点的耦合关系,bij表示输入信号uj(t) 与节点i之间的耦合连接.

对于复杂网络系统(1),若存在一个分段连续的u(t),可在有限的时间内 [t0,tf] 从任意初始状态x(t0) 驱动到任意期望的终端状态x(tf),则称此系统的状态是完全能控.在控制理论中,判断系统是否完全能控可通过卡尔曼判据,对于系统(1)完全能控当且仅当能控性矩阵C=[B,AB,···,AN-1B]是满秩的,即

因此要使一个给定网络能控需要寻找一个输入矩阵B使得能控性矩阵C满秩.

当复杂网络节点间不考虑连接强度时,即不考虑矩阵A与B具体数值,仅考虑矩阵中的元素是零或为独立自由参数,这时矩阵A与B称为结构矩阵.如果存在A与B中一组非零取值,使得网络是能控的,则称系统(1) 为结构能控,也可记为(A,B)结构能控.

对于有向复杂网络G=(V,E),其中V为网络的节点集,E为网络的边集.如果网络边集E的一个子集M中没有两条边共享一个公共的起始节点或结束节点,则M称为G的一个匹配.G中边数最多的匹配称为G的最大匹配.最大匹配一般是非唯一的.如果一个节点是匹配中某条边的结束节点,则该节点为匹配节点,否则,它为非匹配节点.

Liu 等[21]通过将图的匹配理论与结构可控性相结合,提出了一种基于最大匹配算法求解最小驱动节点集的分析复杂网络能控性的理论框架,并给出最小输入定理,证明了实现网络结构可控所需独立控制的节点集合等于非最大匹配的节点集合,其中需要被外部输入施加控制的节点称为网络的驱动节点,驱动节点个数用ND表示,通过对这些驱动节点施加外部输入控制信号可使控制信息传达到网络中每一个普通节点,可实现整个网络的完全能控.

引理 1.最小输入定理[21]:网络的最小输入集等价于最小驱动节点集(ND).如果网络是完美匹配,最小输入集是网络中的任意一个节点;否则,它等于网络最大匹配后未被匹配的节点集.用公式表示:

其中,N为有向网络节点个数,|M|为网中最大匹配节点个数.

网络能控性大小可由控制网络所需要的最小驱动节点数占总节点数的比例来衡量,即网络中的驱动节点密度,记为

其大小反映该网络能被控制的难易程度,控制网络所需的驱动节点数占总节点数的比例越小,即nD越小,表明网络越容易实现完全能控,反之,控制网络所需的驱动节点数占总节点数的比例越大,即nD越大,表明网络越难实现完全能控.

2 节点分类辨识及能控性分析

复杂网络中的节点失效会使网络驱动节点数发生变化,从而影响网络的能控性.然而,不同的节点失效,对网络的能控性的影响也不同.当哪些节点失效,驱动节点个数会增加? 哪些节点失效驱动节点数会减少? 针对这个问题,本节将网络节点进行分类,研究不同类型节点失效对网络结构可控性有何影响.

2.1 节点分类方式

在有向网络中,节点与节点之间通过有向边相连.节点与边的连接存在以下四种关系:

A:只存在输出边,不存在输入边的节点.如图2中节点A所示,将这类节点构成的集合记为VO.

图2 节点与边的四种关系Fig.2 Four relations between nodes and edges

B:只存在输入边,不存在输出边的节点.如图2中节点B所示,将这类节点构成的集合记为VI.

C:既存在输出边又存在输入边的节点.如图2中节点C所示,将这类节点构成的集合记为VIO.

D:既不存在输出边又不存在输入边的节点.如图2 中节点D所示,将这类节点构成的集合记为VD.

对于任意网络而言,最大匹配一般是非唯一.因此网络中节点参与最大匹配的可能性也不相同,可根据匹配关系对原始的网络节点进行分类.

对于属于VO的节点而言,即节点只包含输出边,则该类节点一定为最大匹配的起始节点.可以将其分为以下两种类型:

类型 1.输出完全匹配节点:如果该节点在所有组的最大匹配中一定是最大匹配边集的起始点,则这个节点称为输出完全匹配节点(Output matching node,OM),将这类节点的集合记为VOM.

类型 2.输出不完全匹配节点:如果该节点不是所有组最大匹配边集的起始点,则这个节点称为输出不完全匹配节点(Output non matching node,ONM),将这类节点的集合记为VONM.

例如图1 中,节点v1,v2,v3只含输出边不含输入边,属于VO.在四组最大匹配中,节点v3为所有组最大匹配集中匹配边的起始节点,属于类型1 为OM 节点.节点v1和v2属于某些组最大匹配,不是所有组最大匹配边集的起始点节点,所以属于类型2为ONM 节点.这两类节点集存在如下关系,

图1 有向图和二分图的匹配Fig.1 Matching of directed graph and bipartite graph

对于属于VI的节点,即节点只存在输入边,则该类节点一定为最大匹配的终止节点,可以分成以下两种类型:

类型 3.输入完全匹配节点:如果该节点在所有组的最大匹配中一定是最大匹配边集的终点,则这个节点为输入完全匹配节点(Input matching node,IM).将这类节点的集合记为VIM.

类型 4.输入不完全匹配节点:如果该节点不是所有组最大匹配边集的终点,则这个节点称为输入不完全匹配节点(Input non matching node,INM).将这类节点的集合记为VINM.

例如图1 中,节点v4,v5,v6都属于VI.四组最大匹配中,节点v4是所有组最大匹配边集的终点,所以其类型为IM 节点,属于VIM.节点v5和v6只存在于某些最大匹配中,不是所有组最大匹配边集的终止节点,所以其类型为INM,属于VINM.这两类节点集存在如下关系,

对于属于VIO的节点,即当节点既包含输出边又包含输入边时,根据节点匹配与被匹配的关系,可分为以下四种类型:

类型 5.输入完全匹配和输出完全匹配节点:如果该节点在所有组的最大匹配中一定是最大匹配边集的起点也一定是最大匹配边集的终点,则这个节点为输入完全匹配和输出完全匹配节点(Input matching and output matching node,IM&OM).将这类节点的集合记为VIM&OM.

类型 6.输入不完全匹配和输出完全匹配节点:如果该节点在所有组的最大匹配中一定是最大匹配边集的起点,但不是所有组最大匹配边集的终点,则这个节点为输入不完全匹配和输出完全匹配节点(Input non matching and output matching node,INM&OM).将这类节点的集合记为VINM&OM.

类型 7.输入完全匹配和输出不完全匹配节点:如果该节点不是所有组最大匹配边集的起点,但在所有组的最大匹配中一定是最大匹配边集的终点,则这个节点为输入完全匹配和输出不完全匹配节点(Input matching and output non matching node,IM&ONM).将这类节点的集合记为VIM&ONM.

类型 8.输入不完全匹配和输出不完全匹配节点:如果该节点不是所有组最大匹配边集的起点,也不是所有组最大匹配边集的终点,则这个节点为输入不完全匹配和输出不完全匹配节点(Input non matching and output non matching node,INM&ONM),将这类节点的集合记为VINM&ONM.

图3 节点分类Fig.3 Node classification

对于节点v6而言,和都只存在部分最大匹配情况中,所以节点v6既不是所有组最大匹配边集的起点,也不是所有组最大匹配边集的终点,因此节点v6类型为INM&ONM.

对于节点v8而言,只存在部分最大匹配中,而出现在所有最大匹配情况中,所以节点v8

不是所有组最大匹配边集的起点,但在所有组的最大匹配中一定是最大匹配边集的终点,因此节点v8类型为IM&ONM.

类型 9.孤立节点:当节点既不包含输出边也不包含输入边时,该节点称为孤立节点(记为VD,见图2).这类节点在原始中一定既不是最大匹配的起始节点也不是最大匹配的终止节点,因此如果要实现网络完全能控,这类节点一定为驱动节点.

2.2 节点辨识算法

为了分析不同类型节点对网络可控性的影响,需要识别网络中节点属于哪一类型.因此,本节给出识别出网络中节点类型的算法,算法流程如图4所示.具体步骤如下:

图4 算法流程图Fig.4 Algorithm flow chart

步骤 1.通过Hopcroft-Karp 算法[32]识别二分图网络中的最大匹配组.

步骤 2.选择节点集合中一个节点,记为vi(i=1,2,···,N).N为集合中节点个数.

步骤 3.判断节点vi是否存在输入边和输入边.

步骤 4.若只存在输入边,则跳转步骤5.若只存在输出边,则跳转步骤6.若既存在输出边,又存在输入边,则跳转步骤7.若既不存在输出边又不存在输入边,则节点类型为孤立节点,跳转步骤8.

步骤 5.节点输入边相连的节点为ui.去掉节点vi输入边,以深度优先搜索算法观察是否存在以节点ui为起点的增广路径,若存在,则节点vi为INM,若不存在,则节点vi为IM.

步骤 6.节点输出边相连的节点为wi.去掉节点vi输出边,以深度优先搜索算法观察是否存在以节点wi为终点的增广路径.若存在,则节点vi为ONM,若不存在,则节点vi为OM.

步骤 7.节点输入边相连的节点为xi.节点输出边相连的节点为yi.去掉节点vi输入边和输出边,以深度优先搜索算法观察是否存在以节点xi为起点和以节点yi为终点的增广路径.

若同时存在以节点xi为起点和以节点yi为终点的增广路径,则节点vi为INM&ONM.

若只存在以节点为起点xi的增广路径,不存在以节点yi为终点的增广路径.则节点vi为INM&OM.

若只存在以节点yi为终点的增广路径,不存在以节点xi为起点的增广路径.则节点vi为IM&ONM.

若同时不存在以节点xi为起点和以节点yi为终点的增广路径,则节点vi为IM&OM.

步骤 8.若i＜N,i=i+1,返回步骤2.反之结束操作.

算法伪代码如下:

注 1.假设网络中含有N个节点和L条边.算法时间复杂度由以下两个部分组成,第一部分是识别网络二分图的最大匹配;第二部分是通过深度优先搜索算法寻找增广路径.由文献[29]可知识别网络二分图最大匹配的时间复杂度为 O (N0.5L).通过深度优先搜索算法寻找增广路径可能存在以下四种情况:

1)当vi只含有输入边时,与vi输入边相连的节点记为ui.去掉vi输入边,以深度优先搜索算法识别是否存在以ui为起点的增广路径.使用一次深度优先搜索算法,复杂度为 O (L).

2)当vi只含有输出边时,与vi输出边相连的节点记为wi.去掉vi输出边,以深度优先搜索算法识别是否存在以wi为终点的增广路径.使用一次深度优先搜索算法,复杂度为 O (L).

3)当vi既含有输入边又含有输出边时,与vi输入边相连节点记为xi,与vi输出边相连节点记为yi.去掉vi输入边与输出边,以深度优先搜索算法识别是否存在以xi为起点或yi为终点的增广路径.使用一次深度优先搜索算法,复杂度为 O (L).

4)当vi既不含有输入边又不含有输出边时,该节点类型为孤立节点.无需深度搜索.

综上可知,节点vi为上述这四种情况中之一,网络节点总数为N,寻找增广路径的复杂度最大为O(L).因最大匹配和寻找增广路径为并列关系,故该算法的最大复杂度为 O (N0.5L)+O(NL).

2.3 节点失效对能控性的影响

现实的复杂网络在遭受攻击或意外时,网络中的节点会被破坏或故障失去原有功能,造成节点失效.不同类型的节点失效对网络能控性有何影响?本节根据第2.1 节点分类的方式,给出了网络节点失效时,对网络能控性和驱动节点的影响情况.

定理 1.对于一个含有N个节点的复杂网络,当某一个节点遭受攻击失效时,若失效节点为输入完全匹配节点(IM)时,网络中驱动节点个数保持不变.若失效节点为输入不完全匹配节点(INM)时,网络中驱动节点个数减少一个.

证明.假设网络中节点个数为N.网络二分图最大匹配中被匹配的节点个数为H个.由式(3)可知驱动节点个数ND=N-H.当网络中输入完全匹配节点失效时,节点个数为N-1.由输入完全匹配节点的定义可知,该节点在原始网络中一定被其他节点的匹配.因此该节点失效后,网络中被匹配节点个数变成H-1.驱动节点个数=(N-1)-(H-1)=N-H=ND.驱动节点个数保持不变.当网络中输入不完全节点失效时,节点个数为N-1.由输入不完全匹配节点定义可以知,该节点在最大匹配中不一定被其他节点所匹配.因此该节点失效后,网络最大匹配中被匹配节点个数保持不变为H.驱动节点个数=(N-1)-H=ND-1.驱动节点个数减少一个.□

定理 2.对于一个含有N个节点的复杂网络,当一个节点遭受攻击失效时,若失效节点为输出完全匹配节点(OM)时,网络中驱动节点个数保持不变.若失效节点为输出不完全匹配节点(ONM)时,驱动节点个数减少一个.

证明.假设网络中节点总数为N个,被匹配节点个数为H个.驱动节点个数ND=N-H.当输出完全匹配节点失效时,节点个数为N-1.由输出完全匹配节点定义可以该节点一定参与其他节点的匹配,因此当该节点失效后,一定会造成某个与之连的节点变成未匹配节点,因此失效后网络中被匹配节点个数减少一个,变成H-1.驱动节点个数=(N-1)-(H-1)=N-H=ND.驱动节点个数保持不变.当输出不完全匹配节点失效时,节点个数为N-1.由输出不完全匹配节点定义可知,该节点在最大匹配中不一定参与其他节点的匹配,因此当该节点失效时,网络最大匹配中被匹配的节点个数保持不变为H.驱动节点个数=(N-1)-H=ND-1.驱动节点个数减少一个.□

定理 3.对于一个含有N个节点的复杂网络,当一个节点遭受攻击失效时,若失效的节点类型为IM&OM,网络的驱动节点个数增加一个.当失效的节点类型为IM&ONM 或者INM&OM 时,网络的驱动节点个数保持不变.当失效的节点类型为INM&ONM 时,网络的驱动节点个数减少一个.

证明.网络中节点个数为N,假设匹配节点个数为H.将包含输出边又包含输入边的节点分解为两个节点,一个只含有输出边,另一个只含有输入边.此时网络中节点个数为N+1,这样失效某个既包含输出边又包含输入边的节点等效为失效一个只包含输出边的节点和一个只包含输入边的节点.将IM&OM 节点分解为IM 节点和OM 节点,此时网络中节点总数为N+1.失效IM&OM 节点等效为IM 节点和OM 节点失效,失效一个匹配起始节点和一个匹配终点,匹配节点数少2.引理1可知=(N+1-2)-(H-2)=N-H+1=ND+1即驱动节点个数增加一个;同理将IM&ONM 节点等效为IM 节点和ONM 节点,INM&OM 节点等效为INM节点和OM节点,失效一个匹配起点或一个匹配终点,匹配节点数少1=(N+1-2)-(H-1)=N-H=ND;INM&ONM 节点等效为INM 节点和ONM 节点,匹配节点数保持不变,=(N+1-2)-H=N-H-1=ND-1.即驱动节点个数减少一个.□

注 2.由定理1,2,3 可以看出,当失效节点为IM,OM,INM&OM,IM&ONM 节点时,网络的驱动节点数不变,但网络总节点数减少1,由式(4) 可知由nD=ND/(N-1)衡量能控性大小,所以网络能控性略有减弱;当失效节点为IM&OM 类型时,网络的驱动节点数增加1,网络总节点数减少1,由式(4)可知能控性nD=(ND+1)/(N-1),所以nD明显变大,能控性有明显减弱;当失效节点为INM或ONM 或INM&ONM 类型时,网络的驱动节点数减少1,网络总节点数减少1,由式(4)可知能控性nD=(ND-1)/(N-1),所以nD明显减小,能控性明显增强.

3 仿真实验

3.1 模型网络

首先生成三种典型的网络模型,即ER 随机网络模型[33],BA 无标度网络模型[34],WS 小世界网络模型[35],其中生成ER 网络节点个数N为500 个,节点间连接概率为p=0.02;BA 网络从初始点数是10 个,边数是8 的网络,每次引入一个新节点和4 条边,按照度大的节点优先连接的原则,生成节点数为500 的无标度网络;WS 小世界网络,从500个节点近邻边数为4 的近邻耦合网络,重连的概率为0.3,生成的小世界网络.采用2.2 节所述节点类型识别算法,得出三种网络每种节点类型数量,如表1所示.由于该分类方式针对有向网络,因此在生成网络模型时,将节点之间无向连接关系变成单向有向连接,然后进行仿真.

表1 模型网络不同类型节点占比表Table 1 Proportion of different types of nodes in the model network

从表1 中可以看出,INM&ONM 类型的节点数量在BA 网络和WS 网络中较多,而IM&OM 节点在BA 网络和WS 网络中较少.因为BA 网络中新添加的节点倾向于连接节点度高的节点,而WS 网络具有较高的聚类系数,因此这两类网络中大部分节点不一定是所有匹配边集的起点和终点,即不是固定与某个节点完成匹配.

为了验证每种类型节点失效对网络可控性的影响,对网络中的每类节点进行逐个随机选则并删除,然后计算网络中驱动节点个数占比nD.由于网络失效一个节点后,网络结构发生变化,失效节点的邻近节点类型也会变化,需要重新对网络节点进行分类,再随机选取该类节点失效,计算nD.需要注意是网络中不同类型节点个数不同,为了能够有效对比,失效节点个数保持一致,失效节点的数量以数量最少的类型节点数量为准.

按照上述方法,在ER 网络、BA 网络和WS 网络中逐个失效INM 节点、IM 节点、ONM 节点和OM 节点后网络的驱动节点个数占总节点数的比例nD与失效节点数量占总节点数的比例f的关系如图5、图6 和图7 所示.图中可以看出INM 节点和ONM 节点失效后,驱动节点个数减少,nD值降低,随着INM 节点和ONM 节点失效,网络可控性增加,网络的控制更加容易.相反IM 节点和OM 节点失效后,nD值略有增加.实际上,驱动节点个数ND不变,但由于节点失效,节点总数减少,所以nD值呈现出略有增加的现象.对于一个大规模网络,节点数N很大时,失效少量节点时,驱动节点个数ND不变时,可以近似认为能控性nD不变.

图6 BA 网络 VI 和 VO 失效可控性变化Fig.6 Controllability changes of VI and VO failure in BA networks

图7 WS 网络 VI 和 VO 失效可控性变化Fig.7 Controllability changes of VI and VO failure in WS networks

ER 随机网络模型、BA 无标度网络模型和WS小世界网络模型中INM&ONM 节点、INM&OM节点、IM&ONM 节点和IM&OM 节点失效后,网络可控性nD随失效节点个数占节点总数比例f变化情况如图8、图9 和图10 所示.图中可以看出,当INM&ONM 节点失效后,驱动节点个数减少,nD值降低,网络可控性增强.当INM&OM 节点和IM&ONM 节点失效后,驱动节点个数不变,但网络节点总数减少,nD值略有增大,网络可控性降低.当IM&OM节点失效后,驱动节点个数增多,nD值增大明显,网络可控性显著降低,网络变得更难控制.

图8 ER 网络 VIO 失效可控性变化Fig.8 Controllability changes of VIO f ailure in ER networks

图9 BA 网络 VIO 失效可控性变化Fig.9 Controllability changes of VIO failure in BA networks

图10 WS 网络 VIO 失效可控性变化Fig.10 Controllability changes of VIO failure in WS networks

3.2 真实网络

下面应用真实网络进行节点类型及每种类型的分布情况进行分析.选取了多种社交网络[36],包括某公司经理之间社交网络,某律所律师社交网络,某银行员工间社交网络和某学校学生间社交网络等共7 个网络.在社交网络中节点代表网络中的个体(某个人),网络的边代表不同个体之间社交关系(交流或沟通).根据每个网络的基本数据[36],采用本文第2.2 节点类型识别算法,得出每个网络每种节点类型数量,如表2 所示.

在实际的社交网络中INM 节点和IM 节点为存在输入边的节点,可理解为从不主动与他人交流沟通,被动的接受他人的交流邀请的人;ONM 节点和OM 节点为存在输出边的节点在实际的社交网络中可理解为能主动的与他人交流沟通,从不被动的接受他人的交流邀请的人.同理,INM&ONM、INM&OM、IM&ONM 和IM&OM 节点在实际社交网络中可理解为即能主动的与他人交流沟通又能被动的接受他人的交流邀请的人;VD节点是即不能主动的与他人交流沟通又不被动的接受他人的交流邀请的人.表2 的数据表明,在社交网络中,INM&ONM 节点占比较多,这类节点在节点最大匹配中特性为不是所有最大匹配边集的起点和终点,即不是一定参与其他节点的匹配,也不是一定被其他节点所匹配.这一现象对应人在社交网络中的交流与沟通不是固定不变的,即每个人会与多人产生交流和沟通.与实际中人际社交关系相符合.而INM 节点、IM 节点、ONM 节点和OM 节点等占比较少,这是由于这类节点在网络最大匹配中是最大匹配边集的起点或者终点,即只参与其他节点匹配或者被匹配.这种现象对应实际社交网络中交流与沟通是单向的,这类情况在社交网络中出现概率较少.

表2 实际网络不同类型节点占比表Table 2 Proportion of different types of nodes in the actual network

考虑到网络中节点类型的全面性,本文选取节点数量相对较多的学生社交网络(1)和学生社交网络(2)分析节点失效后对网络能控性的影响.为了有效对比,选取节点数量较多的INM&ONM 类型节点、INM&OM 类型节点,且每种类型失效节点数量保持相同.节点失效后网络的驱动节点个数占比nD与失效节点个数占比f的关系如图11 所示.

图11 社交网络节点失效能控性变化Fig.11 Controllability changes of node failure in social networks

图中可以看出,当INM&ONM 节点失效后,驱动节点个数减少,nD值降低,网络可控性增强.当INM&OM 节点失效后,驱动节点个数不变,但网络节点总数减少,nD值略有增大,网络可控性降低.能控性的变化规律与仿真效果与模型网络一致.

4 结论

本文针对复杂网络中节点失效问题,根据节点相连边的方向和最大匹配关系,将网络节点分成九种类型,并给出辨识节点类型的算法.分析了不同类型节点失效对网络能控性的影响,得出不同类型节点失效对网络驱动节点个数的不同影响,当INM、ONM 和INM&ONM 类型节点失效时,驱动节点数减少1,网络能控性增强;当IM、OM、INM&OM和IM&ONM 类型节点失效时,驱动节点数不变,网络可控性略有降低,此类型节点失效对网络能控性的影响较小,当网络总节点数N较大时,能控性基本不变;当IM&OM 类型节点失效时,驱动节点个数增加1,网络能控性明显降低,此类型节点对网络能控性的影响较大.