2021年2月第2期Vol. 42 No. 2 2021
小型微 型计算 机系统
Journal of Chinese Computer Systems
杨旭华，熊帅
(浙江工业大学计算机科学与技术学院，杭州310023)
E-mail : xhyang@ zjut. edu. cn
摘要：发现复杂网络中最具影响力的节点，有助于分析和控制网络中的信息传播，具有重要的理论意义和实用价值.传统的
确定节点影响力的方法大多基于网络的邻接矩阵、拓扑结构等，普遍存在数据维度高和数据稀疏的问题，基于网络表征学习，本 文提出了一种局部中心性指标来辨识网络中高影响节点(NLC)，首先采用DeepWalk 算法，把高维网络中餉节点映射为一个低
维空间的向量表示，并计算局部节点对之间的欧氏距离；接着根据网络的拓扑结构，计算每个节点在信息的传播过程中，对所在 局部的影响力大小，用以识别高影响力节点.在八个真实网络中，以SIR 和SI 传播模型作为评价手段，将NLC 算法和度中心 性、接近中心性、介数中心性、邻居核中心性、半局部中心性做了对比，结果表明NLC 算法具有良好的识别高影响力传播节点飴 性能.
关键词：节点影响力；网络表征学习；局部节点中心性；复杂网络中图分类号：TP301
文献标识码:A 文章编号:1000-1220(2021)02-0418-06
Identiflcation of Node Influence Using Network Representation Learning in Complex Network
YANG Xu-hua,XIONG Shuai
(Computer Science and Technology College,Zhejiang University of Technology ,Hangzhou 310023 .China)
Abstract ： Finding the most influential propagation nodes in complex networks is helpful to analyze and control the propagation of in
formation in the network , which is of great theoretical significance and practical value. Most of the traditional methods for determining the influence of nodes are based on the adjacency matrix and topology of the network , and the problems of high data dimension and da
ta sparsity are common. Based on Network Representation Learning , this paper proposes an algorithm to identify the high influence propagation nodes of the network ( NLC). Firstly ,the deepwalk algorithm is used to map the nodes in a high-dimensional network into
a vector representation of a low-dimensional space and calculate the euclidean distance between local node pairs. Then ,according to the
topology of the network,the influence of each node on the local area during the propagation of information is calculated to identify the high-influence nodes. In eight real networks , SIR and SI propagation models are used as evaluation methods , comparing the NLC algo rithm with degree centrality , closeness centrality , betweeness centrality , neighborhood coreness , and semi-local centrality , the results
show that NLC algorithm has good performance in identifying high-influence propagation nod
es.Key words : node influence ； network representation learning ； node local centrality ； complex network
1引言
真实世界中的许多系统都可以抽象为复杂网络，比如社 交网络、交通网络、电力网络、通信网络、人物关系网络、流行
病传播网络等.辨识网络中有影响力的传播节点，涉及到网络 的结构和功能等属性，包括度分布，平均距离，连通性，信息传 播，鲁棒性等3〕，在实际应用中，能够控制信息在网络中的 传播⑷、做高效的新闻推广⑸、避免电网中故障的传播⑷、分 析蛋白质之间的相互作用⑺等.
如何有效辨识网络中节点传播影响力的大小，研究者们 已经有了不少研究成果，这些方法总体上可以分为两种类型： 基于局部信息和基于全局信息的判断节点中心性的方法.基 于局部信息的方法，例如：度中心性⑻把节点连接的边的数
量作为衡量的指标；邻居核中心性⑼把节点的一级邻居、二
级邻居和三级邻居节点个数之和当做判断影响力大小的指 标;K-shell 分解方法31，是一种基于节点局部拓扑结构的方 法丄iu 等人认为许多真实网络由于局部的紧密连接而存
在类核结构，导致许多节点的值不能真实的反映节点在网络
中的影响力，他们通过删除冗余边的策略，提高了 K-shell 值 的准确性；郑文萍等人衡量节点在网络连通性中的作用， 通过节点所连边对局部网络连通性的影响来反映该节点在网 络连通性方面的重要性;Chen 等人口结合度中心性和全局
信息，提出了一种半局部中心性方法，实验表现与紧密中心性
相同，但计算复杂度较低；李维娜等人，基于网络的局部社 团结构和节点度的分布情况，提出了一种重要节点挖掘算法
SG-CPMini n &
基于网络全局信息的方法往往能获得比基于局部信息的
算法更高的精确度，但计算复杂度比较高.例如介数中心
收稿日期:2020-02-24 收修改稿日期；2020-04-14 基金项目：国家自然科学基金项目(61773348)资助；浙江省自然科学基金项目 (LY17F030016)资助.作者简介：杨旭华，男，1971年生，博士，教授,CCF 会员，研究方向为机器学习、复杂网络、智能交通；熊0巾，男，1994年
生，硕士研究生，研究方向为机器学习、复杂网络.
2期杨旭华等：利用网络表征学习辨识复杂网络节点影响力419
性和接近中心性：冏，都是基于全局路径的方法，考虑网络中任意节点对之间的路径.谷歌公司提出的PageRank""，通过考虑邻居节点的数量和质量，再进行全局的迭代计算来确定节点的重要性.吕琳環等人提出一种类似于PageRank的算法，在网络中增加了一个背景节点与所有节点进行双向连接，使新的网络成为强连通网络，称作LeaderRank").王斌等人(切考虑网络的结构及属性信息，提出节点信任度的概念，同时将节点信任度引入到PageRank算法中，构建了一种关键节点识别算法TPR(Trust-PageRank)；Lu等人画提出了一种基于信息扩散特性，将节点的局部属性与全局属性相结合的WeiboRank(WR)算法，在微博社交网络数据上表现良好.
上述辨识方法，都是建立在传统的网络表示方法之上的，普遍依赖于网络的邻接矩阵和拓扑结构，具有维度高和数据稀疏的特点，计算复杂度高，在大型网络使用中计算代价比较高.随着网络表征学习技术在自然语言处理等领域的发展和广泛应用，研究者们转而探索如何将网络中的节点表示为低维且稠密的向量，提岀了诸多方法.DeepWalk是网络表征学习的先驱0)，将词表示学习算法word2vec[22]应用在随机游走序列上，从而生成了节点的低维度表示向量.Lineal针对一阶相似度和二阶相似度，提出了一种边采样算法优化目标函数，进而得到节点的向量表示.N o de2vec[241通过改变随机游走序列生
成的方式扩展了DeepWalk算法，将宽度优先搜索和深度优先搜索引入了随机游走序列的生成过程，综合考虑了网络的局部信息和全局信息来表示节点•CANE1251假设每个节点的表示向量由文本表示向量及结构表示向量构成，其中，文本表示向量的生成过程与边上的邻居相关，再利用卷积神经网络和注意力机制对一条边上两个节点的文本信息进行编码，得到节点的表示向量■SDNE1261使用深层神经网络对节点表示间的非线性进行建模，把模型分为两个部分：一个是由Laplace矩阵监督的建模第1级相似度的模块，另一个是由无监督的深层自编码器对第2级相似度关系进行建模，将深层自编码器的中间层输岀作为节点的向量表示.这些算法从不同的角度，采用不同的优化方法，把高维和稀疏的网络映射到低维和稠密的向量空间，保留网络的原有结构，具有计算复杂度低和准确度高等特点.两房退市
在本文中，我们基于网络表征学习提出了一种辨识网络节点影响力的方法.采用网络表征学习DeepWalk算法把高维的复杂网络映射到低维的向量空间，把网络节点映射为欧式空间中低维的向量表示，然后结合网络拓扑信息提出节点的局部中心性，作为判断节点影响力大小的指标.
2基于网络表征学习的节点局部中心性
节点在网络中传播信息时，与其局部的拓扑结构有很大的关系.已有研究表明：节点的K-shell值越大，周围的拓扑结构越紧密，节点向周围区域传播信息的效率越高〔勿，同时，信息传递的强度随着节点间距离的增大而迅速衰减皿)，由此，提出一种基于网络表征学习和局部中心性确定任意节点i的影响力指标：
NLC(i)=Z心X e-')Ti-X/2(J)其中,Ks,■表示节点i的K-shell值必”分别表示节点ij用
DeepWalk网络表征方法映射到低维欧式空间的向量，
比-X」表示两个向量之间的欧氏距离，r(i)表示i节点的三级邻域，即i节点的一级邻居、二级邻居以及三级邻居节点的集合j节点属于r(i)集合.
网络中节点间的距离，本文没有采用网络的最短路径距离，因为会存在如下的问题，如图1所示,i节点在传播它自身的信息时，首先会影响它的一级邻居节点，比如节点k和节点j，当节点A和/被感染后，由于j节点有更多的连接到外部区域的邻居节点(图1中灰节点)，尽管同样是节点i的一级
邻居节点J比k在传播i节点信息的过程中贡献更大【切，所以，信息在网络中的传播，除了距离以外，还与网络的结构密切相关，最短路径距离的长度不能准确的表示信息在传播过程中的衰减，还要根据网络的拓扑结构，对所求节点的邻域节点做进一步的划分.
因为网络表征学习方法不但
可以把高维网络映射到低维的向
量表示，而且可以同时保持网络
的结构，节点间的距离用低维向
量间的欧式距离替代后，不仅考
虑了最短路径距离，而且包含了图1一个有8个节戌和节点周围的拓扑结构信息，能够
9务边的网络更准确的描述信息在网络传播过Fig.1Nitwork with eight程中的衰减因此在本文中，我们
....选择应用DeepWalk方法，把网nodes and nine edges
络节点映射到低维的向量表示，然后用节点相应的低维向量来计算节点之间的距离.
具体地，基于DeepWalk方法，将网络空间映射到欧式空间，把每一个节点表示为一个低维稠密的向量，将具有N个节点的网络G转化为欧氏空间的N个r维向量，一个网络节点及其连边信息对应一个向量，其中任意节点i的向量表示为：Xi=(x.l,X.2,X.3，…，x.,),i=1,2,3,,N,
在本文中，『取N/2
3实验和分析
3.1数据集
为了评估所提出的方法的性能，我们在8个真实世界的网络中进行了实验，这8个网络都是无向网络，也不考虑权重，它们分别是常见形容词和名词的邻接网络adjnoun f30]、科学家合作网络netscience、Ca-GrQc和hep-th[31H]、新西兰宽吻海豚社会网络dolphin1341、小型的facebook社交网络、爵士音乐人合作网络Jazz匈、美国政治图书网络polbooks1371，表1给出了8个真实数据集的拓扑属性参数.其中,N和E分别表示网络的节点数和边数，〈&〉表示网络的平均度，在本文中，考虑到现实世界中网络的度分布往往存在“重尾效应”，令0”=<*>/<*2>[381，表示SIR模型传播的阈值,c表示网络的平均聚类系数.
3.2评价方法和指标
3.2.1SIR疾病传播模型
SIR属于动态传播算法，结果准确性好但计算复杂度高,
420小型微型计算机系统2021年
本文提出的NLC算法及其他静态指标方法计算复杂度低，我们用SIR疾病模型做为基准参照模型去评价不同的判断节点影响力静态指标方法性能的优劣（列.在SIR模型中，如果需要判定一个节点在网络中的传播影响力，则把这个节点设定为网络中唯一的感染节点（Infected），其他节点标记为易感节
表1数据集
Table1Data sets
Network N E〈k〉c
dolphin62159 5.130.1470.27
免费论文下载polbooks1054418.40.0840.488
Jazz198274227.700.0260.617
adj n oun1124257.5890.0730.1728 netscience15892742 3.4510.1440.6378 facebook40398823443.6910.0090.6055 Ca-GrQc524214496 5.5310.05930.5296 hep-th836115751 3.7680.1150.4420
点（Susceptible），在每个时间步，每个感染态节点会以概率0（0=1.50*）感染其易感邻居节点,0”表示SIR模型传播的阈值，然后以概率“（在本文中，我们设置“=1）从疾病中恢复，变成移除态（Recovered），移除态节点不会再被感染.这个过程不断迭代直到网络中没有感染节点为止,r时刻网络中移除态和感染态节点的总数量，记为F（r）,F（r），作为评价r时刻该节点传播影响力大小的指标,F（r）越大，该节点影响力越大. 3.2.2SI疾病传播模型
在该模型中，节点一旦被感染，状态从S变为I之后不能恢复，其他条件和SIR模型相同，在本文中，易感状态节点被感染的概率为苹".如果在相同的时间步的条件下，一个节点感染的网络节点越多，则说明该节点感染能力越强，影响力越大.
3.2.3肯德尔系数
不同的方法都可以按照所计算的传播能力，对网络中所有节点从高到低排序，针对不同的感染率0，我们用肯德尔系数7去评价不同的静态指标方法得到的排序列表和SIR动态传播模型生成的排序列表之间的联系I切，t是一个在[-1, 1]之间的一个数,7■越大，两个序列吻合度越高,T被定义为：
2(M-NJ
N(N-1)
302医院陈菊梅(2)
N c表示两个排序列表相协调元素的数量,M表示二者不协调元素的数量,N表示网络节点总数.
3.3数值仿真
首先，对八个真实网络的每一个节点在本网络内赋予唯一的编号，比如网络1有N个节点，则网络节点的编号应该是1,2,……,N.
3.3.1比较NLC和5种知名中心性方法识别的Top-10高影响力节点的准确性
在表2中，我们以SIR模型计算出来的Top-10节点为基准，在4个真实网络上，用NLC方法，度中心性（DC）、接近中心性（CC）、介数中心性（BC）、邻居核中心性（Cnc）、半局部中心性（CL）分别计算ToplO节点，比较不同方法的准确性，考虑到网络的规模和时间复杂度，本文令『=10[41].具体计算方法为：以dolphin网络为例，首先用SIR模型在t=10时刻，计算得到F（10）数值最大的Top-10节点做为基准，然后用NLC方法算出Top-10节点，如果两组节点有9个相同，则NLC算法的准确率为90%.
表26种中心性算法和SIR模型对排名
前10节点的识别结果
Table2Six algorithms and SIR models
to identify thetop-10nodes
网络dolphin
算法（准确率）
排序DC
(70%)
BC
(60%)
cc
(60%)
Cnc CL
(80%)(80%)
NLC
(90%)
F(10) 115373715151515
23824146383838
346413838464121
434382134342141
55281521413746
61818230304637
7212184151342
830552952525130
9585234221251
10258958173052汉语桥2013
网络adj n oun
算法（准确率）
排序DC
(70%)
BC
(60%)
CC Cnc CL
(70%)(80%)(80%)
NLC
(80%)F(10) 118181818181818
233333523
34444525252352
452524444444444
51051028105105105105
6108010525512851
7251051051251010
828282728262525
92622510552655
102292619325160湖南农业大学学报
网络polbooks
算法（准确率）
排序DC
(80%)
BC
(60%)
CC Cnc CL
(40%)(70%)(90%)
NLC
(90%)F(10) 1931319999
213505913131313
3410885853173
4851350473410
57373107374734
667777774311031
7744153148585
831597367676774
912954112745
104183248741212
网络netscience
算法（准确率）
排序DC
(30%)
BC
(30%)
CC Cnc
(20%)(40%)
CL
(0%)
NLC
(80%)
F(10) 13479793414303455
23515128235143135563
3795171516314325534
4552827575564656335
52952173029171433282133
6143035152914143413354
7143175735541435134757
8143230213212021436135135
9631337602951437562762
102172041124220143854562
在表2中，比较其它5种方法，本文提出的NLC算法在4个数据集中都取得了最高的准确率.接下来，我们比较了各种
2期杨旭华等：利用网络表征学习辨识复杂网络节点影响力421
静态指标算法与SIR模型得到的Top-10节点排序列表的吻合程度，在小型网络polbooks和adjnoun中,6种中心性算法都有较高的准确率,CL算法和NLC算法有相同的准确率，但NLC得到的序列与SIR模型给
出的序列更吻合；在dolphin 和netscience网络中,NLC算法不仅有最高的准确率，而且给出的排序序列与SIR模型给出的序列更吻合；就整体而言，NLC与SIR模型得到的序列保持良好的吻合度.
其中实验结果取1000次实验的平均值，最佳准确率用黑体字标出,F(10)表示SIR模型在第10时间步的结果.
3.3.2比较NLC与5种知名中心性方法在SIR模型下餉肯德尔系数
分别用各种静态指标算法与SIR模型对一个网络中所有节点的影响力排序，然后比较各种静态指标算法得到的节点排序列表和SIR模型得到列表的吻合程度，我们用肯德尔系
如图2所示，针对不同的感染率B，使用NLC和5种知名中心性方法计算出网络中所有节点的影响力大小排序列表，与SIR模型生成的排序列表做对比，得到肯德尔系数T.在adjnoun网络中,BC算法表现最差,CL和Cnc算法表现基本相同，NLC算法表现最好；在polbooks网络中，CC和BC 表现最差,NLC、CL、Cnc表现良好；在netscience网络中，表现最差的还是BC算法,CC和CL算法也表现不佳，当B< 0.04.NLC算法表现最好，总体表现良好；在facebook网络中,CC表现最差，当p>0.04,NLC表现最好；在hep-th网络中，当B<0.04时,NLC算法表现最好，当p>0.04,NLC算法在6种方法中排名第二；dolphin网络中，当B在0到0.04以及0.07到0.1这两个区间时,NLC算法表现最好，优于其它算法；在Jazz和Ca-Grtjc网络中，BC算法表现最差，当B >0.03时,NLC算法表现最好；综上所述,NLC在肯德尔系
数表示这个吻合程度.
0.80
数上表现最佳.
netscience
inoun
b0.70l0.6
0.65
0.60
NLC CC BC DC CL Cnc
00.020.04 0.06 0.080.10
0.020.040.060.080.10
3
NLC CC BC DC CL Cnc
图2NLC,8,BC,DC,CL,Cnc算法的肯德尔系数，取1000实验的平均值.横坐标表示节点被感染的概率，纵坐标表示肯德尔系数Fig.2Kendall correlation coefficient of NLC,CC,BC,DC,CL,Cnc algorithm which are taken as the average value of1000 experiments.The horizontal ordinate represents the probability of the node being infected,and the longitudinal
ordinate represents the Kendall correlation coefficient
3.3.3比较NLC和CL、Cnc方法■所选Top-10节点的平均感染能力
在8种不同的网络中.NLC算法性能均排前列;BC和CC 算法不仅计算量大，而且表现差;Cnc算法和CL算法，在不同的数据集中，表现极不稳定，在有些数据集中表现较好，在有些数据集中甚至差于BC和CC算法.为进一步比较NLC.CL以及Cnc算法的性能，我们使用SI模型检验3种算法性能.
首先用一个算法选出Top-10节点，然后用Top-10节点在第r个时间步之内感染的节点总数与网络节点总数的比值的平均值
I(t)诰
(3)
422小型微型计算机系统2021年
做为该算法的性能指标•在式(3)中，n表示网络节点总数,％，表示Top-10节点中第i个节点第1到第r步感染的节点总数.在相同的时间步和感染概率的情况下，哪一种方法选出的Top-10节点感染的节点越多，可以认为该算法表现越好.
具体实验结果如图3所示，可以看到，NLC算法在4个网络中都取得了最佳性能.在dolphin网络中，NLC算法表现最好,Cnc算法性能最差；在netscience网络中，当时间步大于15后,NLC算法感染的节点比另外两种算法明显增多，达到 稳定的时间也比另外两种算法早，所选Top-10节点表现最好Ca-GrQc网络中，时间步小于10时,3种算法表现相近，大于10后,NLC算法表现最好，且NLC算法在第33个时间步就达到稳定；在hep-th网络中，Cnc算法表现最差，在第42个时间步才达到稳定,NLC算法表现最好.
(d)
©
图3Top-10节点的感染能力和时间步的关系曲线，取1000次实验的平均值.横坐标表示时间步，纵坐标表示第t个时间步内Top-10节点在SI模型中感染的节点数的平均值与网络节点总数的比值
Fig.3Relationship curve of infection ability and time step of Top-10node.The results are taken the average of1000experiments, the horizontal ordinate represents the time step,and the longitudinal ord
inate represents the ratio of the average number of nodes infected by Top-10nodes in the SI model to the total number of network nodes within the t time step
4总结和分析
在本文中，我们基于网络表征学习方法，结合节点的拓扑结构和邻域信息，提出了一种节点局部中心性指标来识别节点影响力的方法•该方法提出网络中的节点的影响力由拓扑结构决定，同时随着距离的增加而衰减•在8个真实网络中，通过和5种知名的中心性方法相比较，在计算Top-10节点、Top-10节点的感染能力和肯德尔系数等方面,NLC算法取得了良好的辨识效果，在分析和控制复杂网络中的信息传播过程中具有广阔的应用前景.
References:
[1]Albert R,Barabasi A L.Statistical mechanics of complex networks
[J].Review of Modem Phy s ics,2001,74(1)：47-97.
[2]Boccaletti S,Latora V,Moreno Y,et al.Complex networks:struc
ture and dynamics[J].Complex Systems and Complexity Science, 2006,424(4-5):175-308.
[3]Newman M E J.The structure and function of complex networks
[J].Siam Review,2003,45(2)：167-256.
[4]Wells C R,Galvani A P.Coupled disease-behavior dynamics on
complex networks:a reviewf J].Physics of Life Reviews,2015,62
(15)：55-56.
[5]Medo M,Zhang Y C,Zhou T.Adaptive model for recommendation
of news[J].Europhysics Letters,2009,88(3)：42-51.
机器人定位技术[6]Albert Reka,Albert Istvdn,Nakarado G L.Structural vulnerability
of the North American power grid[J].Physical Review E,2(X)4,69
(2):59-73.
[7]Li Min,Meng Xiang-mao.The construction,analysis,and applica
tions of dynamic protein-protein interaction networks[J].Journal of Computer Research and Development,2017,54(6):1281-1299.
[8]Bonacich P F.Factoring and weighting approaches to status scores
and clique identification[J].Journal of Mathematical Sociology, 1972,2(1)：113-120.
[9]Bae J,Kim S.Identifying and ranking influential spreaders in com
plex networks by neighborhood coreness[J].Physica a Statistical Mechanics&Its Applications,2014,395(4)：549-559.
[10]Dorogovtsev S N,Goltsev A V,Mendes J F F.K-core organization
of complex networks[J].Physical Review Letters, 2006,96(4)：40601.1-40601.4.
[11]Liu Y,Tang M,Zhou T,et al.Improving the accuracy of the k-
shell method by removing redundant links:from a perspective of spreading dynamics[J].Scientific Reports,2015,5(2)：33~46. [12]Zheng Wen-ping,Wu Zhi-kang,Yang Gui.A novel algorithm for i
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议