Source-linked AI summary
Metrics for Community Analysis: A Survey
Tanmoy Chakraborty, Ayushi Dalmia, Animesh Mukherjee, Niloy Ganguly
TL;DR
Community detection is difficult because communities have no universally accepted definition, can take multiple forms, and require metrics for both discovery and evaluation. The paper surveys state-of-the-art metrics across community structures, examines their use in detection and evaluation, and compares them on synthetic and real-world networks. Its empirical conclusion identifies Permanence and extended modularity density (QMD_ov) as the most appropriate measures for disjoint and overlapping community detection, respectively.
Problem
Community analysis lacks a unified account of metrics for detecting and evaluating diverse community structures, while proposed quality functions may yield contradictory results.
Method
The paper surveys state-of-the-art detection and evaluation metrics across community types and compares them through experiments on synthetic and real-world networks.
Results
Permanence and extended modularity density (QMD_ov) are reported as most appropriate for disjoint and overlapping community detection, respectively.
Takeaways & Limitations
Bringing metrics together supports understanding their evolution and selecting a metric appropriate to the community-analysis context.
Takeaways & Limitations
Modularity is subject to resolution-limit and degeneracy problems, including exponentially many structurally diverse near-optimal partitions.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
Community analysis is difficult because communities lack a universal definition, vary in structure, and require metrics for both detection and evaluation. This survey organizes metrics across community types and compares their performance on synthetic and real-world networks.
- 1. INTRODUCTION: Communities may be disjoint, overlapping, or hierarchical, and community analysis involves both detecting structure and evaluating its appropriateness.The absence of a universally accepted community definition has produced multiple interpretations of community structure.
- 1. INTRODUCTION: Quality metrics are challenging to formulate because researchers disagree about what constitutes a community.Many proposed functions quantify properties selected by their authors to evaluate community goodness.
- 1. INTRODUCTION: Existing surveys mainly treat non-overlapping and overlapping detection separately, leaving the metrics for algorithm design and quality evaluation insufficiently unified.Different quality functions can produce contradictory results, while network and community properties vary across applications.
- 1. INTRODUCTION: The survey brings together detection and evaluation metrics for disjoint, overlapping, fuzzy, and local communities.It covers metrics including Modularity, Permanence, Surprise, Significance, Flex, Normalised Mutual Information, Purity, Rand Index, and F-Measure.
- 1. INTRODUCTION: The survey is organized around optimization metrics for community detection, measures for evaluating detected structures, and comparative performance analysis.The comparison uses experiments on synthetically generated and real-world networks.
2. METRICS FOR DISCOVERING COMMUNITY STRUCTURE
Community-detection metrics quantify the quality of candidate communities or partitions, guiding optimization when the number of possible communities is prohibitively large. The survey organizes topological, model-based, and modularity-related measures while noting important modularity limitations.
- Community detection algorithms optimize goodness metrics because graphs have exponentially many possible communities and enumerating them is NP-Complete.These metrics indicate the quality of detected communities or partitions.
- Topological scoring functions are grouped by internal connectivity, external connectivity, and combinations of internal and external connectivity.Examples include density and edge-inside measures, expansion and cut ratio, and normalized cut or out-degree-fraction measures.
- Modularity compares the fraction of within-partition edges in the original graph with that in a null graph, usually preserving the degree distribution.Its value lies between -1 and 1, and higher values indicate stronger community structure.
- Separability measures internal relative to external edges, density measures realized internal edges among possible edges, and cohesiveness measures resistance to internal splitting.Clustering coefficient, volume, and edges cut provide additional topological views of community quality.
- Modularity has been extended for weighted and directed graphs and modified through similarity-, max-min-, diffusion-, and local formulations.Local modularity computes expected within-module edges using the module and neighboring modules rather than the full graph.
- Modularity has a resolution limit that can hide modules below a network- and interconnectedness-dependent scale, even when those modules are unambiguously defined.It also has a degeneracy problem involving exponentially many structurally diverse near-optimal partitions.
3. METRICS FOR COMMUNITY EVALUATION
Community evaluation metrics compare detected structures with known ground-truth communities, using measures for non-overlapping and overlapping structures. These metrics differ in symmetry, chance correction, topology awareness, and sensitivity to community-count effects.
- Ground-truth validation metrics measure the resemblance between detected and actual community structures when the ground truth is known.
- Purity assigns each detected community its most frequent ground-truth label, but is asymmetric and can be biased by community number and sizes.
- Purity can equal 1 when every node forms its own community, whereas inverse purity favors solutions with few large communities; F-measure balances both versions.
- Rand Index measures pairwise agreement using true-positive, true-negative, false-positive, and false-negative decisions, but can be misleading because of bias.
- Adjusted Rand Index applies chance correction and is often preferred because it seems less sensitive to the number of communities.
- NMI ranges from 0 to 1 but is not a true metric because it does not satisfy the triangle inequality, whereas VI does satisfy it and equals 0 for perfect agreement.
4. EXPERIMENTS AND RESULTS
The experiments compare community scoring metrics on synthetic and real-world networks with known non-overlapping and overlapping ground-truth structures. Results assess how well scoring-based rankings reproduce validation-based rankings, revealing strong but network- and validation-dependent differences among metrics.
- Datasets: The study evaluates scoring functions on synthetic and real-world networks with known non-overlapping and overlapping ground-truth communities.Synthetic networks use the LFR benchmark, while real-world datasets include football, railway, coauthorship, LiveJournal, Amazon, and YouTube networks.
- Experimental setup: The experimental framework ranks detection algorithms separately by scoring metrics and by validation metrics, then compares the resulting rankings.Validation measures for non-overlapping communities include VI, NMI, ARI, F-measure, and purity.
- Non-overlapping communities: Permanence is generally the strongest scoring metric on LFR networks with non-overlapping communities, followed by modularity, while conductance consistently performs worst.Communitude is usually third, followed by modularity density and surprise, with some exceptions where modularity outperforms permanence.
- Non-overlapping communities: On real-world non-overlapping networks, the best metric varies: modularity density leads football with average rank correlation 0.37, whereas permanence leads railway and coauthorship with 0.37.For coauthorship, permanence is followed by significance, communitude, and conductance, each at 0.27; permanence is reported as strongest on average across networks and validation measures.
- Overlapping communities: For overlapping LFR networks, QMD_ov is best in most cases, followed by flex and QS_ov.The experiments vary n, µ, Om, and On when analyzing overlapping community structures.
- Overlapping communities: GEI-based validation produces substantially different trends from the other validation measures, suggesting GEI may not be a good performance indicator for community evaluation.The comparison concerns overlapping-community scoring metrics on LFR networks.
5. CONCLUSION
The review brings community-detection and evaluation metrics together, finding that their suitability varies by community type while identifying unresolved questions about choosing detection settings and metric behavior.
- The review consolidates metrics used to detect and evaluate disjoint, overlapping, and other community structures.It aims to help readers understand metric evolution and select metrics in the right context.
- Newman-Girvan’s modularity was the most popular and widely accepted metric and provided a foundation for other metrics.
- Permanence and extended modularity density (QMD_ov) were identified as most appropriate for measuring disjoint and overlapping community quality, respectively.
- No metric or algorithm can currently detect disjoint and overlapping structures according to network topology without knowing the underlying community type.
- The literature remains limited on network-noise effects and on significance for overlapping structures and goodness metrics beyond modularity.
6. METRICS FOR NON-OVERLAPPING COMMUNITIES
The section presents axioms for community-quality functions, specifying locality, continuity, permutation invariance, scale invariance, richness, and monotonicity as design properties.
- Permutation invariance requires quality to depend on edge weights rather than node identities.
- Scale invariance requires uniform scaling of edge weights to preserve the ordering of community qualities.
- Richness requires every non-trivial partition to be optimal for some graph under the quality function.
- Monotonicity requires quality not to decrease when within-community edges improve and between-community edges weaken.
- Locality requires a community’s contribution to total quality to depend only on nodes in its neighborhood.
- Continuity requires small graph changes to produce small changes in community quality.
7. OTHER METRICS FOR COMMUNITY DETECTION
Community detection metrics address local, multipartite, bipartite, and anti-community structures through specialized objective functions and modularity variants. These measures target structural properties such as internal density, external connectivity, and bipartite density.
- Local community detection: Local community detection focuses on communities surrounding a particular node when the complete network is unavailable.This setting is called the local community structure.
- Local community detection: Local modularity uses known connectivity within C and partial adjacency information outside C to evaluate a local community.The formulation restricts attention to boundary vertices B and uses a boundary-adjacency matrix.
- Local community detection: Alternative local objectives include subgraph modularity, density-isolation, conductance, edge-surplus, and internal density.Density-isolation is defined as fα,β(S) = mS − αcS − βnS, while edge-surplus incorporates an edge-existence probability α.
- Local community detection: Some local metrics seek to maximize internal relations and minimize external relations, while free-rider analysis identifies irrelevant subgraphs included by existing metrics.The internal relation Lin is based on average internal degree, and Lex on average external degree.
- n-partite networks: Multipartite and bipartite networks require specialized modularity measures based on null models, community densities, and vertex-type connectivity.Bipartite modularity variants address asymmetric treatment of vertex types and limitations involving the number of communities.
- n-partite networks: Bipartite modularity can be extended through new null models and density-based formulations, while anti-modularity evaluates anti-community partitioning.The density-based measure sums bipartite densities across communities, and larger QD(P) indicates a more accurate partitioning scheme.
- Anti-community detection: Optimizing anti-modularity was demonstrated experimentally to be a reasonable and reliable approach for anti-community partitioning.Anti-modularity is constructed from the matrix B = A^T A and captures vertices that belong together in anti-communities.
8. METRICS FOR COMMUNITY EVALUATION
Traditional evaluation measures can overlook network topology because they represent community structure primarily as partitions. Alternative comparisons address matching and overlap, but each has scope or metric limitations.
- Issues with traditional measures: Partition-based measures may assign the same scores to structurally different community estimates because they ignore network topology.In the example, purity, inverse purity, and F-Measure coincide for two different incorrect estimates, while ARI and NMI are 0.6 and 0.62.
- Issues with traditional measures: NMI is limited because it does not satisfy the triangle inequality except under restrictive structural conditions.The stated condition requires the compared structures to have identical community numbers and sizes.
- Overlapping-community evaluation: Figure 7 compares rank correlations among five overlapping-community scoring metrics and four validation measures under varying overlap parameters.The experiments vary the number of communities assigned to a node and the percentage of overlapping nodes in LFR networks.
- Partition matching: The Kuhn-Munkres algorithm computes the transformation-minimizing matching in O(n^3), where n is the number of parts.Figure 6 illustrates two possible matchings with different numbers of required node movements.
9. EXPERIMENTS
Experiments use LFR benchmark networks to examine metric behavior under varying network size, mixing, and overlap conditions.
- Experimental setup: The experiments vary n, mixing coefficient µ, overlapping-node percentage On, and per-node community count Om in LFR benchmark networks.Figure 7 reports results while varying Om and On.
10. SUMMARY
The survey organizes metrics for community detection and evaluation across non-overlapping and overlapping community structures. Its summary tables provide a structured reference for these metric classes.
- Metric organization: Tables I and II summarize community detection metrics for non-overlapping and overlapping community structures.The survey uses notation borrowed from the main paper’s Table I.
- Metric organization: Tables III and IV describe community evaluation metrics for non-overlapping and overlapping community structures.The tables separate evaluation measures from detection measures across the two structure types.