*CN102880799A*
(10)申请公布号 CN 102880799 A(43)申请公布日 2013.01.16
(12)发明专利申请
(21)申请号 201210356136.7(22)申请日 2012.09.24
(71)申请人西北工业大学
地址710072 陕西省西安市友谊西路127号(72)发明人于会 刘尊 李勇军 陈华胜
瞿幼苗 李伟华(74)专利代理机构西北工业大学专利中心
61204
代理人陈星(51)Int.Cl.
G06F 19/00(2006.01)
权利要求书 1 页 说明书 11 页 附图 4 页权利要求书1页 说明书11页 附图4页
(54)发明名称
一种基于多属性决策的复杂网络节点重要度综合评价方法(57)摘要
本发明提出了一种基于多属性决策的复杂网络节点重要度综合评价方法,利用网络中单个节点的度中心性、介数中心性、接近中心性、结构洞等多个指标作为该节点重要性评价的多个属性进行综合计算,从而确定节点在网络中的重要程度。由于采用了基于多属性决策的节点重要性综合评价方法,得到了准确的节点重要性排序,克服了现有发明中利用单一指标评价复杂网络中节点重要性的不足。利用本发明对“风筝网络”、“ARPA网络”、“科研合作网络”的计算结果表明,本发明不仅可以针对不同类型的复杂网络节点进行其重要性的综合计算,而且可以选择多个不同的节点重要性评价指标进行综合评价,具有很好的扩展性。CN 102880799 ACN 102880799 A
权 利 要 求 书
1/1页
1.一种基于多属性决策的复杂网络节点重要度综合评价方法,其特征在于:包括以下步骤:
步骤1:确定复杂网络N个节点中每个节点的决策方案,形成决策方案集合为:A={A1,…,Ai,…,AN},其中Ai表示第i个节点对应的决策方案;确定评价每个节点重要度的指标属性集合为S={S1,...,Sm};构建决策矩阵X:
其中Ai(Sj)为第i个节点的第j个指标属性值,i=1,...,N,j=1,...,m;
步骤2:按照下式对决策矩阵X进行标准化处理:
其中Ai(Sj)max=max{Ai(Sj)|1≤i≤N},Ai(Sj)min=min{Ai(Sj)|1≤i≤N},所述效益型指标为指标值属性越高,重要度越大的指标,成本型指标为指标值属性越高,重要度越小的指标;得到标准化后的决策矩阵为R=(rij)N×m;
步骤3:采用层次分析法确定每个指标的权重,其中第j个指标的权重为wj,j=1,...,m,∑wj=1;
步骤4:由步骤2得到的决策矩阵R=(rij)N×m和步骤3得到的各指标权重,构建加权规范化矩阵Y:
根据矩阵Y确定正理想决策方案A+和负理想决策方案A-:
其中L={1,...,N};计算每个决策方案Ai到正理想方案A+和负理想方案A-的距离:
(i=1,...,N;j=1,...,m)(i=1,...,N;j=1,...,m)
计算每个决策方案Ai到理想方案的贴近度Zi:
0≤Zi≤1,i=1,...,N
将每个决策方案到理想方案的贴近度Zi按从大到小进行排序,贴近度越大,则对应节点在网络中的重要程度越高。
2.根据权利要求1所述一种基于多属性决策的复杂网络节点重要度综合评价方法,其特征在于:评价每个节点重要度的指标属性为度中心性、介数中心性、接近中心性以及结构洞;其中度中心性、接近中心性、介数中心性为效益型指标,结构洞为成本型指标。
2
CN 102880799 A
说 明 书
1/11页
一种基于多属性决策的复杂网络节点重要度综合评价方法
技术领域
本发明涉及复杂网络中节点的重要性评价方法,具体为一种基于多属性决策的复
杂网络节点重要度综合评价方法。
[0001]
背景技术
寻找网络中的关键节点是网络科学的重要研究内容之一。
[0003] 复杂网络本质上的非同质拓扑结构,决定了网络中每个节点的重要程度有很大的不同。尤其对各种各样具体的网络比如科研合作网络、疾病传播网络、航空网络、电力网络等,对这些复杂网络中节点的重要性进行评估,发掘网络中的重要节点,具有重要的实用价值。例如:在大规模计算机网络中,可以根据服务器节点的重要程度进行有针对性的备份和冗余建设,在节省资源的同时又能保证网络的鲁棒性;在罪犯关系网络中,重要度排序有利于区分首要分子、骨干分子和追随分子,迅速定位犯罪团伙的头目;在传染病、病毒网络中,可以通过发现感染者并有针对性地治疗和隔离病源,从而有效防止病毒的传播和扩散;在谣言传播的网络中,也可快速定位重要的传播节点,有效阻断谣言的传播等。总之,如何挖掘出复杂网络中的重要性节点,更有针对性地分析其性质,从而为制定正确有效的策略和预防措施是复杂网络研究的基本问题之一。[0004] 在各种复杂网络中,用定量分析的方法寻找网络中最重要的节点(边),或者分析节点相对于其它一个或多个节点的重要程度已经取得了许多进展。目前一般从社会网络和系统科学两种角度分析节点的重要程度。社会网络分析方法的核心思想是“重要性等价于显著性”,对网络中重要节点的发掘以不破坏网络的整体性为基础。一般可以通过节点的中心性指标来衡量,常用的复杂网络中心性指标有度中心性、介数中心性、接近中心性、特征向量中心性等,这些指标从不同的角度刻画了单个节点在网络中的重要程度。系统科学分析方法的核心思想是“重要性等价于该节点(集)被删除后对网络的破坏性”,通过删除某节点(集)后,借助网络连通性等指标的变化来确定其重要程度,一般采用的方法有节点删除法、节点收缩法等。
[0005] 无论是社会网络角度的基于节点显著性等价于重要性,还是系统科学角度的破坏性等价于重要性,对网络节点重要性的度量方法都是基于节点之间的差异性,从某一角度探讨网络节点的重要性问题。比如:基于度的重要性评估方法强调节点与邻接节点连边的数量,可以在一定程度上显示节点在网络中的重要程度,但具有度相同的节点,在网络中的重要程度未必相同;介数刻画了节点或边对网络中信息或流的控制能力,但一般按照最短路径计算,并不符合现实规律;特征向量中心性则充分考虑与目标节点建立连接节点的重要性,并通过邻接节点的重要性来确定目标节点的地位;子图中心性反映了节点在网络局部结构的贡献大小。上述的每种方法都有自身的优点和缺点,均是针对具体问题提出来的,分别从不同的方面刻画了节点在特定网络中的重要性。但现实世界的复杂网络千变万化,很难从一个指标来说明某个节点在网络中的重要程度,网络中一个节点的重要性不仅和其
[0002]
单个的度量指标有关,而且和网络的整体性质相关,需要从不同的角度,利用节点的多个指
3
CN 102880799 A
说 明 书
2/11页
标来进行综合评价。发明内容
要解决的技术问题
[0007] 为了克服现有节点重要性评价方法的不足,本发明提出了一种基于多属性决策的复杂网络节点重要度综合评价方法,利用网络中单个节点的度中心性、介数中心性、接近中心性、结构洞等多个指标作为该节点重要性评价的多个属性进行综合计算,从而确定节点在网络中的重要程度。[0008] 技术方案
[0009] 本发明首先将复杂网络中的每一个节点看作一个方案,以度中心性、接近中心性、介数中心性、结构洞等多个重要性评价指标作为该方案评价的指标属性,从而将复杂网络节点重要性的评价转化为多属性决策问题,决策的准则是评价各个方案在复杂网络中的重要程度。
[0010] 本发明的技术方案为:
[0011] 所述一种基于多属性决策的复杂网络节点重要度综合评价方法,其特征在于:包括以下步骤:[0012] 步骤1:确定复杂网络N个节点中每个节点的决策方案,形成决策方案集合为:A={A1,…,Ai,…,AN},其中Ai表示第i个节点对应的决策方案;确定评价每个节点重要度的指标属性集合为S={S1,...,Sm};构建决策矩阵X:
[0006] [0013]
其中Ai(Sj)为第i个节点的第j个指标属性值,i=1,...,N,j=1,...,m;[0015] 步骤2:按照下式对决策矩阵X进行标准化处理:
[0014] [0016]
[0017]
其中Ai(Sj)max=max{Ai(Si)|1≤i≤N},Ai(Sj)min=min{Ai(Sj)|1≤i≤N},所述效益型指标为指标值属性越高,重要度越大的指标,成本型指标为指标值属性越高,重要度越小的指标;得到标准化后的决策矩阵为R=(rij)N×m;
步骤3:采用层次分析法确定每个指标的权重,其中第j个指标的权重为wj,j=1,...,m,∑wj=1;[0019] 步骤4:由步骤2得到的决策矩阵R=(rij)N×m和步骤3得到的各指标权重,构建加权规范化矩阵Y:
[0018] [0020]
4
CN 102880799 A
说 明 书
3/11页
[0021] [0022] [0023] [0024]
根据矩阵Y确定正理想决策方案A+和负理想决策方案A-:
其中L={1,...,N};计算每个决策方案Ai到正理想方案A+和负理想方案A-的
距离:
[0025] [0026] [0027] [0028] [0029]
(i=1,...,N;j=1,...,m)(i=1,...,N;j=1,...,m)
计算每个决策方案Ai到理想方案的贴近度Zi:
0≤Zi≤1,i=1,...,N
将每个决策方案到理想方案的贴近度Zi按从大到小进行排序,贴近度越大,则对
应节点在网络中的重要程度越高。
[0030] 所述一种基于多属性决策的复杂网络节点重要度综合评价方法,其特征在于:评价每个节点重要度的指标属性为度中心性、介数中心性、接近中心性以及结构洞;其中度中心性、接近中心性、介数中心性为效益型指标,结构洞为成本型指标。[0031] 有益效果
[0032] 本发明的有益效果是:由于采用了基于多属性决策的节点重要性综合评价方法,得到了准确的节点重要性排序,克服了现有发明中利用单一指标评价复杂网络中节点重要性的不足。利用本发明对“风筝网络”、“ARPA网络”、“科研合作网络”的计算结果表明,本发明不仅可以针对不同类型的复杂网络节点进行其重要性的综合计算,而且可以选择多个不同的节点重要性评价指标进行综合评价,具有很好的扩展性。[0033] 因此,本发明提出了一种基于多属性决策的节点重要性的综合评价方法,该方法将复杂网络中的每一个节点看作一个方案,其多个重要性评价指标作为该方案的属性,通过计算每个方案到理想方案的接近程度,最终得到该节点的重要性综合评价结果。利用本发明对“风筝网络”、“ARPA网络”、“科研合作网络”的计算结果表明,本发明可以有效地评价不同类型复杂网络中单个节点的重要性。另外,本发明并不局限于发明书中所列举的几个节点重要度的评价指标,还可以很容易的进行扩展。[0034] 为了清楚阐述本发明的优点,本发明的方法和已有的文献针对ARPA网的计算结果作了对比,文献[1]:利用重要度评价矩阵确定复杂网络关键节点,物理学报,2012,vol.61(5):050201,此文献中综合考虑了网络中节点的效率、节点度值和相邻节点的重要度贡献,用节点的度值和效率值来表征其对相邻节点的重要度贡献,然后给出了关键节点的确定算法,取得的较为理想的效果;但由于该文献仅考虑了节点的度值和效率值,没有考虑介数的计算,对一些网络中处于“桥”位置的关键节点,不能很好的发现其重要性。文献[2]:通信网中节点重要性的评价方法.通信学报,2004,25(8):129-134,该文
5
CN 102880799 A
说 明 书
4/11页
献依据的是移除节点后,网络直径的变化和生成树的数目变化确定节点的重要程度;但该文献采用的是系统科学的分析方法,是以破坏网络的整体性来评价节点在网络中的重要程度的,没有考虑移除节点后导致网络拓扑变化时的节点重要性,而且,这种各个节点单独分析的方法需要解决由于节点移除导致的网络拓扑结构变化甚至被分割的问题。文献[3]:利用重要性贡献矩阵确定通信网中最重要节点,北京航空航天大学学报,2009,vol.35(9):1076-1079,该方法定义了节点重要性贡献矩阵,重点考虑了通信网络中不同节点间的联接关系对节点重要性的影响,节点的初始重要性设为该节点的介数,每个节点对其相邻节点重要程度的贡献与该节点的度有关,从而评价网络中的重要节点,取得了较好的效果;但该文献仅仅考虑了节点的介数和度值,没有考虑网络中节点的效率等其它指标,故而在重要节点删除后形成的孤立社区中并没有取得良好的效果。本发明采用了基于社会网络分析的多个指标,针对不同类型的复杂网络进行了实验,在ARPA网的实验中和上述的三个文献的节点重要性评价结果做了对比,实验结果表明本发明方法所发现的前5个网络重要节点删除后,可以将ARPA网分割为孤立的7个社区,而文献[1]删除前5个重要节点后能分割为3个孤立社区,文献[3]删除前5个重要节点后能分割为5个孤立社区,文献[2]删除前5个重要节点后能分割为7个孤立社区,和本发明得到的结果相同。但文献[2]采用的就是节点删除的方法,是通过破坏网络的联通性来判断网络中的重要节点的,而本发明所用的指标均是社会网络中的中心性评价指标,是以不破坏网络的整体性为基础来综合评价节点的重要程度,所以两种方法的结果有一定差异。附图说明
[0035] 图1本发明方法的流程图[0036] 图2风筝网络
[0037] 图3风筝网络使用本发明计算得出的结果排序图[0038] 图4ARPA网络
[0039] 图5ARPA网络计算后删除前5个重要节点后和其他文献的结果对比图[0040] 其中(a)本文算法删除前5个节点后的图形,(b)文献[1]删除前5个节点后的图形,(c)文献[2]删除前5个节点后的图形,(d)文献[3]删除前5个节点后的图形[0041] 图6对C-DLBP“科研合作网”采用本发明计算得到的Top5%重要节点示意图[0042] 图7对C-DLBP“科研合作网”采用本发明计算得到的Top10%重要节点示意图具体实施方式
下面结合具体实施例描述本发明:[0044] 实施例1:
[0045] 本实施例以Krackhardt设计的“风筝网络”为例,参照附图2,该网络有10个节点,每个节点重要度的指标属性有度中心性DC、介数中心性BC、接近中心性CC、结构洞C,其中,度中心性、接近中心性、介数中心性为效益型指标,即指标属性值越大,则节点的重要程度越高;而结构洞为成本型指标,指标属性值越小,节点的重要程度越高。[0046] 上述每个指标属性,在公开文献通用的定义为:[0047] 定义1:度中心性(Degree centrality)
[0043]
6
CN 102880799 A[0048]
说 明 书
5/11页
节点i相关联的边数与节点i可能存在的最大边数的比率。度中心性的表达式
为:
DCi=ki/(N-1),
[0050] 其中ki表示网络中与节点i关联的边数。度中心性定义表明了一个节点与其它节点直接通信的能力,数值越大,在网络中越重要。[0051] 定义2:接近中心性(Closeness centrality)
[0052] 假设dij表示以节点i为起点,以j为终点的最短路径中所含边的数量,则节点i的接近中心性可以表示为其到网络中其他所有节点距离之和的倒数。接近中心性的表达式为:
[0049] [0053] [0054]
节点接近中心性的值越大,表明节点居于网络中心位置的程度越大,相应地也就
越重要。
定义3:介数中心性(Betweenness centrality)
[0056] 介数中心性的表达式为:
[0055] [0057]
式中gjk(i)表示节点j和k之间通过节点i的最短路径的条数。gjk为从节点j到
节点k之间所有最短路径的总数。介数中心性定义认为如果一个节点是网络中其它节点对之间通信的必经之路,则其在网络中必具有重要地位。节点介数中心性的值越高,则该节点的影响力越大,相应地也就越重要。[0059] 定义4:结构洞(Structure Hole)
[0060] 在网络中如果两个个体或两个群体之间不存在直接连接,且它们之间不存在间接冗余关系,则两者之间的阻碍就是结构洞。Burt提出了计算结构洞的网络约束系数对网络闭合性和结构洞进行测度。节点i的网络约束系数的计算表达式为:
[0058] [0061]
其中,q为连接节点i和节点j的间接节点,Pij为节点i花费在节点j上的时间
(精力)占其总时间(精力)的比例。网络约束系数Ci越小,结构洞程度越大,节点的位置越重要。
[0063] 根据上述指标定义,我们得到“风筝网络”中节点各指标的计算结果,即得到决策矩阵X,再对X进行标准化处理:
[0062] [0064]
[0065]
其中Ai(Sj)max=max{Ai(Sj)|1≤i≤N},Ai(Sj)min=min{Ai(Sj)|1≤i≤N},得到标准化后的决策矩阵为R=(rij)N×m,如下表所示:
[0066]
7
CN 102880799 A[0067]
ID 1 2 3 4 5 6 7 8 9 10
[0068]
DC
说 明 书
C
CC 0.3448 0.4762 0.6667 0.7143 0.7143 0.5556 0.6667 0.5556 0.5882 0.5882
BC 0.00 16.00 28.00 16.67 16.67 0.00 7.33 0.00 1.67 1.67
6/11页
0.1111 1.25 0.2222 0.5556 0.3333 0.4944 0.5556 0.4701 0.5556 0.4701 0.3333 0.7059 0.6667 0.4746 0.3333 0.7059 0.4444 0.5783 0.4444 0.5783
从决策矩阵R中可以看出:该网络中度中心值最大的节点是节点7,节点3虽然度
中心值只有3,但却占据了网络中最好的信息控制地位,有最大的介数中心值,节点4和5有最大的接近中心值和最小的结构洞值,并且在网络结构中的位置相同。
[0069] 采用层次分析法(AHP-Analytic Hierarchy Process)确定每个指标的权重,其中第j个指标的权重为wj,j=1,...,m,∑wj=1,层次分析法首先采用(0,1,2)三标度法来对每一指标进行两两比较后,建立一个比较矩阵B,其次通过变换将比较矩阵转化为判断矩阵,并进行一致性检验,最后得到指标权重。[0070] 比较矩阵B中元素的定义为:
[0071]
[0072] [0073]
对度中心性DC、介数中心性BC、接近中心性CC和结构洞C四个指标按照三标度法
构建的比较矩阵B为:
B DC C
DC C CC BC 1 2
0 0 1 18
0 0
CN 102880799 A
CC BC
[0074]
说 明 书
2 2
1 1 2 2
0 1
7/11页
比较矩阵B的构建基于以下因素考虑:由于度中心性涉及的网络结构因素最少,
所以和其他指标相比重要性较差;而结构洞指标和接近中心性指标相比,理论上很难对比两个指标的好坏,在矩阵B中给出了重要性相同的评价;介数中心性和其他三个指标相比,可以准确发现网络中的“桥”节点,而其他三个指标则无此功能,因此本文在矩阵B的构造中给介数中心性赋予了比其他指标重要性更高的值.
[0075] 对比较矩阵B,按照极差法构造判断矩阵,经一致性检验后,得到各相关指标权重的值分别为:wDC=0.0861,wC=0.2073,wCC=0.2073,wBC=0.4993。[0076] 根据得到的决策矩阵R=(rij)N×m和四个指标的权重,按照公式:
[0077]
[0078] 建立的加权规范化矩阵Y为:
[0079]
[0080] [0081] [0082]
根据矩阵Y确定正理想决策方案A+和负理想决策方案A-:
其中正理想决策方案A+为:{0.0861 0.2073 0.2073 0.4993};负理想决策方案A-为:{0.0143 0.0780 0.1001 0}。
+-[0084] 每个决策方案Ai到正理想方案A和负理想方案A的距离:
[0083] [0085] [0086] [0087] [0088]
(i=1,...,N;j=1,...,m)(i=1,...,N;j=1,...,m)
以及每个决策方案Ai到理想方案的贴近度Zi:
0≤Zi≤1,i=1,...,N
9
CN 102880799 A[0089] [0090]
ID D+说 明 书
以及Zi的结果为:
D- Zi
8/11页
其中
1 0.5317 0.0000 0.0000 2 0.2343 0.3042 0.5650 3 0.0463 0.5225 0.9185 4 0.2026 0.3462 0.6308 5 0.2026 0.3462 0.6308 6 0.5080 0.0904 0.1511 7 0.3688 0.2173 0.3707 8 0.5080 0.0904 0.1511 9 0.4735 0.1262 0.2104 10 0.4735 0.1262 0.2104
将每个决策方案到理想方案的贴近度Zi按从大到小进行排序,贴近度越大,则对
应节点在网络中的重要程度越高。[0092] 从上表中可以得出:Z3>(Z4=Z5)>Z2>Z7>(Z9=Z10)>(Z6=Z8)>Z1。[0093] 合理的解释为:对于风筝网络,节点3处于全局信息控制能力最大的位置,节点3的删除会导致网络不再联通,因此其重要度最大;而节点4和节点5在网络中结构位置相同,因此具有相同的Z值,并且节点4或节点5的删除会导致网络中节点间的通信距离增大,因此重要度次之;节点2是介数值较大的节点,删除节点2会导致节点1与网络断开,但仅仅断开1个节点,说明节点2虽然重要,但没有比删除节点4和5对网络造成的影响大;节点7虽然度数最大,但节点7的删除仅仅使得风筝网络的通信冗余度减少,并不影响整个网络的通信能力;对于节点9和节点10,节点6和节点8,分别在网络中的结构位置相同,但这些节点的删除并没有对网络的通信造成影响,因此排序更为靠后。[0094] 从对“风筝网络”实验可以看出,运用本发明对简单网络节点重要度的评价可以取得良好的结果,能够很好地区分各节点之间的重要程度,有效避免了单个节点单个属性评价重要程度的不足。[0095] 实施例2:
[0096] 本实施例采用附图3中给出的美国ARPA(Advanced Research Project Agency)网络拓扑,它由21个节点和23条链路组成。ARPA拓扑是目前分析网络节点重要性时普遍使用的干线网络拓扑,其网络平均度中心值在2-3之间,大部分节点的度中心值为2。
[0091]
10
CN 102880799 A[0097]
说 明 书
9/11页
下表给出了按照本发明的方法以及“背景技术”中所提到的与文献[1]、文献[2]
和文献[3]所述方法确定的ARPA网络节点重要性评价的排序结果。
[0098]
11
CN 102880799 A
说 明 书
10/11页
[0099]
[0100]
四种算法得出的节点重要性排序都略有差异,主要是因为各自的判断侧重点不
同。文献[1]和文献[3]使用了社会网络的分析方法,利用节点重要度评价矩阵来确定复杂网络中的关键节点;文献[2]使用了系统科学的方法,依据的是移除节点后,网络直径的变化和生成树的数目变化确定节点的重要程度。本发明方法采用综合评价的算法得出的最重要节点是3,同文献[2][3]得出的结论一致。
图5给出了采用上述四种方法得到的ARPA网节点重要程度排序后删除前5个重要节点后的情况。图5(a)为本文算法删除前5个重要节点后的图形,可以看出前5个重要节点删除后,ARPA网络被独立地划分为7个社区,说明本发明方法很好地计算出了ARPA网的关键节点;图5(b)和图5(d)给出了文献[1]和文献[3]得到的计算结果排序后删除前5个重要节点后的图形,其中图5(b)中仅将网络划分为3个社区,图5(d)中则将网络划分为5个社区,对比结果说明本发明的评价方法优于文献[1]和文献[3]中的方法。图5(c)也得到7个孤立社区,单从社区分割的数量上看,与本发明提出方法的结果是相同的,但文献[2]采用的就是节点删除的方法,是通过破坏网络的连通性来判断网络中的重要节点的,而
[0101]
12
CN 102880799 A
说 明 书
11/11页
本发明所用的指标均是社会网络中的中心性评价指标,是以不破坏网络的整体性为基础来综合评价节点的重要程度,所以两种方法的结果有一定差异。[0102] 实施例3:
[0103] 本实施例采用C-DBLP“科研合作网”的一个最大的子集,其中包含462个节点,975条边。按照本发明提出的方法对该网络进行节点重要度评估后,图6给出了采用本发明算法的计算结果排序中选取Top5%重要节点的图示,其中最大的圆形节点表示网络的中心,其它较大的圆形节点为重要节点。图7是选取了Top10%重要节点的图形。可以看出,Top5%和Top10%的节点可以很好的覆盖“科研合作网”中的重要节点,这些节点一般都是课题组的负责人,他们在与其他课题组的项目合作中起了非常重要的联接作用。
13
CN 102880799 A
说 明 书 附 图
1/4页
图1
14
CN 102880799 A
说 明 书 附 图
2/4页
图2
图3
图4
15
CN 102880799 A
说 明 书 附 图
3/4页
图5
图6
16
CN 102880799 A
说 明 书 附 图
4/4页
图7
17
因篇幅问题不能全部显示,请点此查看更多更全内容