-
Optimizing network structure to promote information propagation has been a key issue in the research field of complex network, and both clustering and diffusion characteristics of edges in a network play a very important role in information propagation. K-truss decomposition is an algorithm for identifying the most influential nodes in the network. We find that K-truss decomposition only considers edge clustering characteristics, without considering the diffusion characteristics, so it is easily affected by the local clustering structure in the network, such as core-like groups. There are mutually closely connected the core-like groups in the network, but the correlation between the core-like groups and the other parts of the network is less, so the information is easy to spread in the core-like groups, but not in the other parts of the network, nor over the whole network. For the reason, we propose an index to measure the edge diffusion characteristics in a network, and it is found that the diffusion characteristics of some edges in the periphery of the network are relatively high, but the clustering characteristics of these edges are relatively low, so they are not beneficial for rapid information propagation. In this paper, by considering the relationship between the clustering characteristics and diffusion characteristics of the edges, we propose a novel network structure optimization algorithm for information propagation. By measuring the comprehensive ability strength of the clustering characteristics and the diffusion characteristics of the edges, we can filter out the edges whose comprehensive ability is poor in the network, then determine whether the edges should be optimized according to the relative relationship between the clustering characteristics and the diffusion characteristics of the edges. To prove the effectiveness of the proposed algorithm, it is carried out to optimize the structures of four real networks, and verify the effective range of information propagation before and after the optimization of network structure from the classical independent cascade model. The results show that the network topology optimized by the proposed algorithm can effectively increase the range of information propagation. Moreover, the number of leaf nodes in the optimized network is reduced, and the clustering coefficient and the average path length are also reduced.
-
Keywords:
- clustering characteristics of edges /
- diffusion characteristics of edges /
- optimization of network structure /
- information propagation
[1] Barabasi A L, Albert R 1999 Science 286 509
[2] Watts D J, Strogatz S H 1998 Nature 393 409
[3] Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200
[4] Wu Z, Menichetti G, Rahmede C, Bianconi G 2015 Sci. Rep. 5 10073
[5] Serrano A B, Gómez-Gardeñes J, Andrade R F S 2017 Phys. Rev. E 95 052312
[6] Pastor-Satorras R, Vespignani A 2001 Phys. Rev. E 63 066117
[7] Coupechoux E, Lelarge M 2014 Adv. Appl. Probab. 46 985
[8] L L, Chen D B, Zhou T 2011 New J. Phys. 13 123005
[9] Sydney A, Scoglio C, Gruenbacher D 2013 Appl. Math. Comput. 219 5465
[10] Liu C, Zhang Z K 2014 Commun. Nonlinear Sci. 19 896
[11] Peng G S, Tan S Y, Wu J, Holme P 2016 Sci. Rep. 6 37317
[12] Zhang Z K, Liu C, Zhan X X, Xin L, Zhang C X, Zhang Y C 2016 Phys. Rep. 65 1
[13] Liu C, Zhan X X, Zhang Z K, Sun G Q, Hui P M 2015 New J. Phys. 17 113045
[14] Zhan X X, Liu C, Zhou G, Zhang Z, Sun G Q 2018 Appl. Math. Comput. 332 437
[15] Zhan X X, Liu C, Sun G Q, Zhang Z K 2018 Chaos Soliton. Fract. 108 196
[16] Grady D, Thiemann C, Brockmann D 2012 Nat. Commun. 3 864
[17] Yang C L, Tang K S 2011 Chin. Phys. B 20 128901
[18] L L, Chen D, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1
[19] Malliaros F D, Rossi M E G, Vazirgiannis M 2016 Sci. Rep. 6 19307
[20] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[21] Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602
[22] Liu Y, Tang M, Do Y, Hui P M 2017 Phys. Rev. E 96 022323
[23] Wang J, Cheng J 2012 Proc. VLDB Endow. 5 812
[24] Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M 2003 Behav. Ecol. Sociobiol. 54 396
[25] Newman M E J 2006 Proc. Natl. Acad. Sci. USA 103 8577
[26] Guimerà R, Danon L, Díaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103
[27] Goldenberg J, Libai B, Muller E 2001 Market. Lett. 12 211
[28] Chen W, Wang Y, Yang S 2009 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2009 p199
-
[1] Barabasi A L, Albert R 1999 Science 286 509
[2] Watts D J, Strogatz S H 1998 Nature 393 409
[3] Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200
[4] Wu Z, Menichetti G, Rahmede C, Bianconi G 2015 Sci. Rep. 5 10073
[5] Serrano A B, Gómez-Gardeñes J, Andrade R F S 2017 Phys. Rev. E 95 052312
[6] Pastor-Satorras R, Vespignani A 2001 Phys. Rev. E 63 066117
[7] Coupechoux E, Lelarge M 2014 Adv. Appl. Probab. 46 985
[8] L L, Chen D B, Zhou T 2011 New J. Phys. 13 123005
[9] Sydney A, Scoglio C, Gruenbacher D 2013 Appl. Math. Comput. 219 5465
[10] Liu C, Zhang Z K 2014 Commun. Nonlinear Sci. 19 896
[11] Peng G S, Tan S Y, Wu J, Holme P 2016 Sci. Rep. 6 37317
[12] Zhang Z K, Liu C, Zhan X X, Xin L, Zhang C X, Zhang Y C 2016 Phys. Rep. 65 1
[13] Liu C, Zhan X X, Zhang Z K, Sun G Q, Hui P M 2015 New J. Phys. 17 113045
[14] Zhan X X, Liu C, Zhou G, Zhang Z, Sun G Q 2018 Appl. Math. Comput. 332 437
[15] Zhan X X, Liu C, Sun G Q, Zhang Z K 2018 Chaos Soliton. Fract. 108 196
[16] Grady D, Thiemann C, Brockmann D 2012 Nat. Commun. 3 864
[17] Yang C L, Tang K S 2011 Chin. Phys. B 20 128901
[18] L L, Chen D, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1
[19] Malliaros F D, Rossi M E G, Vazirgiannis M 2016 Sci. Rep. 6 19307
[20] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[21] Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602
[22] Liu Y, Tang M, Do Y, Hui P M 2017 Phys. Rev. E 96 022323
[23] Wang J, Cheng J 2012 Proc. VLDB Endow. 5 812
[24] Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M 2003 Behav. Ecol. Sociobiol. 54 396
[25] Newman M E J 2006 Proc. Natl. Acad. Sci. USA 103 8577
[26] Guimerà R, Danon L, Díaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103
[27] Goldenberg J, Libai B, Muller E 2001 Market. Lett. 12 211
[28] Chen W, Wang Y, Yang S 2009 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2009 p199
Catalog
Metrics
- Abstract views: 4628
- PDF Downloads: 91
- Cited By: 0
下载:
