-
如何用定量分析的方法识别复杂网络中哪些节点最重要, 或评价某个节点相对于其他一个或多个节点的重要程度, 是复杂网络研究的热点问题. 目前已有多种有效模型被提出用于识别网络重要节点. 其中, 引力模型将节点的核数(网络进行k-核分解时的ks值)看作物体的质量, 将节点间的最短距离看作物体间距离, 综合考虑了节点局部信息和路径信息用于识别网络重要节点. 然而, 仅将节点核数表示为物体的质量考虑的因素较为单一, 同时已有研究表明网络在进行k-核分解时容易将具有局部高聚簇特征的类核团节点识别为核心节点, 导致算法不够精确. 基于引力方法, 综合考虑节点H指数、节点核数以及节点的结构洞位置, 本文提出了基于结构洞引力模型的改进算法 (improved gravity method based on structure hole method, ISM)及其扩展算法ISM+. 在多个经典的实际网络和人工网络上利用SIR (susceptible-infected-recovered)模型对传播过程进行仿真, 结果表明所提算法与其他中心性指标相比能够更好地识别复杂网络中的重要节点.How to use quantitative analysis methods to identify which nodes are the most important in complex network, or to evaluate the importance of a node relative to one or more other nodes, is one of the hot issues in network science research. Now, a variety of effective models have been proposed to identify important nodes in complex network. Among them, the gravity model regards the coreness of nodes as the mass of object, the shortest distance between nodes as the distance between objects, and comprehensively considers the local information of nodes and path information to identify influential nodes. However, only the coreness is used to represente the quality of the object, and the factors considered are relatively simple. At the same time, some studies have shown that the network can easily identify the core-like group nodes with locally and highly clustering characteristics as core nodes when performing k-core decomposition, which leads to the inaccuracy of the gravity algorithm. Based on the universal gravitation method, considering the node H index, the number of node cores and the location of node structural holes, this paper proposes an improved algorithm ISM and its extended algorithm ISM+. The SIR model is used to simulate the propagation process in several classical real networks and artificial networks, and the results show that the proposed algorithm can better identify important nodes in the network than other centrality indicators.
-
Keywords:
- complex networks /
- spreading influence /
- gravity model /
- H index /
- k-shell method
[1] Lü L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1
Google Scholar
[2] Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200
Google Scholar
[3] Albert R, Barabási A L 2002 Rev. Modern Phys. 74 47
Google Scholar
[4] Alshahrani M, Fuxi Z, Sameh A, Mekouar S, Huang S 2020 Inform. Sciences 527 88
Google Scholar
[5] Albert R, Jeong H, Barabási A L 1999 Nature 401 130
Google Scholar
[6] Chen D B, Lu L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777
Google Scholar
[7] Sabidussi G 1966 Psychometrika 31 581
Google Scholar
[8] Freeman L C 1977 Sociometry 40 35
Google Scholar
[9] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[10] Lü L Y, Zhou T, Zhang Q M, Stanley H E 2016 Nat. Commun. 7 10168
Google Scholar
[11] Bae J, Kim S 2014 Physica A 395 549
Google Scholar
[12] Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031
Google Scholar
[13] Zareie A, Sheikhahmadi A, Khamforoosh K 2018 Expert Syst. Appl. 108 96
Google Scholar
[14] Fei L, Lu J, Feng Y 2020 Comput. Ind. Eng. 142 106355
Google Scholar
[15] 韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰 2015 物理学报 64 058902
Google Scholar
Hang Z M, Wu Y, Tan X S, Duan D G, Yang W J 2015 Acta Phys. Sin. 64 058902
Google Scholar
[16] Wang Z X, Du C J, Fan J P, X Y 2017 Neurocomputing 260 466
Google Scholar
[17] 闫光辉, 张萌, 罗浩, 李世魁, 刘婷 2019 通信学报 40 109
Google Scholar
Yan G H, Zhang M, Luo H, Li S K, Liu T 2019 J. Communications 40 109
Google Scholar
[18] Alon U 2007 Nat. Rev. Genet. 8 450
Google Scholar
[19] Benson A R, Gleich D F, Leskovec J 2016 Science 353 163
Google Scholar
[20] Li Y, Deng Y 2018 Int. J. Comput. Commun. Control 13 792
Google Scholar
[21] Wang J, Qiao K Y, Zhang Z Y 2019 Future Gener. Comp. Sy. 91 1
Google Scholar
[22] Morone F, Makse H A 2015 Nature 527 544
[23] Zhong L F, Liu Q H, Wang W, Cai S M 2018 Physica A 511 78
Google Scholar
[24] Ma L L, Ma C, Zhang H F, Wang B H 2016 Physica A 451 205
Google Scholar
[25] Li Z, Ren T, Ma X Q, Liu S M, Zhang Y X, Zhou T 2019 Sci. Rep. 9 1
Google Scholar
[26] Yang X, Xiao F Y 2021 Knowl-Based Syst. 227 107198
Google Scholar
[27] Burt R S 2004 American J. Sociology 110 349
Google Scholar
[28] Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602
[29] Newman M E J 2002 Phys. Rev. E 66 016128
Google Scholar
[30] Kendall M G 1945 Biometrika 33 239
Google Scholar
[31] Knight W R 1966 J. Amer. Statist. Assoc. 61 436
Google Scholar
[32] Rossi R, Ahmed N 2015 Twenty-ninth AAAI Conference on Artificial Intelligence Austin, Texas, USA, January 4 2015, pp4292–4293
[33] Blagus N, Šubelj L, Bajec M 2012 Physica A 391 2794
Google Scholar
[34] Newman M E J 2006 Phys. Rev. E 74 036104
Google Scholar
[35] Batagelj V, Mrvar A 1998 Connections 21 47
[36] Isella L, Stehlé J, Barrat A, Cattuto C, Pinton J F 2011 J. Theor. Biol. 271 166
Google Scholar
[37] Lin J H, Guo Q, Dong W Z, Tang L Y, Liu J G 2014 Phys. Lett. A 378 3279
Google Scholar
-
图 1 十种不同排序方法得到的排序结果与SIR传播过程感染节点数的相关性 (a) Enron; (b) Facebook; (c) Netscience; (d) Infectious; (e) USAir; (f) EPA
Fig. 1. The correlation between the ranking results obtained by ten different ranking methods and the number of infected nodes in the SIR propagation process: (a) Enron; (b) Facebook; (c) Netscience; (d) Infectious; (e) USAir; (f) EPA.
图 2 6个真实网络数据集上十种不同排序方法排序准确性对比 (a) Enron; (b) Facebook; (c) Netscience; (d) Infectious; (e) USAir; (f) EPA
Fig. 2. Comparison of sorting accuracy of ten different sorting methods on six real network datasets: (a) Enron; (b) Facebook; (c) Netscience; (d) Infectious; (e) USAir; (f) EPA.
图 3 不同比例节点下十种评估算法的Kendall相关系数对比 (a) Enron; (b) Facebook; (c) Netscience; (d) Infectious; (e) USAir; (f) EPA
Fig. 3. Comparison of Kendall correlation coefficients of ten node influence evaluation algorithms under different scale nodes: (a) Enron; (b) Facebook; (c) Netscience; (d) Infectious; (e) USAir; (f) EPA.
图 4 LFR模拟数据集上十种评估算法的Kendall相关系数对比, 黑色虚线为三个网络的传播阈值βth
(a) $\langle k\rangle $ = 5, βth = 0.0984; (b)$\langle k\rangle $ = 10, βth = 0.0723; (c)$\langle k\rangle $ = 15, βth = 0.0577Fig. 4. Comparison of Kendall correlation coefficients of ten evaluation algorithms on the LFR simulation dataset, the black dashed line is the propagation threshold βth of three different network: (a)
$\langle k\rangle $ = 5, βth = 0.0984; (b)$\langle k\rangle $ = 10, βth = 0.0723; (c)$\langle k\rangle $ = 15, βth = 0.0577.
图 5 当β变化时, 不同θ值所对应的ISM+方法生成的节点重要性排序序列与SIR传播扩散过程生成的节点传播影响力排序序列之间的平均Kendall
$\langle \tau \rangle $ 值 (a) Enron; (b) Facebook; (c) Netscience; (d) Infectious; (e) USAir; (f) EPA; (g) LFR_k5; (h) LFR_k10; (i) LFR_k15Fig. 5. The average Kendall’s
$\langle \tau \rangle $ obtained by comparing the ranking list generated by SIR spreading process and the ranking list generated by the ISM+ methods with different θ when the β changes: (a) Enron; (b) Facebook; (c) Netscience; (d) Infectious; (e) USAir; (f) EPA; (g) LFR_k5; (h) LFR_k10; (i) LFR_k15.表 1 6个真实网络的拓扑统计参数
Table 1. Topological parameters of six real networks.
网络名 N E $ \langle d \rangle $ ${\beta _{{\text{th}}}}$ $\beta $ $ \langle k \rangle $ C D $ k{s_{\max }} $ Enron 143 623 2.9670 0.0774 0.08 8.7133 0.4339 8 9 Facebook 324 2218 3.0537 0.0466 0.05 13.6914 0.4658 7 18 Netscience 379 914 6.0419 0.1250 0.13 4.8232 0.7410 17 8 USAir 453 2025 2.7381 0.0231 0.03 12.8072 0.6252 6 26 Infectious 410 2765 3.6309 0.0534 0.05 13.4878 0.4558 9 17 Web_EPA 4253 6258 4.5003 0.0366 0.08 4.1839 0.0714 10 6 
下载: 导出CSV
-
[1] Lü L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1
Google Scholar
[2] Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200
Google Scholar
[3] Albert R, Barabási A L 2002 Rev. Modern Phys. 74 47
Google Scholar
[4] Alshahrani M, Fuxi Z, Sameh A, Mekouar S, Huang S 2020 Inform. Sciences 527 88
Google Scholar
[5] Albert R, Jeong H, Barabási A L 1999 Nature 401 130
Google Scholar
[6] Chen D B, Lu L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777
Google Scholar
[7] Sabidussi G 1966 Psychometrika 31 581
Google Scholar
[8] Freeman L C 1977 Sociometry 40 35
Google Scholar
[9] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[10] Lü L Y, Zhou T, Zhang Q M, Stanley H E 2016 Nat. Commun. 7 10168
Google Scholar
[11] Bae J, Kim S 2014 Physica A 395 549
Google Scholar
[12] Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031
Google Scholar
[13] Zareie A, Sheikhahmadi A, Khamforoosh K 2018 Expert Syst. Appl. 108 96
Google Scholar
[14] Fei L, Lu J, Feng Y 2020 Comput. Ind. Eng. 142 106355
Google Scholar
[15] 韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰 2015 物理学报 64 058902
Google Scholar
Hang Z M, Wu Y, Tan X S, Duan D G, Yang W J 2015 Acta Phys. Sin. 64 058902
Google Scholar
[16] Wang Z X, Du C J, Fan J P, X Y 2017 Neurocomputing 260 466
Google Scholar
[17] 闫光辉, 张萌, 罗浩, 李世魁, 刘婷 2019 通信学报 40 109
Google Scholar
Yan G H, Zhang M, Luo H, Li S K, Liu T 2019 J. Communications 40 109
Google Scholar
[18] Alon U 2007 Nat. Rev. Genet. 8 450
Google Scholar
[19] Benson A R, Gleich D F, Leskovec J 2016 Science 353 163
Google Scholar
[20] Li Y, Deng Y 2018 Int. J. Comput. Commun. Control 13 792
Google Scholar
[21] Wang J, Qiao K Y, Zhang Z Y 2019 Future Gener. Comp. Sy. 91 1
Google Scholar
[22] Morone F, Makse H A 2015 Nature 527 544
[23] Zhong L F, Liu Q H, Wang W, Cai S M 2018 Physica A 511 78
Google Scholar
[24] Ma L L, Ma C, Zhang H F, Wang B H 2016 Physica A 451 205
Google Scholar
[25] Li Z, Ren T, Ma X Q, Liu S M, Zhang Y X, Zhou T 2019 Sci. Rep. 9 1
Google Scholar
[26] Yang X, Xiao F Y 2021 Knowl-Based Syst. 227 107198
Google Scholar
[27] Burt R S 2004 American J. Sociology 110 349
Google Scholar
[28] Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602
[29] Newman M E J 2002 Phys. Rev. E 66 016128
Google Scholar
[30] Kendall M G 1945 Biometrika 33 239
Google Scholar
[31] Knight W R 1966 J. Amer. Statist. Assoc. 61 436
Google Scholar
[32] Rossi R, Ahmed N 2015 Twenty-ninth AAAI Conference on Artificial Intelligence Austin, Texas, USA, January 4 2015, pp4292–4293
[33] Blagus N, Šubelj L, Bajec M 2012 Physica A 391 2794
Google Scholar
[34] Newman M E J 2006 Phys. Rev. E 74 036104
Google Scholar
[35] Batagelj V, Mrvar A 1998 Connections 21 47
[36] Isella L, Stehlé J, Barrat A, Cattuto C, Pinton J F 2011 J. Theor. Biol. 271 166
Google Scholar
[37] Lin J H, Guo Q, Dong W Z, Tang L Y, Liu J G 2014 Phys. Lett. A 378 3279
Google Scholar
下载:
计量
- 文章访问数: 6430
- PDF下载量: 197
- 被引次数: 0
