A Preliminary Study on Effects of Community Structures on Epidemic Spreading and Detection in Complex Networks

Authors: Yi Yu, Gaoxi Xiao

Abstract:

Community structures widely exist in almost all real-life networks. Extensive researches have been carried out on detecting community structures in complex networks. However, many aspects of how community structures may affect the dynamics and properties of complex networks still remain unclear. In this work, we examine the impacts of community structures on the epidemic spreading and detection in complex networks. Extensive simulation results show that community structures may not help decrease the infection size at steady state, yet they could indeed help slow down the infection spreading. Also, networks with strong community structures may expect to have a smaller average infection size when equipped with a number of sparsely deployed monitors.

Keywords: Complex network, epidemic spreading, infection size, infection monitoring.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1088564

References:

[1] C. Qian, C. Hyunseok, R. Govindan, and S. Jamin, "The origin of power laws in Internet topologies revisited," Proc. IEEE Infocom, vol. 2 pp. 608-617, 2002.
[2] J. Leskovec, J. Kleinberg, and C. Faloutsos, "Graphs over time: densification laws, shrinking diameters and possible explanations," Proc. ACM SIGKDD, 2005.
[3] F. Liljeros, C. R. Edling, L. A. Amaral, H. E. Stanley, and Y. Aberg, "The web of human sexual contacts," Nature, vol. 411, pp. 907-908, 2001.
[4] A.-L. Barabási, R. Albert, and H. Jeong, "Scale-free characteristics of random networks: the topology of the world-wide web," Physica A, vol. 281, pp. 69-77, 2000.
[5] A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, pp. 509-512, October 15, 1999.
[6] R. Cohen, K. Erez, D. ben-Avraham and S. Havlin, "Resilience of the Internet to random breakdowns". Phys. Rev. Lett., vol. 85, pp. 4626–4628, 2000.
[7] R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, "Breakdown of the Internet under intentional attack". Phys. Rev. Lett. vol. 86, pp. 3682–3685, 2001.
[8] S. Xiao, G. Xiao, and T. H. Cheng, "Tolerance of intentional attacks in complex communications networks," IEEE Communications Magazine, vol. 46, no. 1, pp. 146-152, Jan. 2008.
[9] R. Pastor-Satorras and A. Vespignani, "Epidemic spreading in scale-Free networks," Physical Review Letters, vol. 86, pp. 3200-3203, 2001.
[10] R. Pastor-Satorras and A. Vespignani, "Immunization of complex networks," Physical Review E, vol. 65, p. 036104, 2002.
[11] Y. Wang, G. Xiao, J. Hu, T. H. Cheng, and L. Wang, "Imperfect targeted immunization in scale-free networks," Physica A, vol. 388, no. 12, pp. 2535-46, 2009.
[12] M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks," Physical Review E, vol. 69, p. 026113, 2004.
[13] M. E. J. Newman, "Detecting community structure in networks," European Physical Journal B, vol. 38, pp. 321-330, 2004/03/01 2004.
[14] M. E. J. Newman, "Fast algorithm for detecting community structure in networks," Physical Review E, vol. 69, p. 066133, 2004.
[15] J. Zhou, G. Xiao, L. Wong, X. Fu, S. Ma, and T. H. Cheng, "Generation of arbitrary two-point correlated directed networks with given modularity," Physics Letters A, vol. 374, pp. 3129-3135, 2010.
[16] M. J. Barber, "Modularity and community detection in bipartite networks," Physical Review E, vol. 76, p. 066102, 2007.
[17] G. Palla, I. Derenyi, I. Farkas, and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society," Nature, vol. 435, pp. 814-818, 2005.
[18] E. A. Leicht and M. E. J. Newman, "Community structure in directed networks," Physical Review Letters, vol. 100, p. 118703, 2008.
[19] Z. Liu and H. Bambi, "Epidemic spreading in community networks," EPL, vol. 72, p. 315, 2005.
[20] W. Huang and C. Li, "Epidemic spreading in scale-free networks with community structure," Journal of Statistical Mechanics, vol. 2007, p. P01014, 2007.
[21] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, "Cost-effective outbreak detection in networks," Proc. ACM SIGKDD, 2007.
[22] R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, and U. Alon, "On the uniform generation of random graphs with prescribed degree sequences," arXiv:cond-mat/0312028v2, 2004.
[23] N. T. J., Bailey The mathematical theory of infectious diseases and its applications, volume 66, London, UK: Griffin, 1975.