A Preliminary Study on Effects of Community Structures on Epidemic Spreading and Detection in Complex Networks
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.
[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.
[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.
@article{"International Journal of Electrical, Electronic and Communication Sciences:65502", author = "Yi Yu and Gaoxi Xiao", title = "A Preliminary Study on Effects of Community Structures on Epidemic Spreading and Detection in Complex Networks ", 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. ", volume = "7", number = "10", pages = "1367-5", }
