Top

Social Network Analysis and Mining

Published in:

01-12-2015 | Original Article

Fuzzy overlapping community quality metrics

Authors: Mingming Chen, Boleslaw K. Szymanski

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

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

search-config

AI-assisted search

Off

Abstract

Modularity is widely used to effectively measure the strength of the disjoint community structure found by community detection algorithms. Several overlapping extensions of modularity were proposed to measure the quality of overlapping community structure. However, all these extensions differ just in the way they define the belonging coefficient and belonging function. Yet, there is lack of systematic comparison of different extensions. To fill this gap, we overview overlapping extensions of modularity and generalize them with a uniform definition enabling application of different belonging coefficients and belonging functions to select the best. In addition, we extend localized modularity, modularity density, and eight local community quality metrics to enable their usages for overlapping communities. The experimental results on a large number of real networks and synthetic networks using overlapping extensions of modularity, overlapping modularity density, and local metrics show that the best results are obtained when the product of the belonging coefficients of two nodes is used as the belonging function. Moreover, the results may be used to guide researchers on which metrics to adopt when measuring the quality of overlapping community structure.

previous article Studying the attributes of users in Twitter considering their emotional states

next article Detecting sociosemantic communities by applying social network analysis in tweets

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

Adamic LA, Glance N (2005) The political blogosphere and the 2004 U.S. election: Divided they blog. In: Proceedings of the 3rd International Workshop on Link Discovery., LinkKDD ’05ACM, New York, pp 36–43

Boguñá M, Pastor-Satorras R, Díaz-Guilera A, Arenas A (2004) Models of social networks based on social distance attachment. Phys Rev E 70, 056,122

Chakraborty T, Srinivasan S, Ganguly N, Mukherjee A, Bhowmick S (2014) On the permanence of vertices in network communities. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14ACM, New York, pp 1396–1405

Chen D, Shang M, Lv Z, Fu Y (2010) Detecting overlapping communities of weighted networks via a local algorithm. Phys A Stat Mech Appl 389(19):4177–4187CrossRef

Chen M, Kuzmin K, Szymanski B (2014a) Community detection via maximization of modularity and its variants. IEEE Trans Comput Soc Syst 1(1):46–65CrossRef

Chen M, Kuzmin K, Szymanski B (2014b) Extension of modularity density for overlapping community structure. In: 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp 856–863

Chen M, Nguyen T, Szymanski BK (2013a) A new metric for quality of network community structure. ASE Hum J 2(4):226–240

Chen M, Nguyen T, Szymanski BK (2013b) On measuring the quality of a network community structure. In: Proceedings of ASE/IEEE International Conference on Social Computing. Washington, DC, USA, pp 122–127

Collins SR, Kemmeren KP, Chu Zhao FX, Greenblatt GJF, Spencer F (2007) Toward a comprehensive atlas of the physical interactome of saccharomyces cerevisiae. Mol Cell Proteomic 6:439–450CrossRef

Duch J, Arenas A (2005) Community detection in complex networks using extremal optimization. Phys Rev E 72, 027,104. doi:10.1103/PhysRevE.72.027104

Fortunato S (2010) Community detection in graphs. Phys Rep 486:75–174. doi:10.1016/j.physrep.2009.11.002 MathSciNetCrossRef

Fortunato S, Barthélemy M (2007) Resolution limit in community detection. Proc Natl Acad Sci 104(1):36–41. doi:10.1073/pnas.0605965104 CrossRef

Gaiteri C, Chen M, Szymanski BK, Kuzmin K, Xie J, Lee C, Blanche T, Neto EC, Huang SC, Grabowski T, Madhyastha T, Komashko V (2015) Identifying robust clusters and multi-community nodes by combining top-down and bottom-up approaches to clustering. http://arxiv.org/abs/1501.04709

Gavin AC, Aloy P, Grandi P et al (2006) Proteome survey reveals modularity of the yeast cell machinery. Nature 440(7084):631–636CrossRef

Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826MATHMathSciNetCrossRef

Gleiser P, Danon L (2003) Community structure in jazz. Adv Complex Syst 06(04):565–573CrossRef

Gregory S (2010) Finding overlapping communities in networks by label propagation. New J Phys 12(10), 103,018

Gregory S (2011) Fuzzy overlapping communities in networks. J Stat Mech Theory Exp 2011(02), P02,017

Guimerà R, Danon L, DíazGuilera A, Giralt F, Arenas A (2003) Self-similar community structure in a network of human interactions. Phys Rev E 68, 065,103

Hong EL, Balakrishnan R, Dong Q et al (2008) Gene ontology annotations at SGD: new data sources and annotation methods. Nucleic Acids Res 36:D577–D581CrossRef

Knuth DE (1993) The Stanford GraphBase: a platform for combinatorial computing. Addison-Wesley, Reading

Krebs V (2004) http://www.orgnet.com/

Lancichinetti A, Fortunato S (2009a) Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys Rev E 80, 016,118

Lancichinetti A, Fortunato S, Kertész J (2009b) Detecting the overlapping and hierarchical community structure in complex networks. New J Phys 11(3), 033,015

Li Z, Zhang S, Wang RS, Zhang XS, Chen L (2008) Quantitative function for community detection. Phys Rev E 77, 036,109

Lusseau D, Schneider K, Boisseau O, Haase P, Slooten E, Dawson S (2003) The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behav Ecol Sociobiol 54(4):396–405CrossRef

Mewes HW, Amid C, Arnold R et al (2004) MIPS: analysis and annotation of proteins from whole genomes. Nucleic Acids Res 32:D41–D44CrossRef

Muff S, Rao F, Caflisch A (2005) Local modularity measure for network clusterizations. Phys Rev E 72, 056,107

Nepusz T, Petróczi A, Négyessy L, Bazsó F (2008) Fuzzy communities and the concept of bridgeness in complex networks. Phys Rev E 77, 016,107

Newman MEJ (2004) Fast algorithm for detecting community structure in networks. Phys Rev E 69, 066,133. doi:10.1103/PhysRevE.69.066133

Newman MEJ (2006a) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E 74, 036,104

Newman MEJ (2006b) Modularity and community structure in networks. Proc Natl Acad Sci 103(23):8577–8582. doi:10.1073/pnas.0601602103 CrossRef

Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69, 026,113. doi:10.1103/PhysRevE.69.026113

Nicosia V, Mangioni G, Carchiolo V, Malgeri M (2009) Extending the definition of modularity to directed graphs with overlapping communities. J Stat Mech Theory Exp 2009(03), P03,024

Palla G, Derényi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nat 435:814–818. doi:10.1038/nature03607 CrossRef

Pu S, Wong J, Turner B, Cho E, Wodak SJ (2009) Up-to-date catalogues of yeast protein complexes. Nucleic Acids Res 37(3):825–831CrossRef

Shen H, Cheng X, Cai K, Hu MB (2009a) Detect overlapping and hierarchical community structure in networks. Phys A Stat Mech Appl 388(8):1706–1712CrossRef

Shen HW, Cheng XQ, Guo JF (2009b) Quantifying and identifying the overlapping community structure in networks. J Stat Mech Theory Exp 2009(07), P07,042

Xie J, Kelley S, Szymanski BK (2013) Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput Surv 45(4):43:1–43:35CrossRef

Xie J, Szymanski BK (2012) Towards linear time overlapping community detection in social networks. In: The 16th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), pp 25–36

Yang J, Leskovec J (2012) Defining and evaluating network communities based on ground-truth. In: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, MDS ’12. ACM, New York, pp 3:1–3:8

Zachary W (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33:452–473

Zhang S, Wang RS, Zhang XS (2007) Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Phys A Stat Mech Appl 374(1):483–490CrossRef

Title: Fuzzy overlapping community quality metrics
Authors: Mingming Chen
Boleslaw K. Szymanski
Publication date: 01-12-2015
Publisher: Springer Vienna
Published in: Social Network Analysis and Mining / Issue 1/2015
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-015-0279-8

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/2015

Time-aware analysis and ranking of lurkers in social networks

Social ties, homophily and extraversion--introversion to generate complex networks

Modeling and OLAPing social media: the case of Twitter

Using coherencies to examine network evolution and co-evolution

Modeling influence diffusion to uncover influence centrality and community structure in social networks

Inference of demographic attributes based on mobile phone usage patterns and social network topology

Premium Partner