SpringerLink
Log in

Immunization of networks with non-overlap** community structure

  • Original Article
  • Published:
Social Network Analysis and Mining Aims and scope Submit manuscript

Abstract

Although community structure is ubiquitous in complex networks, few works exploit this topological property to control epidemics. In this work, devoted to networks with non-overlap** community structure (i.e., a node belongs to a single community), we propose and investigate three global immunization strategies. In order to characterize the influence of a node, various pieces of information are used such as the number of communities that the node can reach in one hop, the nature of the links (intra-community links, inter-community links), the size of the communities and the interconnection density between communities. Numerical simulations with the susceptible-infected-removed epidemiological model are conducted on both real-world and synthetic networks. Experimental results show that the proposed strategies are more effective than classical alternatives that are agnostic of the community structure. Additionally, they outperform alternative local and global strategies designed for modular networks.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Notes

  1. http://code.google.com/p/socialnetworksimulation/.

  2. http://www-personal.umich.edu/~mejn/netdata/.

  3. http://snap.stanford.edu/data/ca-GrQc.html.

References

  • Albert R, Barabási A-L (2002) Statistical mechanics of complex networks. Rev Mod Phys 74(1):47

    Article  MathSciNet  MATH  Google Scholar 

  • Barabási A-L, Bonabeau E (2003) Scale-free networks. Sci Am 288(5):60–69

    Article  Google Scholar 

  • Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech: Theory Exp 2008(10):10008

    Article  MATH  Google Scholar 

  • Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D-U (2006) Complex networks: structure and dynamics. Phys Rep 424(4–5):175–308

    Article  MathSciNet  MATH  Google Scholar 

  • Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The maximumclique problem. In: Du DZ, Pardalos PM (eds) Handbook of combinatorial optimization. Springer, Boston, pp 1–74

    Google Scholar 

  • Brandes U (2001) A faster algorithm for betweenness centrality. J Math Sociol 25(2):163–177

    Article  MATH  Google Scholar 

  • Chakraborty D, Singh A, Cherifi H (2016) Immunization strategies based on the overlap** nodes in networks with community structure. In: International conference on computational social networks, pp 62–73. Springer

  • Cohen R, Havlin S, Ben-Avraham D (2003) Efficient immunization strategies for computer networks and populations. Phys Rev Lett 91(24):247901

    Article  Google Scholar 

  • Danon L, Diaz-Guilera A, Duch J, Arenas A (2005) Comparing community structure identification. J Stat Mech: Theory Exp 2005(09):09008

    Article  MATH  Google Scholar 

  • Ferrara E (2012) Community structure discovery in facebook. Int J Soc Netw Min 1(1):67–90

    Article  Google Scholar 

  • Ferrara E, De Meo P, Fiumara G, Provetti A (2012) The role of strong and weak ties in facebook: a community structure perspective. Preprint at ar**v:1203.0535

  • Fortunato S (2010) Community detection in graphs. Phys Rep 486(3–5):75–174

    Article  MathSciNet  Google Scholar 

  • Fortunato S, Hric D (2016) Community detection in networks: a user guide. Phys Rep 659:1–44

    Article  MathSciNet  Google Scholar 

  • Ghalmane Z, El Hassouni M, Cherifi C, Cherifi H (2019) Centrality in modular networks. EPJ Data Sci 8(1):15

    Article  Google Scholar 

  • Ghalmane Z, El Hassouni M, Cherifi H (2018) Betweenness centrality for networks with non-overlap** community structure. In: 2018 IEEE workshop on complexity in engineering (COMPENG), pp 1–5. IEEE

  • Ghalmane Z, El Hassouni M, Cherifi C, Cherifi H (2018) k-truss decomposition for modular centrality. In: 2018 9th international symposium on signal, image, video and communications (ISIVC), pp 241–248. IEEE

  • Giabbanelli PJ, Peters JG (2011) Reseaux complexes et epidemies. TSI-Tech Sci Inf 30(2):181

    Google Scholar 

  • Gong K, Tang M, Hui PM, Zhang HF, Younghae D, Lai Y-C (2013) An efficient immunization strategy for community networks. PLoS ONE 8(12):83489

    Article  Google Scholar 

  • Gupta N, Singh A, Cherifi H (2016) Centrality measures for networks with community structure. Phys A 452:46–59

    Article  Google Scholar 

  • Gupta N, Singh A, Cherifi H (2015) Community-based immunization strategies for epidemic control. In: 2015 7th international conference on communication systems and networks (COMSNETS), pp 1–6. IEEE

  • Hébert-Dufresne L, Allard A, Young J-G, Dubé LJ (2013) Global efficiency of local immunization on complex networks. Sci Rep 3:2171

    Article  Google Scholar 

  • Hurley M, Jacobs G, Gilbert M (2006) The basic SI model. New Dir Teach Learn 2006(106):11–22

    Article  Google Scholar 

  • Jebabli M, Cherifi H, Cherifi C, Hammouda A (2014) Overlap** community structure in co-authorship networks: a case study. In: 2014 7th international conference on U-and e-service, science and technology (UNESST), pp 26–29. IEEE

  • Jebabli M, Cherifi H, Cherifi C, Hamouda A (2015) User and group networks on youtube: a comparative analysis. In: 2015 IEEE/ACS 12th international conference of computer systems and applications (AICCSA), pp 1–8. IEEE

  • Jeub LG, Balachandran P, Porter MA, Mucha PJ, Mahoney MW (2015) Think locally, act locally: detection of small, medium-sized, and large communities in large networks. Phys Rev E 91(1):012821

    Article  Google Scholar 

  • Kitromilidis M, Evans TS (2018) Community detection with metadata in a network of biographies of western art painters. ar**v preprint ar**v:1802.07985

  • Kumar M, Singh A, Cherifi H (2018) An efficient immunization strategy using overlap** nodes and its neighborhoods. In: Companion of the web conference 2018 on the web conference 2018, pp 1269–1275. International World Wide Web Conferences Steering Committee

  • Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110

    Article  Google Scholar 

  • Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data (TKDD) 1(1):2

    Article  Google Scholar 

  • Leskovec J, Lang KJ, Dasgupta A, Mahoney MW (2009) Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29–123

    Article  MathSciNet  MATH  Google Scholar 

  • Liu Z, Hu B (2005) Epidemic spreading in community networks. EPL (Europhys Lett) 72(2):315

    Article  Google Scholar 

  • Lü L, Chen D, Ren X-L, Zhang Q-M, Zhang Y-C, Zhou T (2016) Vital nodes identification in complex networks. Phys Rep 650:1–63

    Article  MathSciNet  Google Scholar 

  • Moreno Y, Pastor-Satorras R, Vespignani A (2002) Epidemic outbreaks in complex heterogeneous networks. Eur Phys J B-Condens Matter Compl Syst 26(4):521–529

    Google Scholar 

  • Newman ME (2002) Spread of epidemic disease on networks. Phys Rev E 66(1):016128

    Article  MathSciNet  Google Scholar 

  • Newman ME (2003) The structure and function of complex networks. SIAM Rev 45(2):167–256

    Article  MathSciNet  MATH  Google Scholar 

  • Newman ME (2004) Fast algorithm for detecting community structure in networks. Phys Rev E 69(6):066133

    Article  Google Scholar 

  • Newman ME (2005) A measure of betweenness centrality based on random walks. Soc Netw 27(1):39–54

    Article  Google Scholar 

  • Newman ME (2006) Modularity and community structure in networks. Proc Nat Acad Sci 103(23):8577–8582

    Article  Google Scholar 

  • Orman GK, Labatut V, Cherifi H (2011) On accuracy of community structure discovery algorithms. ar**v preprint ar**v:1112.4134

  • Orman GK, Labatut V, Cherifi H (2012) Comparative evaluation of community detection algorithms: a topological approach. J Stat Mech: Theory Exp 2012(08):08001

    Article  Google Scholar 

  • Orman K, Labatut V, Cherifi H (2013) An empirical study of the relation between community structure and transitivity. In: Menezes R, Evsukoff A, González M (eds) Complex networks. Springer, Berlin, pp 99–110

    Chapter  Google Scholar 

  • Orman GK, Labatut V, Cherifi H (2013) Towards realistic artificial benchmark for community detection algorithms evaluation. Int J Web Based Communities 9(3):349–370

    Article  Google Scholar 

  • Palla G, Derényi I, Farkas I, Vicsek T (2005) Uncovering the overlap** community structure of complex networks in nature and society. Nature 435(7043):814

    Article  Google Scholar 

  • Pons P, Latapy M (2006) Computing communities in large networks using random walks. J Graph Algorithms Appl 10(2):191–218

    Article  MathSciNet  MATH  Google Scholar 

  • Porter MA, Onnela J-P, Mucha PJ (2009) Communities in networks. Not AMS 56(9):1082–1097

    MathSciNet  MATH  Google Scholar 

  • Rosvall M, Bergstrom CT (2007) An information-theoretic framework for resolving community structure in complex networks. Proc Nat Acad Sci 104(18):7327–7331

    Article  Google Scholar 

  • Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Nat Acad Sci 105(4):1118–1123

    Article  Google Scholar 

  • Salathé M, Jones JH (2010) Dynamics and control of diseases in networks with community structure. PLoS Comput Biol 6(4):1000736

    Article  MathSciNet  Google Scholar 

  • Taghavian F, Salehi M, Teimouri M (2017) A local immunization strategy for networks with overlap** community structure. Phys A 467:148–156

    Article  Google Scholar 

  • Traud AL, Mucha PJ, Porter MA (2012) Social structure of facebook networks. Phys A 391(16):4165–4180

    Article  Google Scholar 

  • Tulu MM, Hou R, Younas T (2018) Identifying influential nodes based on community structure to speed up the dissemination of information in complex network. IEEE Access 6:7390–7401

    Article  Google Scholar 

  • Wang W, Liu Q-H, Zhong L-F, Tang M, Gao H, Stanley HE (2016) Predicting the epidemic threshold of the susceptible-infected-recovered model. Sci Rep 6:24676

    Article  Google Scholar 

  • Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’networks. Nature 393(6684):440

    Article  MATH  Google Scholar 

  • Yang J, Leskovec J (2014) Structure and overlaps of ground-truth communities in networks. ACM Trans Intell Syst Technol (TIST) 5(2):26

    Google Scholar 

  • Zhang X-S, Wang R-S, Wang Y, Wang J, Qiu Y, Wang L, Chen L (2009) Modularity optimization in community detection of complex networks. EPL (Europhys Lett) 87(3):38002

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LRIT URAC No 29, Faculty of Science, Rabat IT Center, Mohammed V University, Rabat, Morocco

    Zakariya Ghalmane & Mohammed El Hassouni

  2. LE2I UMR 6306 CNRS, University of Burgundy, Dijon, France

    Hocine Cherifi

Authors
  1. Zakariya Ghalmane
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohammed El Hassouni
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hocine Cherifi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hocine Cherifi.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (pdf 692 KB)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ghalmane, Z., Hassouni, M.E. & Cherifi, H. Immunization of networks with non-overlap** community structure. Soc. Netw. Anal. Min. 9, 45 (2019). https://doi.org/10.1007/s13278-019-0591-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s13278-019-0591-9

Keywords

Search

Navigation