ArticleNo Access

THE RESILIENCE OF COMPLEX NETWORK: AN APPROACH FOR RELEVANT NODES EXTRACTION

Unidad Profesional Interdisciplinaria de Ingeniería y Ciencias Sociales, y Administrativas, Instituto Politécnico Nacional, Ciudad de México 0840, México

E-mail Address: aldo_ramirez26@hotmail.com

Corresponding author.

Search for more papers by this author

and

JUAN BORY-REYES

SEPI-ESIME-Zacatenco, Instituto Politécnico Nacional, Ciudad de México 07738, México

E-mail Address: juanboryreyes@yahoo.com

Search for more papers by this author

https://doi.org/10.1142/S0218348X21500092Cited by:6 (Source: Crossref)

Abstract

In this paper, a new algorithm to select the relevant nodes — those that maintain the cohesion of the network — of the complex network is presented. The experiments on most of the real complex networks show that the proposed approach outperforms centrality measures as node degree, PageRank algorithm and betweenness centrality. The rationale of the algorithm for extracting relevant nodes is to discover the self-similarity of the network. As seen in the algorithm, throughout the extraction sequence of relevant nodes, differences are advised with node degree, PageRank algorithm and betweenness centrality. Finally, empirical evidence is considered to show that complex network robustness is a nonlinear function of the small-worldness measure.

Keywords:

References

1. A.-L. Barabási and R. Albert , Emergence of scaling in random networks, Science 286(5439) (1999) 509–512. Web of Science, Google Scholar
2. S. Johnson et al., Entropic origin of disassortativity in complex networks, Phys. Rev. Lett. 104(10) (2010) 108702. Web of Science, Google Scholar
3. M. E. J. Newman , Mixing patterns in networks, Phys. Rev. E 67(2) (2003) 026126. Web of Science, Google Scholar
4. D. J. Watts and S. H. Strogatz , Collective dynamics of “small-world” networks, Nature 393 (1998) 440. Web of Science, Google Scholar
5. M. E. Newman, C. Moore and D. J. Watts , Mean-field solution of the small-world network model, Phys. Rev. Lett. 84(14) (2000) 3201. Web of Science, Google Scholar
6. E. Estrada , The Structure of Complex Networks: Theory and Applications (OUP Oxford, United States, 2011). Google Scholar
7. Y. Wu et al., On the correlation between fractal dimension and robustness of complex networks, Fractals 27(4) (2019) 1950067. Link, Web of Science, Google Scholar
8. S. Pei, F. Morone and H. A. Makse , Theories for Influencer Identification in Complex Networks, in Complex Spreading Phenomena in Social Systems: Influence and Contagion in Real-World Social Networks, S. Lehmann and Y.-Y. Ahn , eds. (Springer International Publishing: Cham, 2018), pp. 125–148. Google Scholar
9. R. Albert, H. Jeong and A.-L. Barabási , Error and attack tolerance of complex networks, Nature 406 (2000) 378. Web of Science, Google Scholar
10. D. S. Callaway et al., Network robustness and fragility: Percolation on random graphs, Phys. Rev. Lett. 85(25) (2000) 5468–5471. Web of Science, Google Scholar
11. R. Cohen et al., Resilience of the internet to random breakdowns, Phys. Rev. Lett. 85(21) (2000) 4626–4628. Web of Science, Google Scholar
12. P. Holme et al., Attack vulnerability of complex networks: Statistical, nonlinear, and soft matter physics, Phys. Rev. E 65 5 Pt 2 (2002) 056109. Web of Science, Google Scholar
13. R. Cohen et al., Breakdown of the internet under intentional attack, Phys. Rev. Lett. 86(16) (2001) 3682–3685. Web of Science, Google Scholar
14. L. K. Gallos et al., Stability and topology of scale-free networks under attack and defense strategies, Phys. Rev. Lett. 94(18) (2005) 188701. Web of Science, Google Scholar
15. G. Dong et al., Robustness of network of networks under targeted attack, Phys. Rev. E 87(5) (2013) 052804. Web of Science, Google Scholar
16. A. Srivastava et al., Correlations in complex networks under attack, Phys. Rev. E 86(3) (2012) 036106. Web of Science, Google Scholar
17. B. Mirzasoleiman et al., Cascaded failures in weighted networks, Phys. Rev. E 84(4) (2011) 046114. Web of Science, Google Scholar
18. S. Iyer et al., Attack robustness and centrality of complex networks, PLoS One 8(4) (2013) e59613. Web of Science, Google Scholar
19. T. Wen, M. Song and W. Jiang , Evaluating topological vulnerability based on fuzzy fractal dimension, Int. J. Fuzzy Syst. 20(6) (2018) 1956–1967. Web of Science, Google Scholar
20. L. Gou et al., Topological vulnerability evaluation model based on fractal dimension of complex networks, PLoS One 11(1) (2016) e0146896. Web of Science, Google Scholar
21. F. Kawasaki and K. Yakubo , Reciprocal relation between the fractal and the small-world properties of complex networks, Phys. Rev. E 82(3) (2010), p. 036113. Web of Science, Google Scholar
22. D. Li, X. Wang and P. Huang , A fractal growth model: Exploring the connection pattern of hubs in complex networks, Phys. A, Stat. Mech. Appl. 471 (2017) 200–211. Web of Science, Google Scholar
23. R. Cohen and S. Havlin , Scale-free networks are ultrasmall, Phys. Rev. Lett. 90(5) (2003) 058701. Web of Science, Google Scholar
24. M. A. Latif, M. Naveed and F. Zaidi , Resilience of Social Networks Under Different Attack Strategies (Springer International Publishing, Cham, 2013). Google Scholar
25. H. Sawai , A small-world network immune from random failures and resilient to targeted attacks, Procedia Comput. Sci. 18 (2013) 976–985. Google Scholar
26. G.-S. Peng et al., Trade-offs between robustness and small-world effect in complex networks, Sci. Rep. 6(1) (2016) 37317. Web of Science, Google Scholar
27. J. Kim and T. Wilhelm , What is a complex graph?, Phys. A, Stat. Mech. Appl. 387(11) (2008) 2637–2652. Web of Science, Google Scholar
28. M. D. Humphries and K. Gurney , Network “small-world-ness”: A quantitative method for determining canonical network equivalence, PLoS One 3(4) (2008) e0002051. Web of Science, Google Scholar
29. B. B. Mandelbrot , The Fractal Geometry of Nature (Freeman, San Francisco, 1982). Google Scholar
30. E. Rosenberg , A Survey of Fractal Dimensions of Networks, Springer Briefs in Computer Science (Springer International Publishing, USA, 2018). Google Scholar
31. C. Song, S. Havlin and H. A. Makse , Origins of fractality in the growth of complex networks, Nat. Phys. 2 (2006) 275. Web of Science, Google Scholar
32. L. K. Gallos, C. Song and H. A. Makse , A review of fractality and self-similarity in complex networks, Phys. A, Stat. Mech. Appl. 386(2) (2007) 686–691. Web of Science, Google Scholar
33. N. J. Evans et al., Refining the law of practice, Psychol. Rev. 125(4) (2018) 592–605. Web of Science, Google Scholar
34. H. D. Rozenfeld et al., Fractal and transfractal scale-free networks, in Encyclopedia of Complexity and Systems Science, R. A. Meyers ed. (Springer, New York, 2009), pp. 3924–3943. Google Scholar
35. S. Chaoming et al., How to calculate the fractal dimension of a complex network: The box covering algorithm, J. Stat. Mech. Theory Exp. 2007(3) (2007) P03006. Web of Science, Google Scholar
36. X. Pan and H. Wang , Resilience of and recovery strategies for weighted networks, PLoS One 13(9) (2018) e0203894. Web of Science, Google Scholar
37. M. Kitsak et al., Betweenness centrality of fractal and nonfractal scale-free model networks and tests on real networks, Phys. Rev. E 75(5) (2007) 056115. Web of Science, Google Scholar
38. T. Bian and Y. Deng , Identifying influential nodes in complex networks: A node information dimension approach, Chaos 28(4) (2018) 043109. Web of Science, Google Scholar
39. İ. Tuğal and A. Karcı , Comparisons of Karcıand Shannon entropies and their effects on centrality of social networks, Phys. A, Stat. Mech. Appl. 523 (2019) 352–363. Web of Science, Google Scholar
40. L. Jiang et al., Identifying node importance in a complex network based on node bridging feature, Appl. Sci. 8 (2018) 1914. Google Scholar
41. J. Liu et al., Evaluating the importance of nodes in complex networks, Phys. A, Stat. Mech. Appl. 452 (2016) 209–219. Web of Science, Google Scholar
42. F. D. Malliaros, M.-E. G. Rossi and M. Vazirgiannis , Locating influential nodes in complex networks, Sci. Rep. 6(1) (2016) 19307. Web of Science, Google Scholar
43. X. Zhang et al., Extracting the globally and locally adaptive backbone of complex networks, PLoS One 9(6) (2014) e100428. Web of Science, Google Scholar
44. S. P. Borgatti , Identifying sets of key players in a social network, Comput. Math. Org. Theory 12(1) (2006) 21–34. Google Scholar
45. Y. Chen et al., Percolation theory applied to measures of fragmentation in social networks, Phys. Rev. E 75(4) (2007) 046107. Web of Science, Google Scholar
46. E. Rosenberg , Maximal entropy coverings and the information dimension of a complex network, Phys. Lett. A 381(6) (2017) 574–580. Web of Science, Google Scholar
47. H. Akaike , A new look at the statistical model identification, IEEE Trans. Autom. Control 19(6) (1974) 716–723. Web of Science, Google Scholar
48. A. Ramirez-Arellano et al., D-summable fractal dimensions of complex networks, Chaos, Solitons Fractals 119 (2019) 210–214. Web of Science, Google Scholar
49. C. Song, S. Havlin and H. A. Makse , Self-similarity of complex networks, Nature 433 (2005) 392. Web of Science, Google Scholar