Top

Social Network Analysis and Mining

Published in:

01-12-2019 | Original Article

Immunization of networks with non-overlapping community structure

Authors: Zakariya Ghalmane, Mohammed El Hassouni, Hocine Cherifi

Published in: Social Network Analysis and Mining | Issue 1/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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-overlapping 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.

previous article Localizing and quantifying infrastructure damage using class activation mapping approaches

next article Social BI to understand the debate on vaccines on the Web and social media: unraveling the anti-, free, and pro-vax communities in Italy

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

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

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

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

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

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

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

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

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

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

Chakraborty D, Singh A, Cherifi H (2016) Immunization strategies based on the overlapping 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):247901CrossRef

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

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

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 arXiv:1203.0535

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

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

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

Ghalmane Z, El Hassouni M, Cherifi H (2018) Betweenness centrality for networks with non-overlapping 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

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):83489CrossRef

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

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:2171CrossRef

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

Jebabli M, Cherifi H, Cherifi C, Hammouda A (2014) Overlapping 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):012821CrossRef

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

Kumar M, Singh A, Cherifi H (2018) An efficient immunization strategy using overlapping 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):046110CrossRef

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

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–123MathSciNetMATHCrossRef

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

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–63MathSciNetCrossRef

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

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

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

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

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

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

Orman GK, Labatut V, Cherifi H (2011) On accuracy of community structure discovery algorithms. arXiv preprint arXiv: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):08001CrossRef

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–110CrossRef

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

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

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

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

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

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

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

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

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

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–7401CrossRef

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:24676CrossRef

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

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

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):38002CrossRef

Title: Immunization of networks with non-overlapping community structure
Authors: Zakariya Ghalmane
Mohammed El Hassouni
Hocine Cherifi
Publication date: 01-12-2019
Publisher: Springer Vienna
Published in: Social Network Analysis and Mining / Issue 1/2019
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-019-0591-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2019

Diachronic equivalence: an examination of the international news network

Disaster damage assessment from the tweets using the combination of statistical features and informative words

Topic modeling and sentiment analysis of global climate change tweets

False information detection in online content and its role in decision making: a systematic literature review

A heuristic approach to estimate nodes’ closeness rank using the properties of real world networks

Complex networks are structurally distinguishable by domain

Premium Partner