基于区域密度曲线识别网络上的多影响力节点

康玲; 项冰冰; 翟素兰; 鲍中奎; 张海峰

doi:10.7498/aps.67.20181000

摘要

复杂网络多影响力节点的识别可以帮助理解网络的结构和功能，具有重要的理论意义和应用价值.本文提出一种基于网络区域密度曲线的多影响力节点的识别方法.应用两种不同的传播模型，在不同网络上与其他中心性指标进行了比较.结果表明，基于区域密度曲线的识别方法能够更好地识别网络中的多影响力节点，选中的影响力节点之间的分布较为分散，自身也比较重要.本文所提方法是基于网络的局部信息，计算的时间复杂度较低.

关键词:

Complex networks are ubiquitous in natural science and social science, ranging from social and information networks to technological and biological networks. The roles of nodes in networks are often distinct, the most influential nodes often play an important role in understanding the spreading process and developing strategies to control epidemic spreading or accelerating the information diffusion. Therefore, identifying the influential nodes in complex networks has great theoretical and practical significance. Some centrality indices have been proposed to identify the influential nodes in recent years, but most of the existing algorithms are only appropriate to the identifying of single influential node. Many times, spreading process is initiated by simultaneously choosing multiple nodes as the spreading sources, such as rumors, opinions, advertisements, etc. Therefore, it is necessary to develop efficient methods of identifying the multiple influential nodes in complex networks. In this paper, a method based on region density curve of networks (RDC) is proposed to identify the multiple influential nodes in complex networks. Firstly, we rearrange all nodes of network in a new sequence, and then plot the region density curve for network. Finally, we identify the multiple influential nodes based on the valley points of region density curve. Using two kinds of spreading models, we compare RDC index with other indices in different real networks, such as degree, degree discount, k-shell, betweenness and their corresponding coloring methods. The results show that the influential nodes chosen according to our method are not only dispersively distributed, but also are relatively important nodes in networks. In addition, the time complexity of our method is low because it only depends on the local information of networks.

Keywords:

作者及机构信息

1.
安徽大学数学科学学院, 合肥 230601

通信作者: 鲍中奎, zkbao@ahu.edu.cn

基金项目: 安徽省自然科学基金（批准号：1808085MF201）、安徽省高校自然科学基金（批准号：KJ2017A025）、浙江省海洋大数据挖掘与应用重点实验室（批准号：OBDMA201502）、安徽大学信息保障技术协同创新中心开放课题（批准号：ADXXBZ201608）和安徽大学研究基金（批准号：01001951，01005102）资助的课题.

Authors and contacts

1.
School of Mathematical Science, Anhui University, Hefei 230601, China

Corresponding author: Bao Zhong-Kui, zkbao@ahu.edu.cn

Funds: Project supported by the Natural Science Foundation of Anhui Province, China (Grant No. 1808085MF201), the Natural Science Foundation of the Higher Education Institutions of Anhui Province, China (Grant No. KJ2017A025), the State Key Laboratory for Ocean Big Data Mining and Application of Zhejiang Province, China (Grant No. OBDMA201502), the Information Security Technology Collaborative Innovation Center of Anhui University, China (Grant No. ADXXBZ201608), and the Anhui University Foundation, China (Grant Nos. 01001951, 01005102).

参考文献

[1]	Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]
[2]	L L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1
[3]	Huang B, Zhao X Y, Qi K, Tang M, Do Y H (in Chinese) [黄斌, 赵翔宇, 齐凯, 唐明, 都永海 2013 物理学报 62 218905]
[4]	Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]
[5]	Shu P P, Wang W, Tang T, Shang M S 2015 Acta Phys. Sin. 64 208901 (in Chinese) [舒盼盼, 王伟, 唐明, 尚明生 2015 物理学报 64 208901]
[6]	Liu Y, Tang M, Do Y H, Hui P M 2017 Phys. Rev. E 96 022323
[7]	Freeman L C 1979 Social Networks 1 215
[8]	Freeman L C 1977 Sociometry 40 35
[9]	Sabidussi G 1966 Psychometrika 31 581
[10]	Bonacich P 1972 J. Math. Sociol. 2 113
[11]	Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nature Phys. 6 888
[12]	Chen D B, L L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777
[13]	Han Z M, Wu Y, Tan X S, Duan D G, Yang W J 2015 Acta Phys. Sin. 64 058902 (in Chinese) [韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰 2015 物理学报 64 058902]
[14]	Su X P, Song Y R 2015 Acta Phys. Sin. 64 020101 (in Chinese) [苏晓萍, 宋玉蓉 2015 物理学报 64 020101]
[15]	Radicchi F, Castellano C 2016 Phys. Rev. E 93 062314
[16]	Ruan Y R, Lao S Y, Wang J D, Bai L, Hou L L 2017 Acta Phys. Sin. 66 208901 (in Chinese) [阮逸润, 老松杨, 王竣德, 白亮, 候绿林 2017 物理学报 66 208901]
[17]	Bao Z K, Ma C, Xiang B B, Zhang H F 2017 Physica A 468 391
[18]	Hu Z L, Ren Z M, Yang G Y, Liu J G 2014 Int. J. Mod. Phys. C 25 1440013
[19]	Zhao X Y, Huang B, Tang M, Zhang H F, Chen D B 2015 Eur. Phys. Lett. 108 68005
[20]	Guo L, Lin J H, Guo Q, Liu J G 2016 Phys. Lett. A 380 837
[21]	Xiang B B, Bao Z K, Ma C, Zhang X Y, Chen H S, Zhang H F 2018 Chaos 28 013122
[22]	Zhao Z Y, Yu H, Zhu Z L, Wang X F (in Chinese) [赵之滢, 于海, 朱志良, 汪小帆 2014 计算机学报 37 753]
[23]	Chen W, Wang Y, Yang S 2009 Proceedings of the 15th International Conference on Knowledge Discovery and Data Mining Pairs, France, June 28-July 01, 2009 p199
[24]	Newman M E J 2004 Phys. Rev. E 69 066133
[25]	Liu Y, Tang M, Zhou T, Do Y H 2015 Sci. Rep. 5 13172
[26]	Liu J G, Lin J H, Guo G, Zhou T 2016 Sci. Rep. 6 21380
[27]	Li R Q, Wang W, Shu P P, Yang H, Pan L M, Cui A X, Tang M (in Chinese) [李睿琪, 王伟, 舒盼盼, 杨慧, 潘黎明, 崔爱香, 唐明 2016 复杂系统与复杂性科学 3 1]
[28]	Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116
[29]	L L Y, Zhou T 2013 Link Prediction (Beijing:Higher Education Press) p286 (in Chinese) [吕琳媛, 周涛 2013 链路预测(北京:高等教育出版社) 第286页]

施引文献

[1]	Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]
[2]	L L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1
[3]	Huang B, Zhao X Y, Qi K, Tang M, Do Y H (in Chinese) [黄斌, 赵翔宇, 齐凯, 唐明, 都永海 2013 物理学报 62 218905]
[4]	Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]
[5]	Shu P P, Wang W, Tang T, Shang M S 2015 Acta Phys. Sin. 64 208901 (in Chinese) [舒盼盼, 王伟, 唐明, 尚明生 2015 物理学报 64 208901]
[6]	Liu Y, Tang M, Do Y H, Hui P M 2017 Phys. Rev. E 96 022323
[7]	Freeman L C 1979 Social Networks 1 215
[8]	Freeman L C 1977 Sociometry 40 35
[9]	Sabidussi G 1966 Psychometrika 31 581
[10]	Bonacich P 1972 J. Math. Sociol. 2 113
[11]	Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nature Phys. 6 888
[12]	Chen D B, L L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777
[13]	Han Z M, Wu Y, Tan X S, Duan D G, Yang W J 2015 Acta Phys. Sin. 64 058902 (in Chinese) [韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰 2015 物理学报 64 058902]
[14]	Su X P, Song Y R 2015 Acta Phys. Sin. 64 020101 (in Chinese) [苏晓萍, 宋玉蓉 2015 物理学报 64 020101]
[15]	Radicchi F, Castellano C 2016 Phys. Rev. E 93 062314
[16]	Ruan Y R, Lao S Y, Wang J D, Bai L, Hou L L 2017 Acta Phys. Sin. 66 208901 (in Chinese) [阮逸润, 老松杨, 王竣德, 白亮, 候绿林 2017 物理学报 66 208901]
[17]	Bao Z K, Ma C, Xiang B B, Zhang H F 2017 Physica A 468 391
[18]	Hu Z L, Ren Z M, Yang G Y, Liu J G 2014 Int. J. Mod. Phys. C 25 1440013
[19]	Zhao X Y, Huang B, Tang M, Zhang H F, Chen D B 2015 Eur. Phys. Lett. 108 68005
[20]	Guo L, Lin J H, Guo Q, Liu J G 2016 Phys. Lett. A 380 837
[21]	Xiang B B, Bao Z K, Ma C, Zhang X Y, Chen H S, Zhang H F 2018 Chaos 28 013122
[22]	Zhao Z Y, Yu H, Zhu Z L, Wang X F (in Chinese) [赵之滢, 于海, 朱志良, 汪小帆 2014 计算机学报 37 753]
[23]	Chen W, Wang Y, Yang S 2009 Proceedings of the 15th International Conference on Knowledge Discovery and Data Mining Pairs, France, June 28-July 01, 2009 p199
[24]	Newman M E J 2004 Phys. Rev. E 69 066133
[25]	Liu Y, Tang M, Zhou T, Do Y H 2015 Sci. Rep. 5 13172
[26]	Liu J G, Lin J H, Guo G, Zhou T 2016 Sci. Rep. 6 21380
[27]	Li R Q, Wang W, Shu P P, Yang H, Pan L M, Cui A X, Tang M (in Chinese) [李睿琪, 王伟, 舒盼盼, 杨慧, 潘黎明, 崔爱香, 唐明 2016 复杂系统与复杂性科学 3 1]
[28]	Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116
[29]	L L Y, Zhou T 2013 Link Prediction (Beijing:Higher Education Press) p286 (in Chinese) [吕琳媛, 周涛 2013 链路预测(北京:高等教育出版社) 第286页]

[1]	汪亭亭, 梁宗文, 张若曦. 基于信息熵与迭代因子的复杂网络节点重要性评价方法. 物理学报, 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
[2]	阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
[3]	孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
[4]	阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
[5]	苏臻, 高超, 李向华. 节点中心性对复杂网络传播模式的影响分析. 物理学报, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
[6]	阮逸润, 老松杨, 王竣德, 白亮, 侯绿林. 一种改进的基于信息传播率的复杂网络影响力评估算法. 物理学报, 2017, 66(20): 208901. doi: 10.7498/aps.66.208901
[7]	韩忠明, 陈炎, 李梦琪, 刘雯, 杨伟杰. 一种有效的基于三角结构的复杂网络节点影响力度量模型. 物理学报, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
[8]	闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙). 基于扩展度的复杂网络传播影响力评估算法. 物理学报, 2015, 64(8): 088901. doi: 10.7498/aps.64.088901
[9]	韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. 物理学报, 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
[10]	胡庆成, 张勇, 许信辉, 邢春晓, 陈池, 陈信欢. 一种新的复杂网络影响力最大化发现方法. 物理学报, 2015, 64(19): 190101. doi: 10.7498/aps.64.190101
[11]	刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
[12]	任卓明, 刘建国, 邵凤, 胡兆龙, 郭强. 复杂网络中最小K-核节点的传播能力分析. 物理学报, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
[13]	于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
[14]	刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
[15]	张聪, 沈惠璋, 李峰, 杨何群. 复杂网络中社团结构发现的多分辨率密度模块度. 物理学报, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
[16]	周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
[17]	吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
[18]	周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
[19]	吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
[20]	李季, 汪秉宏, 蒋品群, 周涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051

计量

文章访问数: 6387
PDF下载量: 124
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

搜索

留言板