survey

Metrics for Community Analysis: A Survey

Authors:

Tanmoy Chakraborty,

Animesh Mukherjee,

Niloy GangulyAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 50, Issue 4

Article No.: 54, Pages 1 - 37

https://doi.org/10.1145/3091106

Published: 30 August 2017 Publication History

Abstract

Detecting and analyzing dense groups or communities from social and information networks has attracted immense attention over the last decade due to its enormous applicability in different domains. Community detection is an ill-defined problem, as the nature of the communities is not known in advance. The problem has turned even more complicated due to the fact that communities emerge in the network in various forms such as disjoint, overlapping, and hierarchical. Various heuristics have been proposed to address these challenges, depending on the application in hand. All these heuristics have been materialized in the form of new metrics, which in most cases are used as optimization functions for detecting the community structure, or provide an indication of the goodness of detected communities during evaluation. Over the last decade, a large number of such metrics have been proposed. Thus, there arises a need for an organized and detailed survey of the metrics proposed for community detection and evaluation. Here, we present a survey of the start-of-the-art metrics used for the detection and the evaluation of community structure. We also conduct experiments on synthetic and real networks to present a comparative analysis of these metrics in measuring the goodness of the underlying community structure.

Supplementary Material

a54-chakraborty-suppl.pdfr (chakraborty.zip)

Supplemental movie, appendix, image and software files for, Metrics for Community Analysis: A Survey

Download
387.41 KB

References

[1]

E. Abbe and C. Sandon. 2015. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS’15). 670--688.

Digital Library

[2]

R. Aldecoa and I. Marín. 2013. Surprise maximization reveals the community structure of complex networks. Scientific Reports 3 (2013).

[3]

R. Aldecoa and I. Marín. 2011. Deciphering network community structure by surprise. PloS One 6, 9 (2011), e24195.

[4]

A. Arenas, J. Duch, A. Fernndez, and S. Gmez. 2007. Size reduction of complex networks preserving modularity. New Journal of Physics 9, 6 (2007), 176.

[5]

A. Arenas, A. Fernndez, S. Fortunato, and S. Gmez. 2008. Motif-based communities in complex networks. Journal of Physics A: Mathematical and Theoretical 41, 22 (2008), 224001.

[6]

A. Arenas, A. Fernndez, and S. Gmez. 2008. Analysis of the structure of complex networks at different resolution levels. New Journal of Physics 10, 5 (2008), 053039.

[7]

J. Artiles, J. Gonzalo, and S. Sekine. 2007. The SemEval-2007 WePS evaluation: Establishing a benchmark for the web people search task. In Proceedings of the 4th International Workshop on Semantic Evaluations (SemEval’07). Association for Computational Linguistics, 64--69.

Digital Library

[8]

T. Aynaud and J.-L. Guillaume. 2010. Static community detection algorithms for evolving networks. In Proceedings of the 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt’10). 513--519.

[9]

M. F. Balcan and Y. Liang. 2013. Modeling and detecting community hierarchies. In Proceedings of the 2nd International Conference on Similarity-Based Pattern Recognition (SIMBAD’13). Springer-Verlag, Berlin,160--175.

Digital Library

[10]

J. Baumes, M. K. Goldberg, M. S. Krishnamoorthy, M. Magdon-Ismail, and N. Preston. 2005. Finding communities by clustering a graph into overlapping subgraphs.IADIS AC 5 (2005), 97--104.

[11]

A. R. Benson, D. F. Gleich, and J. Leskovec. 2016. Higher-order organization of complex networks. Science 353, 6295 (2016), 163--166.

[12]

P. Berkhin. 2006. A survey of clustering data mining techniques. In Grouping Multidimensional Data - Recent Advances in Clustering. 25--71.

[13]

V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E. L. J. S. Mech. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics 2008 (2008), P10008.

[14]

R. J. G. B. Campello. 2007. A fuzzy extension of the Rand index and other related indexes for clustering and classification assessment. Pattern Recognition Letters 28, 7 (2007), 833--841.

Digital Library

[15]

R. J. G. B. Campello. 2010. Generalized external indexes for comparing data partitions with overlapping categories. Pattern Recognition Letters 31, 9 (2010), 966--975.

Digital Library

[16]

A. Chakraborty, S. Ghosh, and N. Ganguly. 2012. Detecting overlapping communities in folksonomies. In 23rd ACM Conference on Hypertext and Social Media. 213--218.

Digital Library

[17]

T. Chakraborty. 2015. Leveraging disjoint communities for detecting overlapping community structure. Journal of Statistical Mechanics: Theory and Experiment 2015, 5 (2015), P05017.

[18]

T. Chakraborty and A. Chakraborty. 2013. OverCite: Finding overlapping communities in citation network. In International Conference on Advances in Social Network Analysis and Mining (ASONAM'13). 1124--1131.

Digital Library

[19]

T. Chakraborty, S. Kumar, N. Ganguly, A. Mukherjee, and S. Bhowmick. 2016. GenPerm: A unified method for detecting non-overlapping and overlapping communities. IEEE Trans. Knowl. Data Eng. 28, 8 (2016), 2101--2114.

Digital Library

[20]

T. Chakraborty, S. Sikdar, N. Ganguly, and A. Mukherjee. 2014. Citation interactions among computer science fields: A quantitative route to the rise and fall of scientific research. Social Network Analysis Mining 4, 1 (2014), 187.

[21]

T. Chakraborty, S. Sikdar, V. Tammana, N. Ganguly, and A. Mukherjee. 2013. Computer science fields as ground-truth communities: Their impact, rise and fall. In Advances in Social Networks Analysis and Mining 2013 (ASONAM’13). 426--433.

[22]

T. Chakraborty, S. Srinivasan, N. Ganguly, S. Bhowmick, and A. Mukherjee. 2013. Constant communities in complex networks. Scientific Reports 3 (2013).

[23]

T. Chakraborty, S. Srinivasan, N. Ganguly, A. Mukherjee, and S. Bhowmick. 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’14). ACM, New York,1396--1405.

Digital Library

[24]

T. Chakraborty, S. Srinivasan, N. Ganguly, A. Mukherjee, and S. Bhowmick. 2016. Permanence and community structure in complex networks. CoRR abs/1606.01543 (2016).

[25]

D. Chen, M. Shang, Z. Lv, and Y. Fu. 2010. Detecting overlapping communities of weighted networks via a local algorithm. Physica A: Statistical Mechanics and its Applications 389, 19 (2010), 4177--4187.

[26]

G. Chen, Y. Wang, and J. Wei. 2013. A new multiobjective evolutionary algorithm for community detection in dynamic complex networks. Mathematical Problems in Engineering 2013 (2013), 1--7.

[27]

J. Chen, O. R. Zaane, and R. Goebel. 2009. Detecting communities in social networks using max-min modularity. In SDM. SIAM, 978--989.

[28]

M. Chen, K. Kuzmin, and B. K. Szymanski. 2014. Community detection via maximization of modularity and its variants. IEEE Transactions on Computational Social Systems 1, 1 (March 2014), 46--65.

[29]

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

[30]

M. Chen, T. Nguyen, and B. K. Szymanski. 2013. On measuring the quality of a network community structure. In 2013 International Conference on Social Computing (SocialCom’13). 122--127.

Digital Library

[31]

C. Chira, A. Gog, and D. Iclanzan. 2012. Evolutionary detection of community structures in complex networks: A new fitness function. In IEEE Congress on Evolutionary Computation (CEC’12). 1--8.

[32]

A. Clauset, M. E. J. Newman, and C. Moore. 2004. Finding community structure in very large networks. Physical Review E 70, 6 (2004), 066111.

[33]

L. M. Collins and C. W. Dent. 1988. Omega: A general formulation of the rand index of cluster recovery suitable for non-disjoint solutions. Multivariate Behavioral Research 23, 2 (1988), 231--242.

[34]

J. Creusefond, T. Largillier, and S. Peyronnet. 2014. Finding compact communities in large graphs. CoRR abs/1410.2105 (2014).

[35]

J. Creusefond, T. Largillier, and S. Peyronnet. 2015. On the evaluation potential of quality functions in community detection for different contexts. CoRR arXiv:1510.01714 (2015).

[36]

L. Danon, A. Daz-Guilera, J. Duch, and A. Arenas. 2005. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment 2005, 9 (2005), P09008.

[37]

L. Danon, A. Daz-Guilera, J. Duch, and A. Arenas. 2005. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment 2005, 9 (2005), P09008.

[38]

F.-O. de Frana and G.-P. Coelho. 2015. A flexible fitness function for community detection in complex networks. In Complex Networks VI, Giuseppe Mangioni, Filippo Simini, Stephen Miles Uzzo, and Dashun Wang (Eds.). Studies in Computational Intelligence, Vol. 597. Springer International Publishing, 1--12.

[39]

J. Duch and A. Arenas. 2005. Community detection in complex networks using extremal optimization. Physical Review E 72, 2 (2005), 027104.

[40]

B. Faltings, K. Leyton-Brown, and P. Ipeirotis (Eds.). 2012. ACM Conference on Electronic Commerce (EC’12). ACM. http://dl.acm.org/citation.cfm?id=2229012

[41]

Z. Feng, X. Xu, N. Yuruk, and T. A. J. Schweiger. 2007. A novel similarity-based modularity function for graph partitioning. In Data Warehousing and Knowledge Discovery, Ilyeal Song, Johann Eder, and Thomanh Nguyen (Eds.). Lecture Notes in Computer Science, Vol. 4654. Springer, Berlin, 385--396.

[42]

G. W. Flake, S. Lawrence, and C. Lee Giles. 2000. Efficient identification of web communities. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’00). ACM, New York,150--160.

Digital Library

[43]

T. Fleck, A. Kappes, and D. Wagner. 2014. Graph clustering with surprise: Complexity and exact solutions. In Theory and Practice of Computer Science (SOFSEM’14), Viliam Geffert, Bart Preneel, Branislav Rovan, Jlius tuller, and Amin Tjoa (Eds.). Lecture Notes in Computer Science, Vol. 8327. Springer International Publishing, 223--234.

[44]

S. Fortunato. 2010. Community detection in graphs. Physics Reports 486, 3--5 (2010), 75--174.

[45]

S. Fortunato and M. Barthlemy. 2007. Resolution limit in community detection. PNAS 104, 1 (2007), 36--41.

[46]

S. Fortunato and A. Lancichinetti. 2009. Community detection algorithms: A comparative analysis: Invited presentation, extended abstract. In 4th International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS’09). 27.

[47]

E. B. Fowlkes and C. L. Mallows. 1983. A method for comparing two hierarchical clusterings. Journal of the American Statistical Association 78, 383 (1983), 553--569.

[48]

A. Fronczak, P. Fronczak, and J. A. Hołyst. 2004. Average path length in random networks. Physical Review E 70, 5 (Nov.2004), 056110.

[49]

R. Ghosh and K. Lerman. 2010. Community detection using a measure of global influence. In Proceedings of the 2nd International Conference on Advances in Social Network Mining and Analysis (SNAKDD’08). Springer-Verlag, Berlin,20--35.

[50]

M. Girvan and M. E. Newman. 2002. Community structure in social and biological networks. PNAS 99, 12 (June 2002), 7821--7826.

[51]

M. Gong, Q. Cai, Y. Li, and J. Ma. 2012. An improved memetic algorithm for community detection in complex networks. In 2012 IEEE Congress on Evolutionary Computation. IEEE, 1--8.

[52]

M. Gong, B. Fu, L. Jiao, and H. Du. 2011. Memetic algorithm for community detection in networks. Physical Review E 84, 5 (2011), 056101.

[53]

B. H. Good, Y.-A. de Montjoye, and A. Clauset. 2010. Performance of modularity maximization in practical contexts. Physical Review E 81, 4 (Apr. 2010), 046106.

[54]

S. Gregory. 2010. Finding overlapping communities in networks by label propagation. New Journal of Physics 12, 10 (2010), 103018.

[55]

S. Gregory. 2011. Fuzzy overlapping communities in networks. Journal of Statistical Mechanics: Theory and Experiment 2011, 2 (2011), P02017.

[56]

R. Guimera, M. Sales-Pardo, and L. A. N. Amaral. 2004. Modularity from fluctuations in random graphs and complex networks. Physical Review E 70, 2 (2004), 025101.

[57]

M. Halkidi, Y. Batistakis, and M. Vazirgiannis. 2001. On clustering validation techniques. Journal of Intelligent Information Systems 17, 2--3 (Dec. 2001), 107--145.

Digital Library

[58]

S. Harenberg, G. Bello, L. Gjeltema, S. Ranshous, J. Harlalka, R. Seay, K. Padmanabhan, and N. Samatova. 2014. Community detection in large-scale networks: A survey and empirical evaluation. WIREs Computer Statistics 6 (2014), 426--439.

Digital Library

[59]

F. Havemann, M. Heinz, A. Struck, and J. Glser. 2011. Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels. Journal of Statistical Mechanics: Theory and Experiment 2011, 1 (2011), P01023.

[60]

D. S. Hochbaum. 2010. Polynomial time algorithms for ratio regions and a variant of normalized cut. IEEE Transactions on Pattern Analysis and Machine Intelligence 32, 5 (2010), 889--898.

Digital Library

[61]

D. Hric, R. K. Darst, and S. Fortunato. 2014. Community detection in networks: Structural communities versus ground truth. Physical Review E 90, 6 (Dec. 2014), 062805.

[62]

L. Hubert and P. Arabie. 1985. Comparing partitions. Journal of Classification 2, 1 (1985), 193--218.

[63]

E. Hullermeier and M. Rifqi. 2009. A fuzzy variant of the Rand index for comparing clustering structures. In IFSA/EUSFLAT Conference, Joo Paulo Carvalho, Didier Dubois, Uzay Kaymak, and Joo Miguel da Costa Sousa (Eds.). 1294--1298.

[64]

A. K. Jain and R. C. Dubes. 1988. Algorithms for Clustering Data. Prentice-Hall,Upper Saddle River, NJ.

[65]

D. Jiang, C. Tang, and A. Zhang. 2004. Cluster analysis for gene expression data: A survey. IEEE Transactions on Knowledge and Data Engineering 16, 11 (Nov. 2004), 1370--1386.

Digital Library

[66]

S. Kelley. 2011. The Existence and Discovery of Overlapping Communities in Large-Scale Networks. BiblioBazaar. https://books.google.com/books?id=mW4CywAACAAJ.

[67]

Y. Kim, S.-W. Son, and H. Jeong. 2010. Finding communities in directed networks. Physical Review E 81, 1 (Jan 2010), 016103.

[68]

A. Kraskov, H. Stgbauer, R. G. Andrzejak, and P. Grassberger. 2003. Hierarchical clustering based on mutual information. CoRR q-bio.QM/0311039 (2003).

[69]

V. Labatut. 2013. Generalized measures for the evaluation of community detection methods. CoRR abs/1303.5441 (2013).

[70]

A. Lancichinetti and S. Fortunato. 2009. Community detection algorithms: A comparative analysis. Physical Review E 80, 5 (Nov 2009), 056117.

[71]

A. Lancichinetti and S. Fortunato. 2011. Limits of modularity maximization in community detection. Physical Review E 84, 6 (Dec 2011), 066122.

[72]

A. Lancichinetti, S. Fortunato, and J. Kertész. 2009. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics 11, 3 (2009), 033015.

[73]

A. Lancichinetti, M. Kivel, J. Saramki, and S. Fortunato. 2010. Characterizing the community structure of complex networks. PLoS ONE 5, 8 (2010), e11976.

[74]

A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato. 2011. Finding statistically significant communities in networks. PLoS ONE 6, 4 (2011), e18961.

[75]

A. Lázár, D. Ábel, and T. Vicsek. 2010. Modularity measure of networks with overlapping communities. EPL (Europhysics Letters) 90, 1 (2010), 18001.

[76]

J. Leskovec, K. J. Lang, and M. Mahoney. 2010. Empirical comparison of algorithms for network community detection. In Proceedings of the 19th International Conference on World Wide Web (WWW’10). ACM, New York, 631--640.

Digital Library

[77]

X. Li, B. Wu, Q. Guo, X. Zeng, and C. Shi. 2015. Dynamic community detection algorithm based on incremental identification. In 2015 IEEE International Conference on Data Mining Workshop (ICDMW’15). 900--907.

Digital Library

[78]

Z. Li, S. Zhang, R.-S. Wang, X.-S. Zhang, and L. Chen. 2008. Quantitative function for community detection. Physical Review E 77, 3 (2008), 036109.

[79]

T. Y. Lin, S. Ohsuga, C.-J. Liau, and X. Hu (Eds.). 2006. Foundations and Novel Approaches in Data Mining. Studies in Computational Intelligence, Vol. 9. Springer.

[80]

X. Liu, T. Murata, and K. Wakita. 2012. Extending modularity by capturing the similarity attraction feature in the null model. arXiv preprint arXiv:1210.4007 (2012).

[81]

M. W. Mahoney, A. Dasgupta, K. J. Lang, and J. Leskovec. 2009. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics 6, 1 (2009), 29--123.

[82]

C. D. Manning, P. Raghavan, and H. Schütze. 2008. Introduction to Information Retrieval. Cambridge University Press, New York.

[83]

C. P. Massen and J. P. K. Doye. 2005. Identifying communities within energy landscapes. Physical Review E 71, 4 (Apr 2005), 046101.

[84]

A. McDaid and N. Hurley. 2010. Detecting highly overlapping communities with model-based overlapping seed expansion. In ASONAM. Washington, DC,112--119.

Digital Library

[85]

A. F. McDaid, D. Greene, and N. J. Hurley. 2011. Normalized mutual information to evaluate overlapping community finding algorithms. CoRR abs/1110.2515 (2011).

[86]

M. Meilă. 2007. Comparing clusterings—An information based distance. Journal of Multivariate Analysis 98, 5 (May 2007), 873--895.

Digital Library

[87]

A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. 2007. Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement (IMC’07). ACM, New York, 29--42.

Digital Library

[88]

A. Miyauchi and Y. Kawase. 2015. What is a network community?: A novel quality function and detection algorithms. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM’15). ACM, New York, 1471--1480.

[89]

A. Miyauchi and Y. Kawase. 2015. Z-score-based modularity for community detection in networks. CoRR abs/1501.01909 (2015).

[90]

C.-H. Mu, J. Xie, Y. Liu, F. Chen, Y. Liu, and L.-C. Jiao. 2015. Memetic algorithm with simulated annealing strategy and tightness greedy optimization for community detection in networks. Applied Soft Computing 34 (2015), 485--501.

Digital Library

[91]

S. Muff, F. Rao, and A. Caflisch. 2005. Local modularity measure for network clusterizations. Physical Review E 72, 5 (2005), 056107.

[92]

G. Murray, G. Carenini, and R. Ng. 2012. Using the omega index for evaluating abstractive community detection. In Proceedings of Workshop on Evaluation Metrics and System Comparison for Automatic Summarization. Association for Computational Linguistics, Stroudsburg, PA, 10--18.

[93]

T. Nepusz, A. Petróczi, L. Négyessy, and F. Bazsó. 2008. Fuzzy communities and the concept of bridgeness in complex networks. Physical Review E 77, 1 (Jan. 2008), 016107.

[94]

M. E. J. Newman. 2004. Analysis of weighted networks. Physical Review E 70, 5 (Nov. 2004), 056131.

[95]

M. E. J. Newman. 2004. Detecting community structure in networks. EPJB 38, 2 (March 2004), 321--330.

[96]

M. E. J. Newman. 2004. Fast algorithm for detecting community structure in networks. Physical Review E 69, 6 (June 2004), 066133.

[97]

M. E. J. Newman. 2006. Modularity and community structure in networks. PNAS 103, 23 (2006), 8577--8582.

[98]

M. E. J. Newman and M. Girvan. 2004. Finding and evaluating community structure in networks. Physical Review E 69, 2 (Feb. 2004), 026113.

[99]

M. E. J. Newman and E. A. Leicht. 2007. Mixture models and exploratory analysis in networks. PNAS 104, 23 (2007), 9564--9569.

[100]

V. Nicosia, G. Mangioni, V. Carchiolo, and M. Malgeri. 2009. Extending the definition of modularity to directed graphs with overlapping communities. Journal of Statistical Mechanics: Theory and Experiment 2009, 03 (2009), P03024. http://stacks.iop.org/1742-5468/2009/i=03/a=P03024.

[101]

G. K. Orman, V. Labatut, and H. Cherifi. 2012. Comparative evaluation of community detection algorithms: A topological approach. Journal of Statistical Mechanics 8 (2012), p08001.

[102]

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

[103]

L. Peel, D. B. Larremore, and A. Clauset. 2016. The ground truth about metadata and community detection in networks. CoRR abs/1608.05878 (2016). http://arxiv.org/abs/1608.05878

[104]

C. Pizzuti. 2008. GA-net: A genetic algorithm for community detection in social networks. In PPSN, Gnter Rudolph, Thomas Jansen, Simon M. Lucas, Carlo Poloni, and Nicola Beume (Eds.), Vol. 5199. Springer, 1081--1090.

[105]

C. Pizzuti. 2008. GA-net: A genetic algorithm for community detection in social networks. In Parallel Problem Solving from Nature PPSN X, Gnter Rudolph, Thomas Jansen, Nicola Beume, Simon Lucas, and Carlo Poloni (Eds.). Lecture Notes in Computer Science, Vol. 5199. Springer, Berlin, 1081--1090.

Digital Library

[106]

C. Pizzuti. 2009. Overlapped community detection in complex networks. In Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation. 859--866.

Digital Library

[107]

C. Pizzuti. 2012. A multiobjective genetic algorithm to find communities in complex networks. IEEE Transactions on Evolutionary Computation 16, 3 (June 2012), 418--430.

Digital Library

[108]

P. Pons and M. Latapy. 2006. Computing communities in large networks using random walks. Journal of Graph Algortihms and Applications 10, 2 (2006), 191--218.

[109]

R. Rabbany, M. Takaffoli, J. Fagnan, O. R. Zaıane, and R. J. G. B. Campello. 2013. Communities validity: Methodical evaluation of community mining algorithms. Social Netw. Analys. Mining 3, 4 (2013), 1039--1062.

[110]

R. Rabbany and O. R. Zaane. 2015. Generalization of clustering agreements and distances for overlapping clusters and network communities. Data Mining and Knowledge Discovery 29, 5 (2015), 1458--1485.

Digital Library

[111]

F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi. 2004. Defining and identifying communities in networks. PNAS 101, 9 (2004), 2658.

[112]

J. Reichardt and S. Bornholdt. 2004. Detecting fuzzy community structures in complex networks with a potts model. Physical Review Letters 93, 21 (Nov 2004), 218701.

[113]

J. Reichardt and S. Bornholdt. 2006. Statistical mechanics of community detection. Physical Review E 74, 1 (July 2006), 016110.

[114]

J. Reichardt and S. Bornholdt. 2006. When are networks truly modular?Physica D Nonlinear Phenomena 224 (December 2006), 20--26.

[115]

M. Rosvall and C. T. Bergstrom. 2007. An information-theoretic framework for resolving community structure in complex networks. PNAS 104, 18 (2007), 7327.

[116]

M. Rosvall and C. T. Bergstrom. 2008. Maps of random walks on complex networks reveal community structure. PNAS 105, 4 (2008), 1118--1123.

[117]

S. E. Schaeffer. 2007. Survey: Graph clustering. Computer Science Review 1, 1 (Aug. 2007), 27--64. 1574-0137DOI:http://dx.doi.org/10.1016/j.cosrev.2007.05.001

Digital Library

[118]

P. Schuetz and A. Caflisch. 2008. Multistep greedy algorithm identifies community structure in real-world and computer-generated networks. Physical Review E 78, 2 (2008), 026112.

[119]

H. Shen, X. Cheng, K. Cai, and M.-B. Hu. 2009. Detect overlapping and hierarchical community structure in networks. Physica A: Statistical Mechanics and its Applications 388, 8 (2009), 1706--1712.

[120]

H. Shen, X. Cheng, and J.-F. Guo. 2009. Quantifying and identifying the overlapping community structure in networks. Journal of Statistical Mechanics: Theory and Experiment 2009, 7 (2009), P07042.

[121]

J. Shi and J. Malik. 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 8 (Aug. 2000), 888--905.

Digital Library

[122]

K. Steinhaeuser and N. V. Chawla. 2010. Identifying and evaluating community structure in complex networks. Pattern Recognition Letters 31, 5 (April 2010), 413--421.

Digital Library

[123]

A. Strehl and J. Ghosh. 2003. Cluster ensembles — A knowledge reuse framework for combining multiple partitions. Journal of Machine Learning Research 3 (March 2003), 583--617.

[124]

P. G. Sun, L. Gao, and Y. Yang. 2013. Maximizing modularity intensity for community partition and evolution. Information Science 236 (July 2013), 83--92.

Digital Library

[125]

M. T. Thai and P. M. Pardalos. 2011. Handbook of Optimization in Complex Networks: Theory and Applications. Vol. 57. Springer Science 8 Business Media.

[126]

V. A. Traag, R. Aldecoa, and J.-C. Delvenne. 2015. Detecting communities using asymptotical surprise. Physical Review E 92, 2 (Aug. 2015), 022816.

[127]

V. A. Traag, G. Krings, and P. Van Dooren. 2013. Significant scales in community structure. Scientific Reports 3 (2013).

[128]

T. van Laarhoven and E. Marchiori. 2014. Axioms for graph clustering quality functions. Journal of Machine Learning Research 15 (2014), 193--215.

Digital Library

[129]

N. X. Vinh, J. Epps, and J. Bailey. 2009. Information theoretic measures for clusterings comparison: Is a correction for chance necessary? In ICML. ACM, New York, 1073--1080.

Digital Library

[130]

K. Wakita and T. Tsurumi. 2007. Finding community structure in mega-scale social networks. CoRR abs/cs/0702048 (2007).

[131]

Q. Wang and E. Fleury. 2012. Fuzziness and overlapping communities in large-scale networks. Journal of Universal Computer Science 18, 4 (2012), 457--486.

[132]

D. J. Watts and S. H. Strogatz. 1998. Collective dynamics of’small-world’ networks. Nature 393 (1998), 440--442.

[133]

Y. C. Wei, C. K. Cheng, San Diego. Dept. of Computer Science University of California, and Engineering. 1990. Ratio Cut Partitioning for Hierarchical Designs. Dept. of Computer Science and Engineering, University of California, San Diego.

[134]

Y.-C. Wei and C.-K. Cheng. 1989. Towards efficient hierarchical designs by ratio cut partitioning. In 1989 IEEE International Conference on Computer-Aided Design, 1989 (ICCAD’89). Digest of Technical Papers. 298--301.

[135]

J. J. Whang, D. F. Gleich, and I. S. Dhillon. 2013. Overlapping community detection using seed set expansion. In Proceedings of the 22nd ACM International Conference on Conference on Information and Knowledge Management (CIKM’13). ACM, New York, 2099--2108.

Digital Library

[136]

J. Xiang, Y.-N. Tang, Y.-Y. Gao, Y. Zhang, K. Deng, X.-K. Xu, and K. Hu. 2015. Multi-resolution community detection based on generalized self-loop rescaling strategy. Physica A: Statistical Mechanics and its Applications 432 (2015), 127--139.

[137]

J. Xie, S. Kelley, and B. K. Szymanski. 2013. Overlapping community detection in networks: The state-of-the-art and comparative study. ACM Computing Surveys 45, 4, Article 43 (Aug. 2013), 35 pages.

[138]

J. Xie and B. K. Szymanski. 2012. Towards linear time overlapping community detection in social networks. In PAKDD. Kuala Lumpur, Malaysia, 25--36.

Digital Library

[139]

J. Yang and J. Leskovec. 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, 3:1--3:8.

[140]

J. Yang and J. Leskovec. 2013. Overlapping community detection at scale: A nonnegative matrix factorization approach. In WSDM. ACM, New York, 587--596.

Digital Library

[141]

S. Zhang, R.-S. Wang, and X.-S. Zhang. 2007. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A: Statistical Mechanics and Its Applications 374, 1 (2007), 483--490.

[142]

S. Zhang and H. Zhao. 2012. Community identification in networks with unbalanced structure. Physical Review E 85, 6 (Jun 2012), 066114.

[143]

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

[144]

Y. Zhen-Qing, Z. Ke, H. Song-Nian, and Y. Jun. 2012. A new definition of modularity for community detection in complex networks. Chinese Physics Letters 29, 9 (2012), 098901.

Cited By

Wei PFang YWen ZXiao ZChen B(2025)An end-to-end bi-objective approach to deep graph partitioningNeural Networks10.1016/j.neunet.2024.106823181(106823)Online publication date: Jan-2025
https://doi.org/10.1016/j.neunet.2024.106823
Ribeiro Santiago PSoares GQuintero AJamieson L(2024)Comparing the Clique Percolation algorithm to other overlapping community detection algorithms in psychological networks: A Monte Carlo simulation studyBehavior Research Methods10.3758/s13428-024-02415-256:7(7219-7240)Online publication date: 1-May-2024
https://doi.org/10.3758/s13428-024-02415-2
Gaume BAchitouv IChavalarias D(2024)A Unified Graph Clustering Framework for Complex Systems ModelingSSRN Electronic Journal10.2139/ssrn.4766265Online publication date: 2024
https://doi.org/10.2139/ssrn.4766265
Show More Cited By

Index Terms

Metrics for Community Analysis: A Survey
1. Human-centered computing
  1. Collaborative and social computing
    1. Collaborative and social computing design and evaluation methods
      1. Social network analysis
2. Information systems
  1. Information systems applications
    1. Data mining
      1. Clustering

Recommendations

Permanence and Community Structure in Complex Networks

The goal of community detection algorithms is to identify densely connected units within large networks. An implicit assumption is that all the constituent nodes belong equally to their associated community. However, some nodes are more important in the ...
Are Slice-Based Cohesion Metrics Actually Useful in Effort-Aware Post-Release Fault-Proneness Prediction? An Empirical Study
Background. Slice-based cohesion metrics leverage program slices with respect to the output variables of a module to quantify the strength of functional relatedness of the elements within the module. Although slice-based cohesion metrics have been ...
Community discovery and importance analysis in social network

Social networks are widespread and important in our daily life. Finding communities and reveal node characteristics in community are crucial to understand the network structure and function. Many methods based on Nonnegative matrix factorization NMF are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 50, Issue 4

July 2018

531 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/3135069

Editor:
Sartaj Sahni
Department of Computer and Information Science and Engineering / University of Florida / Gainesville, FL

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 August 2017

Accepted: 01 May 2017

Revised: 01 April 2017

Received: 01 May 2016

Published in CSUR Volume 50, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Survey
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

208
Total Citations
View Citations
2,706
Total Downloads

Downloads (Last 12 months)360
Downloads (Last 6 weeks)60

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wei PFang YWen ZXiao ZChen B(2025)An end-to-end bi-objective approach to deep graph partitioningNeural Networks10.1016/j.neunet.2024.106823181(106823)Online publication date: Jan-2025
https://doi.org/10.1016/j.neunet.2024.106823
Ribeiro Santiago PSoares GQuintero AJamieson L(2024)Comparing the Clique Percolation algorithm to other overlapping community detection algorithms in psychological networks: A Monte Carlo simulation studyBehavior Research Methods10.3758/s13428-024-02415-256:7(7219-7240)Online publication date: 1-May-2024
https://doi.org/10.3758/s13428-024-02415-2
Gaume BAchitouv IChavalarias D(2024)A Unified Graph Clustering Framework for Complex Systems ModelingSSRN Electronic Journal10.2139/ssrn.4766265Online publication date: 2024
https://doi.org/10.2139/ssrn.4766265
Prokop PDráždilová PPlatoš J(2024)Overlapping community detection in weighted networks via hierarchical clusteringPLOS ONE10.1371/journal.pone.031259619:10(e0312596)Online publication date: 28-Oct-2024
https://doi.org/10.1371/journal.pone.0312596
Batista ADos Santos A(2024)A Survey on Resilience in Information Sharing on Networks: Taxonomy and Applied TechniquesACM Computing Surveys10.1145/365994456:12(1-36)Online publication date: 20-Apr-2024
https://dl.acm.org/doi/10.1145/3659944
Saxena AFletcher GPechenizkiy M(2024)FairSNA: Algorithmic Fairness in Social Network AnalysisACM Computing Surveys10.1145/365371156:8(1-45)Online publication date: 26-Apr-2024
https://dl.acm.org/doi/10.1145/3653711
Ni LXu HZhang YLuo WHuang YSheng V(2024)Local Overlapping Spatial-aware Community DetectionACM Transactions on Knowledge Discovery from Data10.1145/363470718:3(1-21)Online publication date: 12-Jan-2024
https://dl.acm.org/doi/10.1145/3634707
Govind APoorthuis ADerudder B(2024)Delineating Neighborhoods: An Approach Combining Urban Morphology with Point and Flow DatasetsGeographical Analysis10.1111/gean.1239456:4(700-722)Online publication date: 7-Mar-2024
https://doi.org/10.1111/gean.12394
Guo KChen DHuang QLi FGuo CWu DLiu XChen K(2024)Privacy-Preserving Multi-Label Propagation Based on Federated LearningIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.330998811:1(886-899)Online publication date: Jan-2024
https://doi.org/10.1109/TNSE.2023.3309988
Guan JChen BHuang X(2024)Community Detection via Autoencoder-Like Nonnegative Tensor DecompositionIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2022.320190635:3(4179-4191)Online publication date: Mar-2024
https://doi.org/10.1109/TNNLS.2022.3201906
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents