-
高效率的网络分析方法对于分析、预测和优化现实群体行为具有重要的作用, 而加权机制作为网络重构化的重要方式, 在生物、工程和社会等各个领域都有极高的应用价值. 虽然已经得到越来越多的关注, 但是现有加权方法数量还很少, 而且在不同拓扑类型和结构特性现实网络中的效果和性能有待继续提高. 本文提出了一种新型的双模式加权机制, 该方法充分利用网络的全局和局部的重要拓扑属性(例如节点度、介数中心性和紧密中心性), 并构建了两种新型的运行模式: 一种是在原始模式中通过增加桥边的权重来提高同步能力; 另一种是在逆模式中通过弱化桥边的权重来提高聚类检测. 此外, 该加权机制仅受单一参数
$ \alpha $ 的影响, 非常便于调控. 在人工基准网络和现实世界网络中的实验结果均验证了该模型的有效性, 可以广泛应用于大规模的现实世界网络中.For many real world systems ranging from biology to engineering, efficient network computation methods have attracted much attention in many applications. Generally, the performance of a network computation can be improved in two ways, i.e., rewiring and weighting. As a matter of fact, many real-world networks where an interpretation of efficient computation is relevant are weighted and directed. Thus, one can argue that nature might have assigned the optimal structure and weights to adjust the level of functionality. Indeed, in many neural and biochemical networks there is evidence that the synchronized and coordinated behavior may play important roles in the system’s functionality. The importance of the network weighting is not limited to the nature. In computer networks, for example, designing appropriate weights and directions for the connection links may enhance the ability of the network to synchronize the processes, thus leading the performance of computation to improve. In this paper, we propose a new two-mode weighting strategy by employing the network topological centralities including the degree, betweenness, closeness and communication neighbor graph. The weighting strategy consists of two modes, i.e., the original mode, in which the synchronizability is enhanced by increasing the weight of bridge edges, and the inverse version, in which the performance of community detection is improved by reducing the weight of bridge edges. We control the weight strategy by simply tuning a single parameter, which can be easily performed in the real world systems. We test the effectiveness of our model in a number of artificial benchmark networks as well as real-world networks. To the best of our knowledge, the proposed weighting strategy outperforms previously published weighting methods of improving the performance of network computation.-
Keywords:
- complex networks /
- weighting strategy /
- communication neighbor graph /
- community structure
[1] Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar
[2] Barabasi A L, Albert R 1999 Science 286 509Google Scholar
[3] Han Y, Zhu L, Cheng Z, Li J, Liu X 2020 IEEE Trans. Cybern. 50 1697Google Scholar
[4] 杨博, 刘大有, 刘继明, 金弟, 马海宾 2009 软件学报 20 54Google Scholar
Yang B, Liu D Y, Liu J M, Jin D, Ma H B 2009 J. Software 20 54Google Scholar
[5] Ding S, Yue Z, Yang S, Niu F, Zhang Y 2020 IEEE Trans. Ind. Inf. 32 2101Google Scholar
[6] Liang W, Li K, Long J, Kui X, Zomaya A Y 2020 IEEE Trans. Ind. Inf. 16 2063Google Scholar
[7] Lu M, Zhang Z, Qu Z, Kang Y 2019 IEEE Trans. Knowl. Data Eng. 31 1736Google Scholar
[8] Ma X, Dong D, Wang Q 2019 IEEE Trans. Knowl. Data Eng. 31 273Google Scholar
[9] Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113Google Scholar
[10] Clauset A, Newman M E J 2004 Phys. Rev. E 70 066111Google Scholar
[11] Du W B, Zhou X L, Lordan O, Wang Z, Zhao C, Zhu Y B 2016 Transp. Res. Pt. E-Logist. Transp. Rev. 89 108Google Scholar
[12] Zeng X, Wang W, Chen C, Yen G G 2020 IEEE Trans. Cybern. 50 2502Google Scholar
[13] Palla G, Derenyi I, Farkas I, Vicsek T 2005 Nature 435 814Google Scholar
[14] Li J, Wang X, Cui Y 2014 Physica A 415 398Google Scholar
[15] 李慧嘉, 李慧颖, 李爱华 2015 计算机学报 38 301Google Scholar
Li H J, Li H Y, Li A H 2015 Chin. J. Comput. 38 301Google Scholar
[16] Hofman J M, Wiggins C H 2008 Phys. Rev. Lett. 100 258701Google Scholar
[17] Boccaletti S, Ivanchenko M, LatoraV, Pluchino A 2007 Phys. Rev. E 75 045102Google Scholar
[18] Xu Y, Wu X, Li N, Liu L, Xie C, Li C 2019 IEEE Trans. Circuits Syst. Express Brief 67 700Google Scholar
[19] Han M, Zhang M, Qiu T, Xu M 2019 IEEE Trans. Neural Networks Learn. Syst. 30 255Google Scholar
[20] Hong H, Kim B J, Choi M Y, Park H 2004 Phys. Rev. E 69 067105Google Scholar
[21] Chavez M, Hwang D U, Amann A, Hentschel H E, Boccaletti S 2005 Phys. Rev. Lett. 94 218701Google Scholar
[22] Wang X, Lai Y C, Lai C H 2007 Phys. Rev. E 75 056205Google Scholar
[23] Jalili M, Rad A A, Hasler M 2008 Phys. Rev. E 78 016105Google Scholar
[24] Rad A A, Jalili M, Hasler M 2008 Chaos 18 037104Google Scholar
[25] Lu X, Kuzmin K, Chen M, Szymanski B K 2018 Inf. Sci. 424 55Google Scholar
[26] Zhang Y, Wang M, Gottwalt F, Saberi M, Chang E 2019 J. Informetr. 13 616Google Scholar
[27] De Meo P, Ferrara E, Fiumara G, Provetti A 2013 J. Informetr. 222 648Google Scholar
[28] Yang R, Wang W X, Lai Y C, Chen G 2009 Phys. Rev. E 79 026112Google Scholar
[29] Li H J, Daniels J J 2015 Phys. Rev. E 91 012801Google Scholar
[30] Meyniel F, Dehaene S 2017 PNAS 114 3859Google Scholar
[31] Khadivi A, Ajdari R A, Hasler M 2011 Phys. Rev. E 83 046104Google Scholar
[32] Fortunato S, Barthelemy M 2007 PNAS 104 36Google Scholar
[33] Good B H, de Montjoye Y A, Clauset A 2010 Phys. Rev. E 81 046106Google Scholar
[34] Newman M E J 2002 Comput. Phys. Commun. 147 40Google Scholar
[35] Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Phys. Rep. 424 175Google Scholar
[36] LuL Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1Google Scholar
[37] Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 PNAS 104 11150Google Scholar
[38] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888Google Scholar
[39] Motter A E, Zhou C, Kurths J 2005 Phys. Rev. E 71 016116Google Scholar
[40] Motter A E, Zhou C, Kurths J 2005 EPL 69 334Google Scholar
[41] Nishikawa T, Motter A E 2006 Phys. Rev. E 73 065106Google Scholar
[42] Gerschgorin S 1931 Izv. Akad. Nauk USSR Otd. Fiz.-Mat. Nauk 7 749
[43] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D 2004 PNAS 101 2658Google Scholar
[44] 李慧嘉, 严冠, 刘志东, 李桂君, 章祥荪 2017 中国科学: 数学 4 7241Google Scholar
Li H J, Yan G, Liu Z D, Li G J, Zhang X S 2017 Sci. Sin. Math 4 7241Google Scholar
[45] Li H J, Wang Y, Wu L Y, Zhang J, Zhang X S 2012 Phys. Rev. E 86 016109Google Scholar
[46] Li H J, Zhang X S 2013 EPL 103 58002Google Scholar
[47] Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110Google Scholar
[48] Guimera R, Nunes Amaral L A 2005 Nature 433 895Google Scholar
[49] Duch J, Arenas A 2005 Phys. Rev. E 72 027104Google Scholar
[50] Zachary W W 1977 J. Anthropol. Res. 33 452Google Scholar
[51] Knuth D E 1994 The Stanford Graph Base: A Platform for Combinatorial Computing (New York: ACM Press) p592
[52] Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M 2003 Behav. Ecol. Sociobiol. 54 396Google Scholar
[53] Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103Google Scholar
[54] Gleiser P, Danon L 2003 Adv. Complex Syst. 6 565Google Scholar
[55] Boguna M, Pastor-Satorras R, Diaz-Guilera A, Arenas A 2004 Phys. Rev. E 70 056122Google Scholar
[56] Agarwal G, Kempe D 2008 Eur. Phys. J. B 66 409Google Scholar
[57] Xing N, Zong Q, Dou L, Tian B, Wang Q 2019 IEEE Trans. Veh. Technol. 68 9963Google Scholar
[58] Yang H, Yao Q, Yu A, Lee Y, Zhang J 2019 IEEE Trans. Commun. 67 3457Google Scholar
-
图 4 (a) 无标度网络中
$ {\lambda }_{N}/{\lambda }_{2} $ 与($ \alpha $ ,$ \left\langle k \right\rangle $ )的对应关系(N = 500,$ \beta =0 $ ); (b)无标度网络中$ {\lambda }_{N}/{\lambda }_{2} $ 与($ \alpha $ ,$ \beta $ )的对应关系(N = 500,$ \left\langle k \right\rangle =4 $ )Fig. 4. (a) Corresponding relationship (N = 500,
$ \beta =0 $ ) in scale-free networks between$ {\lambda }_{N}/{\lambda }_{2} $ and ($ \alpha $ ,$ \left\langle k \right\rangle $ ); (b) Corresponding relationship (N = 500,$ \left\langle k \right\rangle =4 $ ) in scale-free networks between$ {\lambda }_{N}/{\lambda }_{2} $ and ($ \alpha $ ,$ \beta $ ).图 5 (a) Watts-Strogatz网络中
$ {\lambda }_{N}/{\lambda }_{2} $ 与($ \alpha $ ,$ \left\langle k \right\rangle $ )的对应关系(N = 500, P = 0.1); (b) Watts-Strogatz网络中$ {\lambda }_{N}/{\lambda }_{2} $ 与($ \alpha $ , P)的对应关系(N = 500,$ \left\langle k \right\rangle =4 $ )Fig. 5. (a) Corresponding relationship (N = 500, P = 0.1) in Watts-Strogatz networks between
$ {\lambda }_{N}/{\lambda }_{2} $ and ($ \alpha $ ,$ \left\langle k \right\rangle $ ); (b) corresponding relationship (N = 500,$ \left\langle k \right\rangle =4 $ ) in Watts-Strogatz networks between$ {\lambda }_{N}/{\lambda }_{2} $ and ($ \alpha $ , P).图 6 (a) GN基准网络中使用加权机制(逆加权机制)前后平均比率R的对比; (b) LFR基准网络中使用加权机制(逆加权机制)前后平均比率R的对比
Fig. 6. (a) Comparison of average ratio R before and after using weighting mechanism (inverse weighting mechanism) in GN benchmark network; (b) comparison of average ratio R before and after using weighting mechanism (inverse weighting mechanism) in LFR benchmark network.
表 1 在现实世界网络中使用8种不同加权策略的实验结果对比, 其中RW代表随机游走方法, SA代表模拟退火方法, VB代表变分贝叶斯方法, PL代表概率推断方法
Table 1. Comparison of experimental results using eight different weighting strategies in real world networks, in which RW represents random walk method, SA stands for simulated annealing method, VB stands for variational Bayesian method, PL stands for probability inference method.
现实世界网络 N $ \left\langle k \right\rangle $ $ {\lambda }_{N}/{\lambda }_{2} $ Chavez Wang Jalili Khadivi RW SA VB PL This work 蛋白质结构网络2 53 4.64 20.92 20.54 6.06 5.83 5.61 4.87 4.43 4.59 4.27 海豚网络 62 5.12 16.89 43.01 6.83 6.22 6.04 5.33 5.07 5.30 4.95 蛋白质结构网络1 95 4.48 63.1 262.2 23.5 19.82 15.71 13.65 10.59 11.88 8.45 蛋白质结构网络3 99 4.37 43.75 299.85 13.07 10.84 10.27 9.87 9.14 9.00 8.02 中国航空网络 203 18.48 13.25 5.79 3.29 2.88 2.23 2.08 1.83 1.76 1.55 电子邮件通讯 1133 9.62 8.63 5.81 5.40 4.04 3.86 3.91 3.84 3.54 3.77 酵母蛋白质交互作用 1458 2.67 52.44 269.07 25.60 17.63 15.61 13.21 10.76 12.66 9.52 蛋白质交互作用 2840 2.92 34.87 41.60 16.50 13.85 11.48 10.47 8.94 9.87 5.50 中国电力网络 865 5.20 49.77 133.8 25.43 20.90 23.44 15.19 12.04 10.56 5.04 科学家合作网络 4380 3.25 68.31 273.14 38.69 25.87 20.02 17.36 10.42 11.77 7.21 因特网AS2 7690 4.00 12.90 3.26 2.94 2.15 2.04 2.10 1.91 1.59 1.88 因特网AS5 8063 4.10 12.88 3.41 3.37 2.56 2.27 2.09 1.97 2.20 1.83 表 2 在不同现实网络使用加权策略得到的实验结果, 其中“/”左右表示加权后和加权前的模块度Q值
Table 2. Experimental results are obtained by using weighting strategy in different real networks, where /’s left or right represents the modularity Q value after or before weighting.
网络 文献 最优Q SA[48] DA[49] CNM[10] 中国航空网络 [11] — 0.644/0.525 0.589/0.428 0.577/0.483 空手道俱乐部 [50] 0.420 0.416/0.342 0.411/0.351 0.413/0.376 《悲惨世界》 [51] 0.561 0.554/0.389 0.539/0.406 0.531/0.395 海豚社会网络 [52] 0.531 0.527/0.375 0.521/0.362 0.517/0.356 电子邮件 [53] 0.579 0.568/0.462 0.543/0.436 0.538/0.444 爵士乐 [54] 0.446 0.439/0.333 0.437/0.341 0.431/0.328 PGP密钥签名 [55] 0.878 0.883/0.674 0.843/0.705 0.872/0.754 表 3 在现实世界网络中使用不同加权策略的实验结果对比, 这里网络聚类算法利用CNM算法, 其中RW代表随机游走方法, SA代表模拟退火方法, VB代表变分贝叶斯方法, PL代表概率推断方法
Table 3. Comparison of experimental results using different weighting strategies in the real world network. CNM algorithm is used as the network clustering algorithm, in which RW represents the random walk method, SA represents the simulated annealing method, VB represents the variable dB method, and PL represents the probability inference method.
网络 Chavez Wang Jalili Khadivi RW SA VB PL This work 空手道俱乐部 0.316 0.322 0.351 0.362 0.374 0.381 0.390 0.386 0.413 中国航空网络 0.449 0.478 0.423 0.432 0.506 0.543 0.564 0.578 0.603 《悲惨世界》 0.357 0.369 0.399 0.411 0.439 0.457 0.488 0.433 0.531 爵士乐 0.338 0.347 0.353 0.361 0.383 0.399 0.42 0.387 0.431 PGP密钥签名 0.583 0.678 0.676 0.715 0.744 0.786 0.839 0.820 0.872 海豚社会网络 0.357 0.381 0.371 0.374 0.406 0.444 0.483 0.500 0.517 电子邮件 0.368 0.409 0.431 0.443 0.471 0.499 0.503 0.495 0.538 -
[1] Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar
[2] Barabasi A L, Albert R 1999 Science 286 509Google Scholar
[3] Han Y, Zhu L, Cheng Z, Li J, Liu X 2020 IEEE Trans. Cybern. 50 1697Google Scholar
[4] 杨博, 刘大有, 刘继明, 金弟, 马海宾 2009 软件学报 20 54Google Scholar
Yang B, Liu D Y, Liu J M, Jin D, Ma H B 2009 J. Software 20 54Google Scholar
[5] Ding S, Yue Z, Yang S, Niu F, Zhang Y 2020 IEEE Trans. Ind. Inf. 32 2101Google Scholar
[6] Liang W, Li K, Long J, Kui X, Zomaya A Y 2020 IEEE Trans. Ind. Inf. 16 2063Google Scholar
[7] Lu M, Zhang Z, Qu Z, Kang Y 2019 IEEE Trans. Knowl. Data Eng. 31 1736Google Scholar
[8] Ma X, Dong D, Wang Q 2019 IEEE Trans. Knowl. Data Eng. 31 273Google Scholar
[9] Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113Google Scholar
[10] Clauset A, Newman M E J 2004 Phys. Rev. E 70 066111Google Scholar
[11] Du W B, Zhou X L, Lordan O, Wang Z, Zhao C, Zhu Y B 2016 Transp. Res. Pt. E-Logist. Transp. Rev. 89 108Google Scholar
[12] Zeng X, Wang W, Chen C, Yen G G 2020 IEEE Trans. Cybern. 50 2502Google Scholar
[13] Palla G, Derenyi I, Farkas I, Vicsek T 2005 Nature 435 814Google Scholar
[14] Li J, Wang X, Cui Y 2014 Physica A 415 398Google Scholar
[15] 李慧嘉, 李慧颖, 李爱华 2015 计算机学报 38 301Google Scholar
Li H J, Li H Y, Li A H 2015 Chin. J. Comput. 38 301Google Scholar
[16] Hofman J M, Wiggins C H 2008 Phys. Rev. Lett. 100 258701Google Scholar
[17] Boccaletti S, Ivanchenko M, LatoraV, Pluchino A 2007 Phys. Rev. E 75 045102Google Scholar
[18] Xu Y, Wu X, Li N, Liu L, Xie C, Li C 2019 IEEE Trans. Circuits Syst. Express Brief 67 700Google Scholar
[19] Han M, Zhang M, Qiu T, Xu M 2019 IEEE Trans. Neural Networks Learn. Syst. 30 255Google Scholar
[20] Hong H, Kim B J, Choi M Y, Park H 2004 Phys. Rev. E 69 067105Google Scholar
[21] Chavez M, Hwang D U, Amann A, Hentschel H E, Boccaletti S 2005 Phys. Rev. Lett. 94 218701Google Scholar
[22] Wang X, Lai Y C, Lai C H 2007 Phys. Rev. E 75 056205Google Scholar
[23] Jalili M, Rad A A, Hasler M 2008 Phys. Rev. E 78 016105Google Scholar
[24] Rad A A, Jalili M, Hasler M 2008 Chaos 18 037104Google Scholar
[25] Lu X, Kuzmin K, Chen M, Szymanski B K 2018 Inf. Sci. 424 55Google Scholar
[26] Zhang Y, Wang M, Gottwalt F, Saberi M, Chang E 2019 J. Informetr. 13 616Google Scholar
[27] De Meo P, Ferrara E, Fiumara G, Provetti A 2013 J. Informetr. 222 648Google Scholar
[28] Yang R, Wang W X, Lai Y C, Chen G 2009 Phys. Rev. E 79 026112Google Scholar
[29] Li H J, Daniels J J 2015 Phys. Rev. E 91 012801Google Scholar
[30] Meyniel F, Dehaene S 2017 PNAS 114 3859Google Scholar
[31] Khadivi A, Ajdari R A, Hasler M 2011 Phys. Rev. E 83 046104Google Scholar
[32] Fortunato S, Barthelemy M 2007 PNAS 104 36Google Scholar
[33] Good B H, de Montjoye Y A, Clauset A 2010 Phys. Rev. E 81 046106Google Scholar
[34] Newman M E J 2002 Comput. Phys. Commun. 147 40Google Scholar
[35] Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Phys. Rep. 424 175Google Scholar
[36] LuL Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1Google Scholar
[37] Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 PNAS 104 11150Google Scholar
[38] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888Google Scholar
[39] Motter A E, Zhou C, Kurths J 2005 Phys. Rev. E 71 016116Google Scholar
[40] Motter A E, Zhou C, Kurths J 2005 EPL 69 334Google Scholar
[41] Nishikawa T, Motter A E 2006 Phys. Rev. E 73 065106Google Scholar
[42] Gerschgorin S 1931 Izv. Akad. Nauk USSR Otd. Fiz.-Mat. Nauk 7 749
[43] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D 2004 PNAS 101 2658Google Scholar
[44] 李慧嘉, 严冠, 刘志东, 李桂君, 章祥荪 2017 中国科学: 数学 4 7241Google Scholar
Li H J, Yan G, Liu Z D, Li G J, Zhang X S 2017 Sci. Sin. Math 4 7241Google Scholar
[45] Li H J, Wang Y, Wu L Y, Zhang J, Zhang X S 2012 Phys. Rev. E 86 016109Google Scholar
[46] Li H J, Zhang X S 2013 EPL 103 58002Google Scholar
[47] Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110Google Scholar
[48] Guimera R, Nunes Amaral L A 2005 Nature 433 895Google Scholar
[49] Duch J, Arenas A 2005 Phys. Rev. E 72 027104Google Scholar
[50] Zachary W W 1977 J. Anthropol. Res. 33 452Google Scholar
[51] Knuth D E 1994 The Stanford Graph Base: A Platform for Combinatorial Computing (New York: ACM Press) p592
[52] Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M 2003 Behav. Ecol. Sociobiol. 54 396Google Scholar
[53] Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103Google Scholar
[54] Gleiser P, Danon L 2003 Adv. Complex Syst. 6 565Google Scholar
[55] Boguna M, Pastor-Satorras R, Diaz-Guilera A, Arenas A 2004 Phys. Rev. E 70 056122Google Scholar
[56] Agarwal G, Kempe D 2008 Eur. Phys. J. B 66 409Google Scholar
[57] Xing N, Zong Q, Dou L, Tian B, Wang Q 2019 IEEE Trans. Veh. Technol. 68 9963Google Scholar
[58] Yang H, Yao Q, Yu A, Lee Y, Zhang J 2019 IEEE Trans. Commun. 67 3457Google Scholar
计量
- 文章访问数: 4319
- PDF下载量: 54
- 被引次数: 0