一种基于信度函数的复杂网络重要节点识别方法

2018-06-25莫泓铭

长春师范大学学报 2018年6期

莫泓铭

(四川民族学院图书馆，四川康定 626001)

在科学技术突飞猛进的今天，人们的生活中充满了各种各样的信息化的系统，如电力系统、交通网络系统、通信系统、在线社交系统等.这些应用系统或者本身就是网络化的，或者可以抽象为网络.复杂网络的“无标度”[1]和“小世界”[2]等特性的发现，掀起了一轮又一轮的复杂网络研究热潮[3].在复杂网络的众多研究领域中，节点重要度识别一直是一个热门话题.所谓重要节点，在不同的网络结构或应用领域中有不同的理解.通俗地讲，重要节点是相对的，它或它们相对于网络中的其他非重要节点而言能更大程度地影响网络的结构或功能[4].网络中的重要节点的数量通常比较少，但通过它们，可以快速地影响到网络中的绝大部分节点.比如，在无标度网络中针对重要节点的蓄意攻击可以快速导致网络的级联失效[5]，微博中的大V用户所发布的信息可以快速传遍微博[6]，等等.

寻找网络中的重要节点，一方面可以通过其进一步挖掘网络结构，另一方面可以对其加以重点利用，从而更好地优化网络结构，促进网络的良好运转[7].研究者们提出了许多关于复杂网络重要节点的识别方法，常见的有节点的度中心算法[8]、接近中心算法[9]、结构洞中心算法[10-11]等.这些算法大多是从节点单一属性出发，或局部或全局地衡量节点的重要性.相关研究表明，节点是具有多重属性的[12].如何利用节点的多属性这一特性来更好更准确地识别复杂网络中的重要节点是一个值得探讨的问题.于会等[13-14]基于TOPSIS结合节点的度中心性、介数中心性、接近中心性和结构洞等属性探讨节点的重要度，常振超等[15]基于节点多属性检测网络社团，李文兰等[16]基于节点多属性识别合著网络中的关键节点.证据理论，又称信度函数，作为一种不确定信息处理工具[17-18]，近年来被广泛地运用于各类决策应用中[19-22].为了解决复杂网络中的节点重要度识别问题，本文提出了一种基于信度函数的复杂网络节点重要性识别方法，该方法将节点的度中心、接近中心性、结构洞等属性视为不同的信度函数，运用证据理论中的组合规则将它们进行充分融合，得到节点的一个综合评估值.实例验证表明该方法具有有效性和全面性，能集成单一算法的优点同时克服其不足.

1 预备知识

1.1 常见的复杂网络节点重要性算法

节点的度中心性(Degree Centrality)是指与节点直接相连的一级邻居数量，其计算公式为：

(1)

其中，vij表示节点i与j直接相连的状态，vij=1表示节点i与j之间有一条边直接相连，vij=0表示节点i与j之间无直接边相连.节点拥有的直接邻居越多，其度越大，就越重要.节点度中心算法从网络局部信息出发来衡量节点的重要性，具有简单、快捷等特点.然而，网络中的许多节点通常具有相同数量的一级邻居，其度值相同，在这种情况下，度中心算法视它们的重要程序一样，因而无法进一步区分.

节点的接近中心性(Closeness Centrality)衡量的是从某个特定节点出发到网络中其他节点的最短路径所含边的数量的倒数，其计算公式为：

(2)

其中，dij代表节点i与节点j之间的最短路径中的边的数量.

接近中心算法是节点在网络中所处的位置这一属性出发来衡量节点的重要性.节点的接近中心值越大，说明其在网络中处于中心位置的可能越大，就越重要.节点的接近中心算法从网络全局的角度来衡量节点的重要程序，需遍历整个网络，相对度中心算法而言，其运算复杂度较高.

1.2 结构洞

结构洞理论是由美国社会学家Burt在其著作《结构洞：竞争的社会结构》中提出的[9].Burt认为网络中的位置比关系的强弱更为重要，节点在网络中的位置决定了其地位的高低，相应地拥有更多的信息、资源与权力.结构洞理论认为，如果两个节点之间无法直接联系，必须通过第三者才能取得联系，那么这两个节点之间的第三者就占据了一个结构洞.衡量结构洞的指标有网络约束系数(Constraint，CT)、网络有效规模(Effective Size，ES)、效率(Efficient，EF)、等级度(Hierarchy，HI)等，不同的指标适用于不同的应用场合.在本文中，采用网络约束系数作为衡量结构洞的指标.网络约束系数是指网络节点形成结构洞时所受到的约束，其计算公式为：

(3)

其中，Γ(i)为节点i的所有一级邻居的集合，节点q为节点i与j的共同邻居.pij为节点i为维持与节点j的邻居关系所付出的精力与总精力的比例，piq和pqj分别为节点i与j与共同邻居q维持关系所付出精力占其总精力的比例.pij的计算公式如下：

(4)

其中，zij表示节点i到j的关系，当节点i到j之间有联系时，其值为1，否则为0.piq和pqj的计算公式与pij类似.

结合公式(3)和(4)可知，节点的网络约束系数指标能够反映节点的一级邻居数量及它们之间联系的紧密程度情况.节点i的度越大，则其一级邻居数量越多，pij的值就越小，说明一级邻居数量越多的节点更容易形成结构洞.piq和pqj从节点的共同邻居的角度出发，节点i,j,q之间联系越紧密，它们之间形成的三角形拓扑结构就越多.由此可见，节点的网络约束系数值就越大，说明该节点的邻居很少且与其他邻居的闭合或重合程度很高，这类节点的影响范围有限，不易获得更多的新的关系支援，因而在竞争中处于不利的地位.反之，节点的网络约束系数越小，其越容易形成结构洞，进而有利于获得新的关系支援，在竞争中处于有利的地位，即网络约束系数小的节点在网络中的影响力较大.结构洞理论在复杂网络的节点重要度识别[23-26]、社会网络分析[27-28]和企业管理[29]等方面得到了广泛应用.

1.3 信度函数

信度函数理论又称为证据理论，是Dempster于1967年提出的[17]，其试图运用传统概率中的上下限来表达实际问题中的不确定性，随后其学生Shafer于1976年对其进行了进一步推广[18].证据理论相比较传统的主观贝叶斯理论，最大的特点在于不需要先验信息，并且可以直接表达“不确定”与“不知道”.证据理论中的信度函数允许我们基于信度和组合规则，使用一个问题的概率来推导另一个相关问题的概率.证据理论的相关概念简要介绍如下：

(5)

2 基于信度函数的融合节点重要度识别模型

基于信度函数的节点重要度识别模型如图1所示，主要由以下几部分构成：①选择节点相关属性；②测定相关选定属性值；③构建信度函数框架并将测得的属性值转换为信度函数；④运用Dempster组合规则融合节点属性信度函数；⑤分析融合结果并据此排序.

图1 基于信度函数的复杂网络节点重要度识别模型

3 实例应用

在本例中，采用USAir97数据集来验证本模型的有效性.USAir97是一个加权的有向网络，为简便描述，将其视为无权的无向网络.USAir97数据集中包含了332个节点、2126条边，节点的最大度值为139，最小为1[30].USAir97网络如图2所示.下面将运用新建立的节点重要度识别模型来识别USAir97网络中节点的重要度情况.

图2 USAir97网络

Step1 结合USAir97网络特性，选取节点的度、紧密度和结构洞等属性作为测定指标.

Step2 分别运用相关算法，测得节点的度、紧密度和结构洞等属性值，如表1中第2、4、6列所示.需要说明的是，由于结构洞属性中的网络约束系数是一个逆指标，即数值越小其影响力越大，而度与紧密度指标均是正向指标，为统一测量指标体系，需对节点的网络约束系数值进行相应处理.由于该网络节点众多，限于篇幅，表1只列出了部分节点.

表1 节点相关属性值及排序

Step3 构建信度函数理论框架.在本例中，主要测试节点的重要程度，即可简单地将节点的重要与否划分为重要与不重要，即其辨识框架为{重要，不重要}，数学化表示为Θ={H,L}.Θ为辨识框架，H代表重要，L代表不重要.建立好辨识框架后，接下来需要将相关属性值转化为信度函数的形式.

首先，选择参考值.选择相关属性值的最大值和最小值作为参考值，则：

DCmax=max{DC1,DC2,DC3,…,DCn},

DCmin=min{DC1,DC2,DC3,…,DCn},

CCmax=max{CC1,CC2,CC3,…,CCn},

CCmin=min{CC1,CC2,CC3,…,CCn},

Cmax=max{C1,C2,C3,…,Cn},

Cmin=min{C1,C2,C3,…,Cn}.

其中，DCmax为度值中的最大值，DCmin为度值中的最小值，CCmax为聚集系数值中的最大值，CCmin为聚集系数值中的最小值，Cmax为结构洞属性中网络约束系数值中的最大值，Cmin为结构洞属性中网络约束系数值中的最小值，即DCmax=139,DCmin=1,CCmax=0.6073,CCmin=0.1978,Cmax=0.9596,Cmin=0.

其次，构建信度函数转换模型.以节点i的度为例，mDCi(H)和mDCi(L)分别代表节点i在度中心算法中的重要程度与不重要程度，同理有mCCi(H)、mCCi(L)、mCi(H)和mCi(L).节点i的相关属性的信度函数可通过下列模型转换得到：

其中，ω为可调节参数，其目的在于避免当最大值与最小值一样时上述转换模型出现分母为0的情况.理论上，ω可取值为任意非零实数，为简便，在本模型中ω取值为1.节点i的各相关属性信度函数经整理，有：

MDC(i)=(mDCi(H),mDCi(L),mDCi(Θ)),

MCC(i)=(mCCi(H),mCCi(L),mCCi(Θ)),

MC(i)=(mCi(H),mCi(L),mCi(Θ)).

其中，

mDCi(Θ)=1-mDCi(H)-mDCi(L),

mCCi(Θ)=1-mCCi(H)-mCCi(L),

mCi(Θ)=1-mCi(H)-mCi(L).

以节点118为例，节点118的度、聚集系数、结构洞为：

整理可得节点1的各属性信度函数有：

MDC(118)=(mDC118(H),mDC118(L),mDC118(Θ))=(0.9928,0,0.0072).

(6)

MCC(118)=(mCC118(H),mCC118(L),mCC118(Θ))=(0.2905,0,0.7095).

(7)

MC(118)=(mC118(H),mC118(L),mC118(Θ))=(0.4897,0,0.5103).

(8)

Step4 融合相关信度函数.在得到节点各属性的信度函数后，运用Dempster组合规则，对节点属性的信度函数进行两两融合，最终得到节点的一个综合决策信度函数：

M(i)=(mi(H),mi(L),mi(Θ)).

(9)

在本例中，对节点1，运用公式(5)，依次融合公式(6)～(8)，得到节点118的综合决策信度函数：

M(118)=(m118(H),m118(L),m118(Θ))=(0.9974,0,0.0026).

(10)

Step5 公式(9)中的mi(Θ)代表系统无法进一步将该部分数值分配给H或L，在本模型中，为简便起见，将mi(Θ)平均分配给mi(H)和mi(L).则节点的融合最终值可由如下公式获得：

(11)

对节点1，有F(118)=m118(H)-m118(L)=0.9947-0=0.9947.

重复上述步骤，同理可得其它节点的融合最终值，如表1中第8列所示.

4 分析讨论

由表1中第2～3列可看出，度中心算法从节点的邻居数量这一局部属性出发，能快速地计算出网络中各节点的一级邻居数量，并依此进行排序，然而对于度值相同的节点，其无法进一步区分其重要性，只能将它们视作同等重要，如节点182和节点152，节点293和节点162等.紧密度中心从节点在网络中所处的位置这一全局属性出发来衡量节点的影响力，表1的第4～5列表明，那些处于网络拓朴中心地位的节点更为重要，能识别不同网络的不同影响力，特别是对于那些度值相同的节点，能根据它们的位置信息进行有效的区分，如节点182和节点152虽然都具有相同的邻居数，但由于它们在网络中所处的位置不同，因而其排名也不同，分别为6和11.结构洞算法从当前节点的邻居的角度来考量节点的影响力，其不仅考量节点的一级邻居数量，还将节点的邻居对该节点的贡献及邻居的影响力等纳入了考虑范围.表1中的第6～7列表明，节点所拥有的邻居数量及邻居的影响力也是很重要的，如节点182和节点152，虽然都拥有相同数量的一级邻居，但由于邻居的影响力不一样，因而它们的排序也不一样.总体而言，上述三种方法都是从特定角度来衡量节点的影响力，有侧重，也有不足，得到的结果也有差异.网络中的节点不是孤立存在的，它受网络拓朴、节点邻居数量、邻居的影响力等多方因素的影响.节点是多属性的.在本文中，基于信度函数通过融合节点的多种属性，以期更为准确地衡量节点的影响力.从表1中的第8～9列可以看出，新方法通过融合节点的度、紧密度和结构洞等属性，最终得到节点的综合唯一评估值，且不存在无法进一步区分的情况.从排序结果来看，本文方法较好地考虑了节点的度中心、紧密度中心和结构洞中心等因素，排名前10的节点分别覆盖了度中心、紧密度中心和结构洞中心的前10、9和7个节点.

5 结语

本文提出了一种基于信度函数的复杂网络中识别节点重要性的方法，通过将节点的相关属性转换为信度函数并据此进行融合，最终得到节点的综合评价指标值并以此排序.实例验证表明，此方法是有效的，能够综合节点单一属性算法的优点，并克服单一属性算法的不足.需要说明的是，本文提出的方法仅考虑了节点的少数属性，并且仅运用于无向无权的网络中，在下一步的工作中，我们将考虑融合节点更多的属性，并且将该方法进一步推广运用到有向有权的网络中.

[参考文献]

[1]Albert-László Barabási,Réka Albert.Emergence of scaling in random networks[J].Science,1999(286):509-512.

[2]Duncan J Watts,Steven H Strogatz.Collective dynamics of‘small-world’networks[J].Nature,1998(393): 440-442.

[3]周涛,张子柯,陈关荣,等.复杂网络研究的机遇与挑战[J].电子科技大学学报,2014(1):1-5.

[4]任晓龙,吕琳媛.网络重要节点排序方法综述[J].科学通报,2014(13):1175-1197.

[5]Réka Albert,Hawoong Jeong,Albert-László Barabási.Error and attack tolerance of complex networks[J].Nature, 2000(406):378-382.

[6]Jianshu Weng,Ee-Peng Lim,Jing Jiang,et al.Twitterrank:finding topic-sensitive influential twitterers[C]. ACM,2010:261-270.

[7]莫泓铭.节点重要度在复杂网络鲁棒性中的应用[J].长春师范大学学报,2016(2):22-25.

[8]Linton C Freeman.Centrality in social networks conceptual clarification[J].Social networks,1978(3):215-239.

[9]Kazuya Okamoto,Wei Chen,Xiang-Yang Li.Ranking of closeness centrality for large-scale social networks[J]. Lecture Notes in Computer Science,2008(59):186-195.

[10]Phillip Bonacich.Factoring and weighting approaches to status scores and clique identification[J].Journal of Mathematical Sociology,1972(1):113-120.

[11]张惠玲,张蒙.基于结构洞指数的网络节点重要度评估[J].计算技术与自动化,2016(1):101-103.

[12]王劲松,李宗育,徐晏琦.基于多属性决策的复杂网络节点攻击研究[J].电光与控制,2016(4):42-47.

[13]Ronald S Burt.Structural holes:the social structure of competition[M].Harvard University Press,2009.

[14]于会,刘尊,李勇军.基于多属性决策的复杂网络节点重要性综合评价方法[J].物理学报,2013(2):46-54.

[15]常振超,陈鸿昶,刘阳,等.基于联合矩阵分解的节点多属性网络社团检测[J].物理学报,2015(21):456-465.

[16]李文兰,王野,李立,等.基于多属性决策合著网络关键节点识别研究[J].情报理论与实践,2017(9):95-100.

[17]Arthur P Dempster.Upper and lower probabilities induced by a multivalued mapping[J].The Annals of Mathematical Statistics,1967(2):325-339.

[18]Glenn Shafer.A mathematical theory of evidence[M].Princeton University Press,1976.

[19]蒋雯,张安,邓勇.基于信度函数的决策及应用[J].计算机工程与应用,2008(31):36-38.

[20]莫泓铭,夏龄.基于证据理论的川西水电开发生态环境评价研究[J].长春师范大学学报,2017(2):35-40.

[21]赵汝鹏,田润澜,王晓峰.基于证据理论的雷达信号融合识别算法改进研究[J].电子技术应用,2017(6):19-22.

[22]韩德强,杨艺,韩崇昭.DS证据理论研究进展及相关问题探讨[J].控制与决策,2014(1):1-11.