Metrics for Community Analysis: A Survey
arXiv:1604.03512
Abstract
Detecting and analyzing dense groups or communities from social and information networks has attracted immense attention over last one 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 out to be even complicated due to the fact that communities emerge in the network in various forms - disjoint, overlapping, hierarchical etc. Various heuristics have been proposed depending upon 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. There arises a need for an organized and detailed survey of the metrics proposed with respect to community detection and evaluation. In this survey, we present a comprehensive and structured overview 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-world networks to present a comparative analysis of these metrics in measuring the goodness of the underlying community structure.
arXiv comment7 Figures, 8 tables
References in corpus (58)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Fast algorithm for detecting community structure in networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Finding community structure in networks using the eigenvectors of matrices
- Maps of random walks on complex networks reveal community structure
- Resolution limit in community detection
- Comparing community structure identification
- Analysis of weighted networks
- Defining and identifying communities in networks
- Community detection algorithms: a comparative analysis
- Statistical Mechanics of Community Detection
- Detecting the overlapping and hierarchical community structure of complex networks
- Finding statistically significant communities in networks
- Community structure in directed networks
- The performance of modularity maximization in practical contexts
- Modularity from Fluctuations in Random Graphs and Complex Networks
- An information-theoretic framework for resolving community structure in complex networks
- Finding local community structure in networks
- Modularity and community detection in bipartite networks
- Detect overlapping and hierarchical community structure in networks
- Mixture models and exploratory analysis in networks
- Limits of modularity maximization in community detection
- Fuzzy communities and the concept of bridgeness in complex networks
- Module identification in bipartite and directed networks
- Size reduction of complex networks preserving modularity
- Average path length in random networks
- Average path length in uncorrelated random networks with hidden variables
- A Local Method for Detecting Communities
- Characterizing the community structure of complex networks
- Spectral Measures of Bipartivity in Complex Networks
- Normalized Mutual Information to evaluate overlapping community finding algorithms
- Evaluating Local Community Methods in Networks
- LinkRank: Finding communities in directed networks
- Local modularity measure for network clusterizations
- Identifying "communities" within energy landscapes
- Significant Scales in Community Structure
- Quantifying and identifying the overlapping community structure in networks
- Motif-based communities in complex networks
- When are networks truly modular?
- Deciphering Network Community Structure by Surprise
- Detecting communities using asymptotical Surprise
- Hierarchical Clustering Based on Mutual Information
- Surprise maximization reveals the community structure of complex networks
- Z-score-based modularity for community detection in networks
- Modularity measure of networks with overlapping communities
- Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
- Comparison of Communities Detection Algorithms for Multiplex
- Axioms for graph clustering quality functions
- Multi-resolution community detection based on generalized self-loop rescaling strategy
- On the evaluation potential of quality functions in community detection for different contexts
- SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization
- Extending modularity by capturing the similarity attraction feature in the null model
- Finding compact communities in large graphs