On the influence of topological characteristics on robustness of complex networks

• Autorzy: Kasthurirathna D. , Piraveenan M. , Thedchanamoorthy G.

Identyfikatory

DOI

10.2478/jaiscr-2014-0007

• Języki publikacji: EN

Abstrakty

EN

In this paper, we explore the relationship between the topological characteristics of a complex network and its robustness to sustained targeted attacks. Using synthesised scale-free, small-world and random networks, we look at a number of network measures, including assortativity, modularity, average path length, clustering coefficient, rich club profiles and scale-free exponent (where applicable) of a network, and how each of these influence the robustness of a network under targeted attacks. We use an established robustness coefficient to measure topological robustness, and consider sustained targeted attacks by order of node degree. With respect to scale-free networks, we show that assortativity, modularity and average path length have a positive correlation with network robustness, whereas clustering coefficient has a negative correlation. We did not find any correlation between scale-free exponent and robustness, or rich-club profiles and robustness. The robustness of small-world networks on the other hand, show substantial positive correlations with assortativity, modularity, clustering coefficient and average path length. In comparison, the robustness of Erdos-Renyi random networks did not have any significant correlation with any of the network properties considered. A significant observation is that high clustering decreases topological robustness in scale-free networks, yet it increases topological robustness in small-world networks. Our results highlight the importance of topological characteristics in influencing network robustness, and illustrate design strategies network designers can use to increase the robustness of scale-free and small-world networks under sustained targeted attacks.

Słowa kluczowe

EN

topological characteristics; complex network; random networks; robustness

• Wydawca: University of Social Sciences
• Czasopismo: Journal of Artificial Intelligence and Soft Computing Research
• Rocznik: 2013
• Tom: Vol. 3, No. 2
• Strony: 89--100
• Opis fizyczny: Bibliogr. 34 poz., rys.

Twórcy

autor

Kasthurirathna D.

• Centre for Complex Systems Research Faculty of Engineering and IT The University of Sydney, NSW 2006, Australia

autor

Piraveenan M.

• Centre for Complex Systems Research Faculty of Engineering and IT The University of Sydney, NSW 2006, Australia

autor

Thedchanamoorthy G.

• Centre for Complex Systems Research Faculty of Engineering and IT The University of Sydney, NSW 2006, Australia

Bibliografia

• [1] R. Albert and A.-L. Barab´asi, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 74, pp. 47–97, 2002.
• [2] U. Alon, Introduction to Systems Biology: Design Principles of Biological Circuits. London: Chapman and Hall, 2007.
• [3] S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet andWWW. Oxford: Oxford University Press, January 2003.
• [4] F. Kepes (Ed), Biological Networks. Singapore:World Scientific, 2007.
• [5] J. Park and M. E. J. Newman, “Statistical mechanics of networks,” Physical Review E, vol. 70, no. 6, pp. 066 117+, Dec 2004. [Online]. Available: http://dx.doi.org/10.1103/PhysRevE.70.066117
• [6] M. Piraveenan, M. Prokopenko, and A. Y. Zomaya, “Assortative mixing in directed biological networks,” IEEE/ACM Transactions on computational biology and bioinformatics, vol. 9(1), pp. 66–78, 2012.
• [7] M. Piraveenan, M. Prokopenko, and L. Hossain, “Percolation centrality: Quantifying graphtheoretic impact of nodes during percolation in networks,” PloS one, vol. 8, no. 1, p. e53095, 2013.
• [8] M. Piraveenan, M. Prokopenko, and A. Zomaya, “On congruity of nodes and assortative information content in complex networks,” Networks and Heterogeneous Media (NHM), vol. 3, no.10.3934/nhm.2012.7.441, pp. 441–461, 2012.
• [9] R. V. Sol´e and S. Valverde, “Information theory of complex networks: on evolution and architectural constraints,” in Complex Networks, ser. Lecture Notes in Physics, E. Ben-Naim, H. Frauenfelder, and Z. Toroczkai, Eds. Springer, 2004, vol. 650.
• [10] R. Albert, H. Jeong, and A.-L. Barab´asi, “Error and attack tolerance of complex networks,” Nature, vol. 406, pp. 378–382, 2000.
• [11] A.-L. Barab´asi, “Scale-free networks: A decade and beyond,” Science, vol. 325, no. 5939, pp. 412–413, 2009.
• [12] A.-L. Barab´asi, R. Albert, and H. Jeong, “Scalefree characteristics of random networks: The topology of the world-wide web,” Physica A, vol. 281, pp. 69–77, 2000.
• [13] A.-L. Barab´asi and E. Bonabeau, “Scale-free networks,”Scientific American, vol. 288, pp. 50–59, 2003.
• [14] A. Cavagna, A. Cimarelli, I. Giardina, G. Parisi, R. Santagati, F. Stefanini, and M. Viale, “Scale-free correlations in bird flocks,” 2009, arXiv:0911.4393. [Online]. Available:http://arxiv.org/abs/0911.4393100 D. Kasthurirathna, G. Thedchanamoorthy
• [15] M. Mitchell, “Complex systems: Network thinking,” Artificial Intelligence, vol. 170, no. 18, pp. 1194–1212, 2006.
• [16] D. J. Watts and S. H. Strogatz, “Collective dynamics of ’small-world’ networks,” Nature, vol. 393,pp. 440–442, 1998.
• [17] A. Jamakovic and S. Uhlig, “Influence of the networkstructure on robustness,” in Networks, 2007.ICON 2007. 15th IEEE International Conference on. IEEE, 2007, pp. 278–283.
• [18] M. E. J. Newman, “Mixing patterns in networks,” Physical Review E, vol. 67, no. 2, p. 026126, 2003.
• [19] M. Piraveenan, M. Prokopenko, and A. Y. Zomaya, “Local assortativeness in scale-free networks,” Europhysics Letters, vol. 84, no. 2, p. 28002, 2008.
• [20] ——, “Local assortativeness in scale-free networks addendum,” Europhysics Letters, vol. 89, no. 4, p. 49901, 2010.
• [21] V. Latora and M. Marchiori, “Efficient behavior of small-world networks,” Physical Review Letters, vol. 87, no. 19, p. 198701, 2001.
• [22] M. E. J. Newman, “Models of the small world,” Journal of Statistical Physics, vol. 101, no. 3, pp. 819–841, November 2000. [Online]. Available:http://dx.doi.org/10.1023/A:1026485807148
• [23] D. J. Watts and S. H. Strogatz, “Collective dynamics of small-world networks,” Nature, vol.393, no. 6684, pp. 440–442, June 1998. [Online].Available: http://dx.doi.org/10.1038/30918
• [24] R. Albert, H. Jeong, and A.-L. Barab´asi, “Error and attack tolerance of complex networks,” Nature, vol. 406, no. 6794, pp. 378–382, 2000.
• [25] P. Crucittia, V. Latora, M. Marchiori, and A. Rapisarda, “Error and attack tolerance of complex networks,” Physica A, vol. 340, p. 388394, 2004.
• [26] A. H. Dekker and B. D. Colbert, “Network robustness and graph topology,” in Proceedings of the 27th Australasian conference on Computer science - Volume 26, ser. ACSC ’04. Darlinghurst, Australia, Australia: Australian Computer Society, Inc., 2004, pp. 359–368.
• [27] M. Piraveenan, G. Thedchanamoorthy, S. Uddin, and K. S. K. Chung, “Quantifying topological robustness of networks under sustained targeted attacks,” Social Network Analysis and Mining, 2013.[Online]. Available: 10.1007/s13278-013-0118-8
• [28] J. A. Hanley and B. J. Mcneil, “The meaning and use of the area under a receiver operating characteristic (ROC) curve.” Radiology, vol. 143, no. 1, pp. 29–36, Apr. 1982.
• [29] E. Kreyszig, Advanced Engineering Mathematics, 9th Edition. John Wiley, December 2005.
• [30] M. E. J. Newman, “Assortative mixing in networks,” Physical Review Letters, vol. 89, no. 20, p. 208701, 2002.
• [31] M. Piraveenan, S. Uddin, and K. S. K. Chung, “Measuring topological robustness of networks under sustained targeted attacks,” in 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. New York: IEEE Computer Society, 2012.
• [32] S. Sarkar and A. Dong, “Characterizing modularity, hierarchy and module interfacing in complex design systems,” in ASME 2011 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference (IDETC/CIE2011), vol. 9: 23rd International Conference on Design Theory and Methodology; 16th Design for Manufacturing and the Life Cycle Conference. New York: ASME, 2011, pp. 375–384.
• [33] J. T. Lizier, M. Piraveenan, D. Pradhana, M. Prokopenko, and L. S. Yaeger, “Functional and structural topologies in evolved neural networks,” in Advances in Artificial Life: Tenth European Conference on Artificial Life (ECAL ’09), ser. LNCS/LNAI. Springer, 2009, vol. 5777-5778.
• [34] S. Milgram, “The small world problem,” Psychology Today, vol. 1, p. 61, 1967