计算机应用研究
Application Research of Computers
Vol. 33 No. 9
Sep. 2016
基于网络结构的节点中心性排序优化算法$
张凯，马英红
(山东师范大学管理科学与工程学院，济南250014)
摘要：针对社交网络中节点中心性排序算法存在的不足，从网络结构的角度提出了一种准确有效的节点中心 性排序算法（CentraRank)。运用新浪微博数据和随机数据的模拟实验证明了算法的可行性和有效性，并根据佩 龙一佛罗贝尼乌斯定理证明算法的收敛性。实验结果表明，该算法能够克服其他中心性算法的缺陷，在精度和 收敛度方面均有所提升。最后在该算法的基础上提出了一种基于网络结构的边中心性排序优化算法（Edge-
Rank) ， 并验证了算法的正确性。
关键词：中心性；排序算法；网络结构；精度中图分类号：TP393; TP301.6
文献标志码：A
文章编号：1001-3695(2016)09-2596-05
doi：10.3969/j.issn. 1001-3695.2016.09.007
Centrality ranking algorithm based on network structure
Zhang Kai，Ma Yinghong
(School of Management Science & Engineering, Shandong Normal University, Jinan 250014, China)
Abstract： To solved the problem that nodes centrality ranking algorithm of networks worked badly in quality, this paper deve
loped an efficient algorithm based on network structure. This paper applied the random data to confirm the feasibility and validity and used the Perron-Frobenius Theorem to prove the convergence of the algorithm. Simulation experiments show that the algorithm is more effective than the compared ones in the precision and convergence. On the bases of nodes centrality ranking algorithm, this paper proposed the edges centrality ranking algorithm and then verified the validity.
Key words： centrality； ranking algorithm； network structure； precision
大优势;b)利用网络全局属性的指标进行节点中心性排序，如
〇引言
信息技术的快速增长带动了生活的网络化,人们的生活中 也存在各种各样的网络:在线社交网络、科研网络以及交通网 络等。社会网络是人们通过各种关系建立起来的联系,并通过 成员之间的交互作用形成的一种网络化结构。社会网络分析 法就是对于社会网络的关系结构或者属性进行分析，行动者可 以是人、社区或者群体等,他们之间的关系能够反映出一定的 现象或者数据。诸多数据可以表示为二元图G=(F,S),其中 的
F
特征向量[5]、邻居度[6]以及紧密性[7]等,这些算法往往复杂度 较高,但是考虑的网络信息也更加全面;c)利用网络位置的中
心性排序算法，最具代表性的就是K-核分解[8'9]算法;d)利用 随机游走™进行节点中心性排序，这种方法在基于节点属性 中比较常见，也可以利用网络结构判断节点的中心性。李星等 人[11]借鉴随机游走的思想，提出了一种中心性的快速算法，并 证明了算法在复杂度方面有一定的改进。
许多基于节点属性衡量指标都是基于PageRank算法和
HITS
表示研究的成员集合是成员之间的关系的集合。社会
算法，并结合相关的网络属性进行排序。Cha等人[12]从
网络的一个突出特点是存在少数的关键节点，这类节点对研究 网络的功能和保持网络的稳定性具有重要的作用。例如网络 在遭受外界蓄意攻击时，关键节点遭到攻击就会导致整个网络 瘫痪。研究网络节点重要（中心）性排序是亟待解决的问题, 这对处理信息流、预防传染性的传播以及网络上的其他重要的 行为具有非常重要的意义。王林等人[1]通过社会网络、交通 网络等几个实例指出了中心化的意义。孙睿[2]介绍了国内外 节点重要性排序的研究现状，指出节点重要性排序主要涉及基 于网络结构和基于节点属性的重要性排序两个方面。
基于网络结构的节点重要性排序衡量指标较多，主要研究 有四个方面:a)利用网络局部属性的指标进行节点中心性排 序，常见的是度排序算法[3•'在节点中心性衡量方面占据较
收稿日期：2015-05-08;修回日期：2015-06-23 资助项目（20133704110003)
粉丝数量、转发次数以及引用次数三个方面衡量节点用户的重 要性,Romero等人[13]运用HITS算法结合粉丝的消极相关性 提出新的中心性衡量指标。研究社会网络的重要任务之一就 是对于节点的中心性进行排序，不同网络的结构存在差异性， 所以如何有效地评估节点在不同网络结构中的中心性是研究 社会网络关键问题之一。目前，基于信息流的边排序算法并不 少见。Fortimato等人[14]用移除网络中的边而导致的网络效率 改变值来衡量边的中心性;Newman等人[15]用边上经过的最短 路径的条数定义边中心性;Me〇a等人[16]提出K-path指标，该 指标基于信息传播能力计算网络中边的重要性。
PageRank算法最初是用来衡量Google网页重要性的算
法。PageRank算法已应用到很多领域，有学者将算法理论和
基金项目：国家自然科学基金资助项目（71471106);高等学校博士学科点专项科研基金
作者简介：张凯（1989-),女，山东德州人，硕士研究生，主要研究方向为社交网络（970055982@ qq.com);马英红（1971-),女，教授，主要研究方 向为复杂网络.
第9期张凯，等:基于网络结构的节点中心性排序优化算法• 2597 •
数学的知识结合解决PageRank算法的收敛速度问题[17];有将 传统PageRank算法应用到网页排序方面。例如戚华春等 人[18]提出了 PagelWk-Time算法，解决了原算法偏重旧网页问 题;李凯等人[19]将网页被点击次数作为集体个性化向量应用
于PageRank算法中，提高了搜索引擎查询结果的精度。也有 学者将PageRank算法应用到社会网络的领域，用于网络中节 点的中心性排名。Lyu等人[2()]提出LeaderRank算法对网络的 节点进行排序，结果表明LeaderRank算法比PageRank算法排 序更精准;陈少钦等人[21]提出了一种实时中心性算法（MU-
Rank);刘建国等人[22]指出在复杂网络中节点排序方面，Page- Rank 算法考虑网络的全局拓扑特性，但是也忽略了其他一些
实际因素。PageRank算法在社会网络领域都是结合节点属性 指标进行中心性排序，基于网络结构并与节点度中心性、中介
中心性排序算法结合的不多见。本文借鉴经典的PageRank (以下简称PR)算法的节点中心性排序的思想，加入紧密性和 中介性指标，提出了 CentmRank中心性算法模型，并证明了
CentmRank的收敛性。通过搜集的新浪微博数据证实了算法
的可行性和有效性。用度排序指标作为原始的中心性节点，加 快算法的收敛速度;并在此基础上提出基于节点的边中心性排 序算法（EdgeRank)，并验证了算法的正确性。
1算法的相关准备
本文研究的网络主要是有向无权网络，复杂网络可以表示
成一个二元图G(F，E)，其中的F表示所有节点或顶点的集 合3是图中边的集合，节点之间的关系可以用邻接矩阵表示。
在网络中成员的重要性往往用节点的中心性进行衡量。 中心性衡量指标可以分为四大类[23] :a)节点的度中心性，描述 一个节点是如何被连接的;b)紧密性表示一个节点抵达其他节 点的难易程度;c)中介性表示一个节点在网络中与其他节点连 接的重要性;d)邻居节点度的大小反映节点邻居的重要程度。
节点的度中心性。用度测量的中心性是网络中最直接的 地位指标，一个节点的度中心性可以表示为
di(g)/(n- 1)
(1)
式（1)描述节点的度中心性，其取值范围为（〇，1)，度中心性 越接近1表示节点越重要。但是度测量的中心性指标只能衡 量网络的局部信息。紧密性指标考察给定的节点和任意其他 节点的紧密程度，该指标表示为
m^in-
(2)
尽管紧密性能够衡量一个节S和其他中心性节点的接近 程度，但该算法仅考虑节点局部接近性，没有远程连接和网络 的整体结构。中介性指标是测量节点在网络中的位置优势，中 介性指标表示为
以
=
x
\\k,j\\ (n -P^1/) (nPjkj) -2)
(3)
2
节点的中介性越大越能够反映它在网络传播中的重要位 置，中介性针对节点的局部位置的关键性进行衡量有比较显著 的效果。邻居度表示的是在网络中节点随机选取它的一个邻 居度分布的情况，这个指标认为一个节点的重要性是由它的邻 居的重要性来决定的。邻居节点度分布可以表示为
P(d)
= ldP(d)d (4)
PageRank算法也是衡量节点中心性的传统算法之一，
PageRank的数学模型如下：
PR(A) =(1 -d) +d( z
= i C([)
(5)
其中:为网页4的
PageRank值
;为链接到网页
乃的PageRank值;C (〇为网页乃的出度数量为阻尼系 数，〇 < d < 1，通常d被设定为〇. 85。从式(5 )中可以看出算法 考虑了度和出（入)度对于节点结构的影响。一
个网页的入度
越多表示该网页越重要。
2节点中心性算法的优化
本文从网络的结构出发，提出了衡量节点中心性的新算
法，并验证了算法的正确性和有效性。2.1算法优化思想2.1.1 算法模型的优化
本文用7个点的无向网络（图1)[24]说明目前算法存在的 问题以及改进的原因。表1给出了图1中节点的中心性比较。
图
1 7个点的无向网络
表1图1中的节点中心性的比较
中心性指标
节点1、2、6和7
节点3和5
节点4度0.330.50.33紧密性
0.40.550.6中介[■生
00.530.6PageRank
0.33
0.5
0.33
由图1和表1中可以得出以下结论:
a) 考虑度中心性。从表1中的结果可以看出节点4心性与节点1、2、6和7的相等，但从图1中看出节点4的中心 性要远远大于节点1、2、6和7的中心性。如果去掉节点4,网 络的结构会发生变化，对于信息传输产生很大的影响，所以度 中心性衡量该网络时会出现偏差。
b)
考虑PageRank算法的中心性。从式（5)中看出PageRank 算法仅考虑了节点的度和邻居的特点 ，所以和度中心性产
生了相同的结果，PageRank算法在衡量该网络时也会导致偏差。c)
紧密性和中介性的值衡量节点在抵达其他节点的难易 程度和重要程度。从表1中看出在PageRank算法中缺乏这方 面的指标，并且从表2中可以看出紧密性和中介性指标与Page-
Rank 算法的相关性不大，所以将这两个指标和 PageRank 算法
线性结合能够达到互补的效果。选取均值是因为在式（2)和 (3)中可以看出两个指标均与最短路径有关系，并且两个指标 代表不同的意义，如果单独考虑三个指标需要设置两个调整参 数，增加模型的复杂度。
刘建国等人[22]在节点重要性排序进展中也指出四大中心 性指标各有利弊:度指标简单直观，但是只反映了节点的局部 特征;邻居度能够考虑不同邻居的影响；中介性考虑了节点的 负载能力；紧密性考虑节点的局部接近性，依赖于网络的拓扑 结构。他们在最后的结论中还指出中心性指标均是在不同的 角度评价节点。付立东等人[25]指出利用全局和局部结合的角 度，设计出一种基于结构的中心性度量方法成为必要。
所以本文提出新的算法模型，既保留PageRank算法的优 点，又加入紧密性和中介性指标进行调整，简单地线性相加能 够将不同指标的优点组合，得到的新算法命名为CentmRank (以下简称CR算法）。由于不同的指标适用于不同的网络，M
的中 -
• 2598 •计算机应用研究第33卷
能够裉据实际网拿靈右调整被本太的樓型能更符食网络特 &
算海的模型如下；
CRj -/j.^w^CRj + (1 -fijCi
I
矩阵使讀其'到的每个项相加等于1,春_一个唯一猶等负 特征值的单位特怔向.量（特征值为1的特征向量)*若/^ = 1， 标准化的矩阵满足佩龙一怫罗敕尼乌斯定理，则一建存在唯一
的非负的Cfl,厕算法一g是收敛的。着，则令s = C/?/M， 献转换成；=恥，同_特征值为1 a因此，特征向量是唯一 6|
式中各鑫数.的舍文如T%
a) Cfl,表示节点，:的中心性值，是衡量节点中心性的最终指标。
b) W
是邻接矩阵„會向网络申的邻接矩阵是仅包含0和
1的矩阵，且
['1 是 C:中的斑
1〇 酬
(7)
是调整系数，是用来衡量原始PR算法与，紧密性和中
介性指标ft据的权重大小取值会决定参数古据的比倒，M 较大，说明PR算法占据的权重大。本文确定调韁系数采取的 实证法=(通_体鮮___：最_的调整系数。
d)C,.是节点;'的中介性和紧密性指标的均直。
= (m-i + &,}/1
(8.)
其中:叫是节桌i的紧密性值，计算方法如式<2)所示;是 节点〖的中介性值，计算方法如式(3)所示。
2.1.2 輕始中心值的选取
虽然初始直选取并不影响最终的结果座是初始中心值选 取对_
法至袭^,能在一窠__上喊少算法的运行坎数，
提升算法的性能，由、于本文算法延续了 PR算法思想，所以在 选欺初始楦时以各种指标和PR算法的皮尔逊相关性为依据，
如_ 2所.艰s:
表2备指标的皮尔逊相美性
PR中0.140介性
0. 622入度
0.146出度
0.564总度
紧0.120
密性
在表^中看扭，入度指标和PH算法的最终结条的相 关性最大，在算法运行过程中能够加速算法的收敛、降低算法 的运行次_，所魏本文难取网络的入度指标作为初始:中心值《
数据量是擧响算法复杂度的一个非常重要的因.素,原算法 为降低运行次縣取了 〇 ~1的随机数作为初始中心值，本文 为进一步地提升算法的性能，将标准化的入度指标作为初始的 中心値,:#_结:果中证明了本算我的优象 2.2算法设计
:鷥•*=的具雜步骤如下:i
a)
输人邻接矩阵6 ,并将矩阵进行标准化，得到矩阵P;
b) 根据式(2)和(3)计算每个节点的m,和
值,并根据
式(8)得出每个节点的C,值；
4选取式1)中标准化的网絡慶備作为初.始的参心性值
QT
,并确定M的值:；
d)对每一1、节点“根据式(6)依次计靠每个节点的Ci?,眞:;
«?),判:断緒果的收敛性，翥 mas( al».{ C/T - Cft) ) > 0. _1, 输出Cft;香则重复歩骤d>,6 2.3算法收敛性证明
算法主要取决于式(6)，因此，，只需要证明式（6)的收敛性 即可a;而式(6)的收敛性等价宁桃的收敛性，
证明：对每一个节点_«，霉味=^|%®,.。因此，对网络 中康翁节6
，Cfl =M • 1/1/ • CR,
讀于||定n X «矩阵1/1/, Cfl即
为射:应M的特征霜量。式〈:6)的收敛性等赠于求特征爾量翁
唯一性a根据佩龙^弗罗:只尼乌廣定通_p6]，如果难负的随机
的,故算法收敏。
经过以上的征明过卷可知，式(6)暴收欽的。
3
节点中心性算法实验结果与分析
新浪微博中的关注s’是一种单向、无须对方确认的关系，
只要用户喜欢就可以关ft对方，通过新浪微博的关疰关系构建 的网翁更能体规用户的主动需求:。柯鲁数据乗自:于社交网站
新浪徽博，利用253彳、单个用户，采集用户之间的关注关系，如 节点〗:关浅节点i，那么构成霜_'藤连攘新浪微薄关注关系网络由Pajet软件实规可视化，如图2 所示。两络中节点代表新浪徼博的用户，如节点1关注节点 .2,那么:1:—设构成有輿连接，网絡有.253个节,g 510 .条边D 从图中看出节点之间的互动比较少，这与新浪微博的性质相 符，新浪繼爾是一种弱关系构建的网络,网络中关注倾向于在 K
li
人之间展开:，藥规一种比较稀逾的拭況。数据是以自我为 中心构處的网》，所以网鄭中不存在孤立的苷点。网絡•大部
分节点的总度比较小，仅少数节点的总度较大,这和大部分的 雾际网雄碁本相符a新浪徽:博网络是比较常见的一養審向网 络，并鳳通过关注关系构建更能体现用户的主观需求,用于算 法的结桌分析更准确。
图
2
新漬微博关注关系两齋
3.1 M值的确定
无论雜平》>R算法还裹CR算法来说，/*值的确定都蠢一 个难点《本文采用实际数据拟合,用误差来区分不同取值的效
果，读盡值越小，敎果就越好a A »上的证明可知，式(6)巾的 M是求解CR的关键。为了求解M的值,利用图2中的新浪微 博数据进行实证计算夸
M眞看摄核心算法模謹中的调整系数,为:了获取最ft償, 本文来取擬差大小评定M_it本文误差齒公式为
其中^一和A分别代_*排#结果中相邻两点的Cft值，由于
CR_法的值非唯一性冰，在多次运算续程中取总撰靈大:小
均值评定:於値》分别取M =丨〇-1，〇■ 2.，...，〇.9丨，在MATLAB■中 觀g运行勘次^获取9个对:歲:的弘值迸行比较^翁圈3中:发 现读差能够较好地.K分憧，.当M = 〇. 8和弘=〇. 9时，褒S泡 值巖小，且鏡差是逐渐减小的，这与'PR _播中的〇. 85 •常接 近a圈2新浪徽博案例中本家也选取弘=0. 85作为调整系数。 3.2中心性排序结果对比
对于图2的新浪慠博关注关系网络数据„本节依据CR算 法选取了前八名的用户并获取这些用户在节点总度、节点人 度、中介性以及PR等代表性的排序结果进行对比，分析这些
第9期张凯，等:基于网络结构的节点中心性排序优化算法
• 2599 •
用户的变化情况，结果如表3所示。
表
3
各类中心性排序算法的排序结果对比
编号
237用户名总度
入度
中介性
PRCR240张泉灵21611163赵晓42166数据挖掘53442423186宋丹丹324334134王子多8101125倪正东99248
51爱国者冯军75388667周晓鹏
677
78
从表3中可以看出，PR算法的排序结果和入度相关性较 大，但是没有考虑中介性等指标，将本文CR算法和PR算法的 排序结果进行对比也可以看出本文算法的准确性。表中编号 163和166的CR和PR的排序结果正好相反，用户“数据挖掘 与数据分析”在
CR
算法中排名第3，但是在PR算法中排名第
4，用户“数据挖掘与数据分析”比用户“宋丹丹”在CR
算法中
排名有所提前，是因为考虑表中的中介性指标，用户“数据挖 掘与数据分析”的中介性排名远远大于用户“宋丹丹”，导致排
名有所提前，表中编号51和248也出现了同样的情况。表中 编号134和186的CR算法排名较PR算法排名都有上升，同 样可以看出是中介性指标起的作用。3.3网络鲁棒性结果对比
本文还通过鲁棒性考察节点排名的变动更加符合实际。 鲁棒性是进行系统分析的关键性指标，并且对于网络的稳定性 具有重要的意义。本文中用最大连通子图来说明CR算法比
PR
算法的实际意义更加明确，使用图2新浪微博关注关系网
络数据，在MATLAB 7. 0软件和Windows X
P
系统环境下仿真，
结果如图4所7K。图中横坐标1，5，…，10分别代表在PR和
CR
算法中移除排名前1、前5以及前10名的节点；纵坐标代 表最大连通子图中节点的个数。
图3
不同M值下的 图4
恶意攻击下最大连
误差大小
通子图中节点数量的变化
在图4中可以看出，PR算法和CR算法在1、2和4这三个 点出现重合，是因为PR算法和CR算法排在前两名的用户都 是“张泉灵”和“赵晓”，并且两算法前四名的用户也完全相同； 但是在后续的过程中，CR算法面对恶意攻击最大连通子图中 节点数量变化得更快，这说明CR算法的排序结果对于网络的 鲁棒性更重要，可以得出CR算法的结果更符合现实意义的结 论。并且横坐标达到9之后，最大连通子图的数量趋于稳定， 仿真过程终止。3.4算法精度分析
算法精度是衡量算法性能的重要指标之一，本文对比了五 种不同算法的误差，用误差大小体现算法精度。误差的公式也 采用其中'^和'分别代表在排序结果中相邻两 点的CR值，运用图2新浪微博关注关系网络数据，最终求得的 结果如表4、图5所示。表4中1、8、16…分别代表前1、8、16项… 的累加值，因为72项之后误差都为0，所以考察72项之前的项。
表
4
各类算法误差比较
比较项
1
8
1624324048566472CR0.00970.04450. 0542
0.0565
0.05930.06010. 06040.06090.06160.0618PR
0.01710. 0503
0.05660.05980.06220.06280. 06320.06380.06460.0656入度
0.0260. 05620.06320. 06670.06840.07020.07020.07020.07020.0702中介数 〇• 0424 0• 1356
0.1539
0.1645
0.1668
0.1680
0.1681
0. 1681
0.1681
0.1681
从表4和图5中能够得到以下结论：
a)
本文的算法精度要远远大于其他四种中心性排序算法
(误差远远小于其他算法），在误差趋于稳定的过程中，算法的 优势还是比较明显的，并且CR算法在节点数量非常大的情况 下，最大平均误差为0. 0618，远远小于PR的0. 0656，所以能够 接受该算法。
b)
在节点个数达到10之后，误差指标变化幅度较小，达
到70左右基本保持不变，这是因为在新浪微博中的用户关注 关系是一种有向弱关系，所以用户之间的双向信息交互行为相 对少，也就是说处于活跃的用户数量较少。在实际的社会网络 中，处于中心位置的用户数量很少，大部分的节点都处在无交 互的状态。实验结论与现实情况吻合。3.5时间复杂性分析
本节总共选取7个案例，前6个案例是随机生成的有向网 络，第7个案例是图2的新浪微博关注关系网络，算法在MAT-
LAB 7.0 软件和 Windows XP 系统环境下平均运行 100 次，得
到的结果如图6所示。图6中，表示矩阵的规模，=丨4,8, 16,32,64，128,254丨分别表示的是该点应用的案例是4 x4, 8 x 8，…的邻接矩阵构造的网络，依此类推。
图5
各类中心性排序
图6
PR和CR算法在不同矩阵
算法的精度对比
规模下的运行次数对比
从图6中能够得到以下结论：
a)
矩阵规模和运行的次数不相关。伴随着矩阵规模的增
大，运行次数呈现先降低后升高的现象，表明两者不存在一定
的相关关系。
b)
在同等网络规模下，本文算法的运行次数少，远远快于
原来的PR算法。例如在〃 =32的随机网络中，算法运行100 次之后得到的PR平均运行结果为10,得到的本文算法的平均 运行次数是6次，结果显示了本文算法的可行性。并且在图中 还能够看出伴随网络规模的增加，算法的运行次数并不增加。
4基于节点的边中心性排序算法
本文从网络结构的角度，在节点中心性算法的基础上将网
络中的边转换成网络中的节点，提出一种基于节点的边中心性
排序EdgeRank算法（以下简称ER算法）。4.1算法思想
ER
算法的构造如下：
a)将网络中的边转换成点，然后运用点中心性排序算法
解决边排序问题。转换方法如图7所示。其中（a)代表的是 有向网络转换，图7中上半部分的边1、2和3转换成下半部分 的点1、2和3，转换前后均是有向网络；（b)代表的是无向网络
• 2600 •
计算机应用研究
第33卷
转换，图中上半部分的边1、2和3转换成下半部分的点1、2和 3，转换前后均是无向网络。
图7
有向和无向网络转换模型
为了说明网络转换前后的等价性，本文运用网络的度指标 和中介性指标来说明。在图7中得出有向网络中编号为1的 边出度为2，编号2和3的边的位置平行，并且入度都为1，通 过编号为1的边才能够到达编号为2和3的边，转换后的图形 也是如此。无向网络中三条边是全连通的，转换后的网络是完 全图。可以看出这种转换方法不仅能够保证从边到点的等价 替换，还能够保证各边在网络中的位置不变，转换之后的模型 还能够简化网络，容易计算边的各种属性值。
b)用CentmRank算法对转换后的网络排序，得到网络边 中心性排序结果。4.2算法准确性分析
4.2.1 无向网络算法准确性分析
迈克尔罢工网络是进行边中心性算法的经典案例[27]，网 络中包含24个点和37条边以及3个社团。网络描述的是 1973年发生的一场罢工活动，最初指定的Sam-Wendle没能够 及时终止罢工活动，迈克尔指出Bob-Norm这条边最利于终止 罢工，这条边位于三个社团的重叠部分，在网络中发挥着最重 要的作用。Simko运用NetworGame软件计算出迈克尔罢工网 络中居于最中心的边是Bob-Norm,他们能够100%终止罢工， 并且指出最不利于罢工终止的边是Sam-Wendle，他们终止罢 工的可能性仅有8%。无向网络边排序结果如图8所示。
从图8(其中横坐标表示转换之后的边序号）中可以看出， 17号边中心性排序结果为1，正好对应边Bob-Norm,说明17号 边在网络中发挥着领导者的作用，在这条边的领导下能够迅速 地终止罢工。37号边的中心性排序结果为37,正好对应边
Sam-Wendle，算法得出的排序结果不仅与NetworGame软件[27]
一致，还完全符合实际情况，都能够说明算法的正确性。
4.2.2 有向网络算法准确性分析
有向网络选取的是图2中新浪微博网络节点排序算法中 前8名的用户构建的网络，网络中包含8个节点和13条有向 边，进行网络转换后得到的排序结果如图9所示。其中横坐标 表示转换之后的边序号。
从图9可以看出，序号为7的边位于第1名，序号为6的 边居于第13名，单凭排序结果无法确定算法结果的优劣。为 了更好地说明算法的性能，采取鲁棒性对于排序结果进行测 试，说明边的中心性排序结果的实际意义。为了对边的重要性
和节点的重要性进行比较，本文定义新指标进行对比分析。
网络的破坏率=总节点个数
-
最大连通子图中点个数/总点个数
（9)
从式(9)可以看出网络的破坏率与边或者节点的中心性 成正比，破坏率越大，说明该边或者节点在网络中的位置越重 要。图10为有向网络中攻击节点和边的破坏率对比。其中， 横坐标表示边和节点排序的结果序号，每次删除对应的一个
点。实验是在MATLAB 7. 0软件，Windows XP系统环境下仿
真的。从图10可以看出，随着边排序编号的增加，网络的破坏 率递减，说明了边排序算法的准确性。攻击节点和边网络的破 坏率出现很大的不同，攻击网络的边对于网络的破坏率明显增 大，在实际生活中也是如此，切断一条交通要道往往使两地成 为孤立的个体。攻击边导致网络的最大破坏率能够达到
〇
. 76%，能够导致高达80%的网络瘫痪，这对于实际生活中的
网络能够产生较大影响;而攻击网络的节点最高的破坏率仅有
50%，这与边的破坏率相比还差距比较大。
图11是攻击边的破坏率。其中横坐标表示边排序的结果
序号总和，如2就代表排在前2名的用户。ER算法排序代表 攻击在ER算法中居于前六名的边序号;random表7K在随机生 成的数据抽取三组同规模的数据与CR算法对比。
d4 d
2 移除的节点或者边的排序编号 移除的边的数量
图
10
有向网络中攻击节点
图
11
有向网络中攻击
和边的破坏率对比边的破坏率
在图11中，为了降低随机性的概率，在破坏率前10名的 随机数据中选取三组数据。ER算法产生的网络破坏率远远大 于随机数组，由于网络中仅包含13条边，所以在删除4条边之 后网络的破坏率基本重合，说明ER算法排序的准确性。
5结束语
本文提出了节点中心性排序CR算法，证明算法的收敛
性，并进行仿真实验验证算法的误差和收敛次数远远小于PR
算法;在此基础上提出了基于节点的边中心性排序ER算法， 证明了算法的正确性。本文还存在很多的不足:a)仅仅考虑 了网络结构指标，忽视了节点的属性指标，以后进一步将结构 指标和属性指标进行融合，定义更加符合实际的中心性排序算 法;b)将边转换成节点后，网络中邻接矩阵规模增大，复杂度 提升。参考文献：
[1]
王林，张婧婧.复杂网络的中心化[J].复杂系统与复杂性科2006,3(1) ：13-20.
[2] 孙睿，罗万伯.网络舆论中节点重要性评估方法综述[J].计算机
应用研究，2012,29(10) :3606-3608 ,3628.
[3] 任卓明，邵凤，刘建国，等.基于度与集聚系数的网络节点重要性
度量方法研究[J].物理学报，2013, 62(12) :12-18.
[4] Freeman L C. A set of measures of centrality based on between-ess
[J]. Sociometry, 1977,40( 1) ：35-41.
[5] Bonacich clique identification P. Factoring [ and weighting approaches to status scores and
J ]. Journal of Mathematical Sociology,
1972,2(1) ：113-120.
(下转第 2605 页）
学，
第9期包晓晓，等：改进混沌烟花算法的多目标调度优化研究• 2605 •
的平衡,仍有待考量。
5结束语
本文提出了一种求解多目标调度问题的改进混沌烟花算
364.
[8] Ding Ke, Zheng Shaoqiu, Tan Ying. A GPU-based parallel fireworks
algorithm for optimization [ C ]//Proc of the 15th Annual Conference on Genetic and Evolutionary Computation Conference. Yew York ： ACM Press,2013：9-16.
[9]
王培崇，高文超，钱旭，等•应用精英反向学习的混合烟花爆炸优 化算法[J] •计算机应用，2014,34(10) :2886-2890.
法（CPAFWA)，设计了一种双元锦标赛和动态淘汰制相结合的 帕累托非劣解集构造方法,该策略在求取帕累托非劣解集上的 时间复杂度明显优于传统的双元锦标赛法。为了避免算法陷 人局部最优,提高求解质量，根据逻辑自映射产生混沌序列，对 20%的种群进行混沌搜索。通过求解本文所构建的三目标作 业车间调度模型，证明所提算法的有效性。
在Job-Shop标准问题上的仿真实验结果表明，混沌搜索过 程可以有效提高作业车间调度问题的求解质量。然而,结果同 时表明，该搜索过程会降低算法的整体时间效率，导致算法的 实际运行时间较长。因此,如何在不影响算法求解质量的情况 下提高混沌搜索效率仍值得进一步研究。参考文献：
[10] Zheng Yujun, Song Qin, Chen S Y. Multi objective fireworks optimization for variable-rate fertilization in oil crop production[ J]. Applied Soft Computing,2013,13(11) ：4253-4263.(5) ：515-528,
[12] Coello C A,Lechuga M S. MOPSO ： a proposal for multilple objective
particle swarm optimization [M]. Washington D C： IEEE Press, 2002:1051-1056.
[13] Sha D Y, Lin H H. A multi-objective PSO for Job-Shop scheduling
pr〇blems[J]. Expert Systems with Applications,2009,37(2) ：l-6.[14] El-Gohary A, Al-Ruzaiza A S. Chaos and adaptive control in two
prey,one predator system with nonlinear feedback [ J]. Chaos, S〇li- tons and Fractals,2007,34(2) ： 443-453.
[11] 谭营，郑少秋•烟花算法研究进展[J]•智能系统学报，2014,9
[15] 刘长平，叶春明•基于逻辑自映射的变尺度混沌粒子群优化算法 [1 ] Baker K. Introduction to sequencing and scheduling [ M]. New
[】].计算机应用研究，2011，28 (8):2825-2827.York: Wiley, 1974:1-15.
[2] 雷德明，吴智铭•基于粒子群优化的多目标作业车间调度[J].上 [16] Mehrabian A R, Lucas C. A novel numerical optimization algorithm
inspired from weed colonization [J]. Ecological Informatics, 2006, 海交通大学学报，2007,41 (11) :1796-1800.
1(4) ：355-366.[3] 覃朝勇，刘向，郑建国•求解多目标Job-Shop生产调度问题的量子
[17 ] Beasley J E. OR-Library ： distributing test problems by electronic mail 进化算法[J] •计算机应用研究，2010，27(3) :849-852.
[J]. Journal of the Operational Research Society, 1990,41[4] 王伟玲，李俊芳，王晶•求解多目标作业车间调度问题的双种群遗
(11) ： 1069-1072.传算法[】].计算机集成制造系统，2011，17(4):808-815.
[18] Ponnambalam S G, Ramkumar V, Jawahar N. A multi-objective ge[5] 任晓莉.LS0改进CGA解决多目标作业车间调度问题[J] •计算
netic algorithm for Job-Shop scheduling [ J ]. Production Planning 机应用与软件，2015,32(3):60-64.[6]
肖晓伟，肖迪，林锦国，等•多目标优化问题的研究概述[J] •计算
and Control,2001,12(8) ：764-774.
[7] Tan Ying, Zhu Yuanchun. Fireworks algorithm for optimization
[C ]//Advances in Swarm Intelligence. Berlin ： Springer, 2010 ： 355-(上接第26〇0页）
机应用研究，2011，28(3) :805-827.
[19] Zitzler E, Thiele L. Multi-objective evolutionary algorithms ： a com
parative case study and the strength Pareto approach [ J ]. IEEE
Trans on Evolutionary Computation, 1999 ,3(4) ：257-271.
[6] Bonacich P. Power and centrality ： a family of measures [ J].
can Journal of Sociology, 1987,92(5) ：1170-1182.
Arneri-
[7] Jackson M 0, Wolinsky A. A strategic model of social and economic
netw〇rks[J]. Journal of Economic Theory, 1996,71 (1) ：44-74.[8] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential
spreaders in complex networks[J].
[16] De Meoa P, Ferrarab E, Fiumara G, et al. A novel measure of edge
centrality in social networks [ J ]. Knowledge-Based Systems, 2012, 30(6) ：136-150.
[17] Soon I Y,Koh S N. Speech enhancement using 2D Fourier transform
[J]. IEEE Trans on Speech and Audio Processing,2003, 11
(6) ： 717-724.
Nature Physics,2010(6) ：888-
893.
[9] Carmi S,Havlin S,Kirkpatrick S. A model of Internet topology using
k-shell decomposition [J] • Proceedings of the National Academy of Sciences of USA, 2007,104(27) ：11150-11154.
[10] Li Ping, Zhang Jie, Xu Xiaoke, et al. Dynamical influence of nodes
revisited ： a Markov chain analysis of epidemic process on networks [J]. Chinese Physics Letters, 2012,29(4) ：048903.[11] 李星，钟志农，李洋.一种随机游走中心性的快速算法[J].计算
机应用研究，2013,30(8) :2337-2340.
[12] Cha M, Haddadi H, Benevenuto F, et al. Measuring user influence
in twitter： the million follower fallacy [ C ]//Proc of the 4th International Conference on Weblogs and Social Media. 2010：97-105.[13 ] Romero D M, Galuba W, Asur S, et al. Influence and passivity in so
cial media [C]//Machine Learning and Knowledge Discovery in Databases. Berlin： Springer-Verlag, 2011 ： 113-114.
[14 ] Fortunato S, Latora V, Marchiori M. A method to find community
structures based on information centrality [ J ]. Physical Review E, 2004, 70(5) ：056104.
[15] Newman M,Girvan M. Finding and evaluating community structure in
networks [J]. Physical Review E, 2003, 69(2) ： 26113.
[18] 戚华春，黄德才.具有时间反馈的PageRank改进算法[J].浙江工
业大学学报，2005,33(3) : 272-275.[19 ]李凯，赫极龄，左万利• PageRank-Pro: —种改进的网瓦排序算法
[J]•吉林大学学报:理学版，2003,41 (2) :175-179.
[20] Lyu Linyuan, Zhang Yicheng, Yeung C H. Leaders in social net
works, the delicious case[J]. PLoS ONE, 2011, 6(6) ：l-9.[21] 陈少钦，范磊，李建华• MURank:社交网络用户实时影响力算法
[J]•通讯技术，2013(3) :88-92.
[22] 刘建国，任卓明，郭强，等•复杂网络中节点重要性排序的研究进
展[J]•物理学报，2013,62(17):178901.
[23] Borgatti S P. Centrality and network flow [ J ]. Social Networks, 2005,27(1) ：55-71.
[24] Jackson M 0. Social and economic networks [ M]. [ S. 1. ] ： Princeton
University Press, 2008.
[25] 付立东，高琳.模块密度谱分的复杂网络社团发现方法[J].西安
电子科技大学学报，2010,37(5) :916-92L
[26] Meyer C D. Matrix analysis and applied linear algebra[ M]. [ S. 1.]：
SIAM ,2007.
[27 ] Simko G I, Csermely P. Nodes having a major influence to break co
operation define a novel centrality measure ： game centrality [ J ] • PLoS ONE,2013 ,8(6) ：6-12.
因篇幅问题不能全部显示，请点此查看更多更全内容