基于接近中心性指标的牵制控制理论研究

基于接近中心性指标的牵制控制理论研究

张冰冰,尚丽辉,刘典勇

(上海理工大学 光电信息与计算机工程学院,上海200093)

摘要复杂网络中性能指标多种多样,如何获得其良好的控制效果,对网络控制节点的选择是一个关键性因素。提出了基于接近数中心性指标来选取牵制控制节点,研究了采用该方法对网络的牵制控制效果。其研究结果表明,该方法能有效对复杂网络进行牵制控制,同时为牵制控制提供了参考。

关键词复杂网络;接近中心性;牵制控制

收稿日期:2015-01-26

基金项目:国家自然科学基金资助项目(81101116);国家科技支撑基金资助项目(2012BAI23B04)

作者简介:张冰冰(1991—),男,硕士研究生。研究方向:过程控制。E-mail:545286799@qq.com。尚丽辉(1977—),女,博士,讲师。研究方向:复杂网络和过程控制。

doi:10.16180/j.cnki.issn1007-7820.2015.09.010

中图分类号TN914;TB383

Research on Pinning Control Theory Based on Closeness Centrality

ZHANG Bingbing,SHANG Lihui,LIU Dianyong

(School of Optical-Electrical and Computer Engineering,University of Shanghai for

Science and Technology,Shanghai 200093,China)

AbstractComplex networks have various performance indices,and the choice of the control nodes in the networks has a great influence on control effect.A method for selecting nodes basing on closeness centrality is put forward in this article.The effect of this method on the control near the center of the network is discussed.Results show that the method can efficiently improve the control of the networks.

Keywordscomplex network;closeness centrality;pinning control

目前对于复杂网络的牵制控制还没有统一选取节点的方法,科学家们在不同的网络模型下依据网络节点度的大小和介数等信息选取节点。但这并不是最佳选取牵制控制节点方式,本文提出网络节点的接近数中心性来依次选取牵制控制的节点,并运用不同的牵制控制策略来研究接近数中心性对网络中节点的影响力。

1牵制控制策略分析

1.1　接近中心性性能指标简介

一个网络是由N个节点构成,且其中的任意节点i到其他节点的平均距离为di,即有

(1)

其中,dij为节点i到节点j的距离。di的值越小意味着节点i更接近其他节点,则节点i对于信息流动具有最佳的观察视野,因此di值的大小也反应了节点i在网络中的重要程度。为了更好地与其它指标比较,将di值进行中心化处理,即将di的倒数定义为节点i的接近中心性(Closeness Centrality),简称为接近数,记为CCi,即有

(2)

一般而言,网络中度值最大的节点、介数最大的节点和接近数最大的节点并不相同。著名社会学家Krackhardt曾设计了i,j=1,2,…,N一个包含10个节点的社会网络,被称为风筝网络(Kite Network)[1],如图1所示。在这个网络中,Diane有更多的邻居,是度值最大的节点,其度中心性为0.667;尽管Heather的度值较小,但其却又是最大的介数,在网络中起到重要作用,其介数中心性为0.389;尽管Fernando and Garth的度值没有Diane大,但是它们到其它节点的平均路径却最短,和其它节点也有着紧密联系,接近数中心性为0.643。

图1　风筝网络

1.2　接近中心性指标的牵制控制分析

考虑一个拥有总数为N个节点网络G,并且每个节点均是n的动态系统,该系统的状态方程可描述为

(3)

其中,xi是网络中节点i的状态向量;f(xi)为节点i的状态函数;常数c为节点之间的耦合强度;对角阵Γ=(τij)∈Rn×n是0-1矩阵,表示一对网络节点具体的内部连线关系。矩阵A=(aij)∈RN×N为该耦合矩阵,若节点i和节点j(i≠j)之间有边相连,则aij=aji=1;否则aij=aji=0,且有

(4)

耦合矩阵A的对角线元素为

aii=-ki,i=1,2,…,N

(5)

其中,ki为节点i的度。定义拉普拉斯算子(Laplacian)L=(lij)=-A。不失一般性的牵制控制该网络达到如下的期望平衡点

(6)

假设该系统牵制控制节点的比例为f(0

(7)

其中,ε>0为反馈增益。当ε值足够大时,那些被牵制控制的节点显然能达到期望的平衡状态,但这只占网络中节点数量的一小部分。为使其他未被牵制控制的节点也能达到期望的稳定状态,则必须使反馈增益ε达到一定的值。因此,能使网络中全部节点达到期望状态的反馈增益ε的大小可用于衡量和评价该牵制控制策略的有效性。那么使网络全局稳定的条件与未被牵制控制的节点的拉普拉斯算子矩阵的最小特征值有关[3],即

stab(G,D)=minλ(L(VD))

(8)

其中,VD表示未被牵制控制的节点。假若存在一个常数β,使得牵制控制整个网络所需要的耦合强度的临界值c>β/stab(G,D),显然,当stab(G,D)的值c越大,耦合强度的临界值越小。这说明未被牵制控制节点的拉普拉斯算子矩阵的最小特征值越大,则该牵制控制策略越有效。在网络G中,且仅当牵制控制节点集合能直接或间接到达其他所有的节点时,stab(G,D)>0;即对于任意的未被牵制控制的节点u∈VD,均存在一条连接节点u和v(v∈D)的路径。假设d(i,j)表示节点j到节点i的距离,d(V1,V2)为节点集合V2到V1的Hausdorff距离,则有

d(V1,V2)=supj∈V2infi∈V1d(i,j)

(9)

因此,无向网络G的牵制控制的稳定性可以用以下的表示

(10)

(11)

其中,V1⊂VD,k是被牵制控制节点D中节点度最大值,距离d是被控节点到未被控制节点的距离,即d=d(VD,D),E(V1,V2)是节点V2到节点V1的所有连边。由式(10)～式(11)可知,使网络G到达全局稳定的下界不仅和被牵制控制节点中的最大度有关,还与被控节点集合及未被控节点集合的距离紧密相关。因此,根据节点的度并不是唯一的选择,还有牵制控制与未被牵制控制节点集合之间的距离也是要考虑的方面。

从网络中度的定义可知,度表征了网络中的局部信息,它并不能表征除去与其直接相连的节点的信息。然而接近中心性指标却是表征了网络中全部节点的信息和全局信息[4-6]。文中就是根据度来获取节点牵制控制和接近中心性选取节点进行牵制控制,并对两种牵制控制策略进行了对比。通常在一些BA无标度网络模型中,网络节点的接近中心性和节点的度是呈紧密的线性关系,在这样的网络中无法有效地区分出牵制控制度大的节点和牵制控制接近中心性大节点网络的稳定性。然而有些网络,其节点的接近书中心性和度值之间存在弱的线性关系。

本文中选取了科学家相互协作网络,在这个网络中有一些节点尽管有小的度,但却有大的接近中心性,同时这些点也有大的聚类系数并在网络中起关键作用。在所选取的无向网络中,文中选取的节点数量占总节点的比例f,则选取的节点总数为fN进行牵制控制研究,并对在依据接近书中心性和度值的牵制控制策略中进行了对比。

2科学家相互协作网络的仿真分析

在学习工作中,经常读到多个学者合著的文章,现在将学者看作网络中的节点,其合著的文章或者科研项目看作网络中的边,若两个学者之间合作过至少一个项目,则这两个学者就有边直接连接。这样就形成了一个网络就是本节选取的科学家相互协作网络,其网络的总结点数为1 461,经过研究发现,其并不是连通的,有的科学家没有和任何其他人合作过项目,则网络中代表该科学家的节点没有边和其他节点连接,变成了网络中的孤立节点。有的科学家虽与其他科学家合作过项目,但其并未和其余更多的科学家合作过项目,这样他们就成了网络中的一个小的连通片。

本文中研究是的科学家相互协作网络的最大连通字片,其数量为379,最大连通字片的平均度为4.823 2,如图2和图3所示。从图中可以看出科学家相互协作网络中,节点度和接近数中心性之间并不具有线性关系,这样方便更好地研究接近数中心性和度值两种网络指标在复杂网络中的影响力。

图2　科学家相互网络的节点接近数中心性和度值的关系

图3　对数坐标下科学家相互网络的节点 接近数中心性和度值的关系示意图

首先选取网络中节点的接近数中心性大的节点和随机选取节点,通过仿真对比发现在一定数量之下,牵制控制网络中的接近数中心性大的节点比牵制控制随机节点有更好的牵制控制效果,但当牵制控制节点的数量超过一定值之后,牵制控制控制网络中接近数中心性大的节点反而比牵制控制随机节点更差,如图4和图5所示。接近数中心性大的节点在网络中所起的作用比随机选取节点的作用大,但现实中的网络通常具有小世界、不均匀的特性,接近数大的节点更倾向于和接近数大的节点相连。这就造成了在依据网络节点的接近数中心性选取节点时,通常选得不够均匀,可能集中在某一片区域,而网络整体稳定的速度取决于网络中最后一个节点达到稳定状态的时间。

图4　两种牵制控制策略下stab(G,V)值与节点控制个数n的关系

图5　两种牵制控制策略下stab(G,V)的值与 节点控制比例f的关系示意图

为更进一步比较网络中节点的接近数中心性和度两种牵制控制策略下科学家相互协作网络的stab(G,V)值的变化情况,如图6和图7所示。在选取的节点数量较小时,牵制控制网络中接近数中心性大的节点比牵制控制度大的节点效果更好。然而随着节点数量的增加依据网络节点接近数中性选取节点的方式有更好的控制效果。但当选取的节点数量到达一定值时,牵制控制度大的节点拥有更好的牵制控制效果。这说明对单项指标而言,接近数中心性大的节点优于度的节点,但当牵制控制选取的节点数量达到一定值时,影响网络状态行为的还有网络的拓扑结构。

图6　两种牵制控制策略下stab(G,V)的值与节点控制个数n的关系

图7　两种牵制控制策略下stab(G,D)的值 随牵制控制节点比例f的变化图

3结束语

本文首先对复杂网络的接近数中心性进行了介绍,依据网络接近数中心性指标进行稳定性分析。在此基础上,选取了现实生活中的科学家相互协作网络进行仿真研究,接近数中心性指标在网络中的作用效果。发现就牵制控制网络中的单个节点而言,接近数中心性比度值大的节点有更好的牵制控制效果。但随着牵制控制节点的不断增加,牵制控制随机得到的节点和牵制控制度大的节点,反而比牵制控制接近数中心性更大的节点,有更好的牵制控制效果。这说明影响牵制控制效果的不光有网络的单个指标,还有网络

的拓扑结构。牵制控制在选取极少量的节点时,能达到最佳的控制效果,同时更应该考虑接近数中心性更大的节点,其对于信息的流动具有更理想的观察视野。

参考文献

[1]KrackhardtD.Assessingthepoliticallandscape:structure,cognition,andpowerinorganizations[J].AdminScienceQuart,1990(35):342-369.

[2]JiaZ,LiX.Theefficiencyanalysisofseveralcategoriesofpinningstrategiesofacomplexnetwork[C].Beijing:ChineseControlConference,2010:4656-4660.

[3]LiWL,LiX,RongZH,etal.Globalstabilizationofcomplexnetworkswithdigraphtopologiesviaalocalpinningalgorithm[J].Automatica,2012,46(1):116-121.

[4]NishikawaT,MotterAE,LaiYC,etal.Heterogeneityinoscillatornetworkseasiertosynchronizability[C].PhysicsReviewLetter,2003,91(2):014101-014107.

[5]HongH,KimJ,ChoiMY,etal.Factorsthatpredictbettersynchronizabilityoncomplexnetworks[J].PhysicsReviewE,2004,69(2):067105-067110.

[6]JaliliM,AjdariRA,HaslerM,etal.Enhancingsynchronizibilityofweighteddynamicalnetworksusingbetreennesscentrality[J].PhysicsReviewE,2008,78(4):016105-016112.