Source-linked AI summary
Empirical Comparison of Algorithms for Network Community Detection
Jure Leskovec, Kevin J. Lang, Michael W. Mahoney
TL;DR
Community detection in large real-world networks relies on objectives and approximate algorithms whose outputs may be biased relative to intuitive communities. This paper systematically compares objectives and algorithm classes across network sizes, finding that behavior varies by graph type and that aggressive score optimization can produce unintuitive clusters.
Problem
Community detection must approximate typically NP-hard objectives, but algorithms can return systematically biased clusters whose properties differ across methods and graph types.
Method
The paper empirically compares more than 40 networks, 12 community-quality objectives, and 8 approximation-algorithm classes using a size-resolved optimization framework.
Results
Conductance and related bi-criterion objectives behave differently across graph types, whereas modularity and other single-criterion objectives behave qualitatively similarly.
Takeaways & Limitations
Aggressive conductance optimization can yield disconnected or barely connected clusters, while approximate optimization may produce more compact and intuitive communities.
Takeaways & Limitations
Good compact communities should have external-to-internal conductance ratios ideally below 1.0, but the evaluated algorithms do not explicitly optimize internal cuts.
Abstract
from arXiv · showhide
Detecting clusters or communities in large real-world graphs such as large social or information networks is a problem of considerable interest. In practice, one typically chooses an objective function that captures the intuition of a network cluster as set of nodes with better internal connectivity than external connectivity, and then one applies approximation algorithms or heuristics to extract sets of nodes that are related to the objective function and that "look like" good communities for the application of interest. In this paper, we explore a range of network community detection methods in order to compare them and to understand their relative performance and the systematic biases in the clusters they identify. We evaluate several common objective functions that are used to formalize the notion of a network community, and we examine several different classes of approximation algorithms that aim to optimize such objective functions. In addition, rather than simply fixing an objective and asking for an approximation to the best cluster of any size, we consider a size-resolved version of the optimization problem. Considering community quality as a function of its size provides a much finer lens with which to examine community detection algorithms, since objective functions and approximation algorithms often have non-obvious size-dependent behavior.
1. INTRODUCTION
The paper examines how community objectives and approximation algorithms identify clusters in large networks, emphasizing their systematic biases and size-dependent behavior. It evaluates many methods rather than seeking a universally best definition or algorithm.
- Motivation: Community detection seeks node groups with stronger internal than external connectivity, but exact objective optimization is typically NP-hard.Heuristics and approximation algorithms are therefore used to obtain interpretable communities.
- Motivation: Approximation methods can be systematically biased, with spectral methods favoring compact but less-separated clusters and other methods favoring better separation.Performance also varies across graph types, including low-dimensional manifolds and expanders.
- Study design: The study compares more than 40 networks, 12 community-quality objectives, and 8 classes of approximation algorithms.Its goal is to understand structural properties and biases rather than identify one universally best method.
- Study design: The evaluation includes empirical analyses of objective functions and algorithms, alongside questions about recoverable and meaningful communities in very large graphs.The paper also considers whether existing algorithms are sufficiently powerful to recover interesting communities.
- Study design: The size-resolved formulation approximates the best cluster separately at every possible size instead of optimizing for an unrestricted size or a fixed partition.This exposes non-obvious size-dependent behavior in objectives and approximation algorithms.
- Study design: The paper compares spectral-based Local Spectral with flow-based Metis+MQI to examine clusters produced by distinct computational paradigms.These methods are introduced as an initial structural comparison before broader analyses.
2. RELATED WORK AND BACKGROUND
The background connects community detection to connectivity-based definitions, established algorithms, and the network community profile. The NCP measures the best community quality at each size, enabling structural comparisons across networks and methods.
- Related work: Prior work formalizes communities using internal-versus-external connectivity, conductance-based bicriteria, flow ideas, and edge-counting rules.These approaches operationalize the intuition that community members interact more strongly with one another than with the rest of the network.
- Related work: Modularity evaluates internal connectivity against a randomized null model and became influential in community-detection research.The cited related work also includes betweenness-based boundary detection.
- Related work: The study builds on scalable local spectral methods, near-linear-time heuristics, and broader reviews of community detection.These lines of work address community finding in very large graphs from complementary perspectives.
- Evaluation setting: The evaluation models networks as undirected graphs and spans over 100 social and information networks ranging from tens to millions of nodes.The corpus covers networks with sizes from tens of nodes and scores of edges to millions of nodes and tens of millions of edges.
- Background: Conductance measures a cluster’s boundary relative to its volume, with lower values indicating more community-like sets.The paper primarily uses conductance while also considering other community-quality measures.
- Background: The network community profile defines Φ(k) as the minimum community score among all node sets of size k, for sizes up to half the network.This makes community quality explicitly size resolved.
- Background: For a four-node example, set B has the best conductance, while sets D and D+E are best at sizes 3 and 6.These examples illustrate how the profile selects the best-scoring set separately at each size.
- Background: The NCP’s magnitude and shape characterize how strongly communities are expressed across size scales and provide a basis for comparing detection methods.The paper uses NCP plots and related structural metrics to study how cluster properties depend on size.
3. COMPARISON OF ALGORITHMS
The comparison evaluates conductance quality alongside structural properties across spectral, flow-based, and heuristic community-detection methods. Results expose size-dependent trade-offs: Metis+MQI often finds better cuts, while Local Spectral produces more compact clusters.
- Methods: The study compares cluster quality and structural properties using spectral Local Spectral, flow-based Metis+MQI, and heuristic methods.The experiments generate candidate clusters of varied sizes and examine conductance alongside internal structure.
- Spectral and flow-based methods: Local Spectral always returns connected clusters, while raw Metis+MQI can produce internally disconnected clusters that must be split into connected components.The comparison therefore uses broken-up Metis+MQI clusters alongside connected Local Spectral clusters.
- Spectral and flow-based methods: Metis+MQI generally finds lower-conductance cuts, whereas Local Spectral produces clusters with shorter internal paths and greater compactness.The conductance gap becomes clearer at intermediate sizes, while Local Spectral clusters have smaller average shortest-path lengths.
- Spectral and flow-based methods: At small sizes Metis+MQI tends to have a slightly better external-to-internal conductance ratio, but at larger sizes Local Spectral has the advantage.The ratio compares the conductance of the external cut with the best internal cut.
- Size-dependent behavior: Clusters below approximately 100 nodes are often compact and well separated, whereas larger clusters are harder to separate than to split internally.The paper reports that community-like sets with stronger internal than external connectivity are uncommon at large size scales.
- Other algorithms: Leighton-Rao resembles Local Spectral for connected sets and Metis+MQI for possibly disconnected sets at small to medium scales, but performs much worse at large scales.The large-scale degradation is attributed to expander-like cores in large real networks, while Graclus and Dendrogram produce compact clusters similar to Local Spectral.
4. COMPARISON OF OBJECTIVE FUNCTIONS
The paper compares community-quality objectives across cluster sizes, showing broadly similar size-dependent behavior but important differences in which cluster sizes and structures each score favors.
- Algorithmic cluster structure: Figure 3 contrasts compact Local Spectral clusters with more sprawling Metis+MQI clusters, which have larger diameter and better conductance at roughly 500 nodes.The Local Spectral method has difficulty pushing probability mass along long extended paths.
- Size-resolved behavior: The size-resolved analysis finds clusters up to about 100 nodes become progressively more community-like, whereas larger clusters become less community-like across eight scores.The scores reward internal edges and penalize external edges, producing a shared nonmonotonic trend.
- Objective-specific preferences: Flake-ODF prefers larger clusters, while Maximum-ODF favors small clusters and becomes nearly flat above several hundred nodes.The distinction arises because Maximum-ODF penalizes the worst-case node, whereas Flake-ODF counts nodes whose internal degree is not greater than their external degree.
- Objective-specific preferences: Internal Density peaks around clusters of 10 nodes and then rapidly approaches 1, indicating that larger clusters become progressively sparser by this measure.The cut ratio score also fluctuates substantially for large clusters, reflecting high variation in the number of edges leaving similarly sized clusters.
- Correlated objectives: Conductance, expansion, normalized cut, and Average-ODF exhibit similar behavior and generally identify practically the same clusters.Evaluating these scores on conductance-optimized clusters leaves the plot shape essentially unchanged, indicating high correlation.
- Objective assessment: The experiments question Internal Density and Maximum-ODF as community scores, while high variance makes the cut ratio less preferable.The paper reports that conductance, expansion, normalized cut, and Average-ODF give similar best-scoring clusters.
- Objective behavior across graphs: Conductance and related bi-criterion objectives behave differently across graph types, whereas modularity and other single-criterion objectives behave more similarly.This comparison spans low-dimensional graphs, expanders, and large real-world social and information networks.
5. COMPUTING LOWER BOUNDS
The paper computes theoretical lower bounds to assess how closely approximate community-detection algorithms approach optimal cuts across size scales. Spectral bounds apply to cuts of any balance, whereas SDP bounds apply to equal-volume cuts.
- Approximate algorithms provide only upper bounds on the best clusters, so theoretical lower bounds are used to assess their quality.The bounds help determine how close extracted clusters are to the true optimum, which is generally intractable to compute.
- The spectral lower bound applies to cuts of any balance, while spectral embeddings can be rounded into cuts that provide upper bounds at different sizes.The embedding places the graph on a line for subsequent cut construction.
- The SDP lower bound targets cuts that partition the graph into two sets of exactly equal volume.Its matrix formulation imposes unit diagonal, volume-balance, and positive-semidefinite constraints.
- SDP embeddings represent equal-volume cut structure on a hypersphere, which can likewise be rounded to obtain actual cuts.The resulting cuts can be compared with the lower bound at perfect volume balance.
- Modularity behaves differently from conductance: partitions of roughly half the network tend to achieve the best modularity.The modularity curves do not show particularly interesting nonmonotonic trends.
- The lower bounds show that partitioning algorithms perform well across size scales and that best conductance clusters can greatly outperform half-network cuts.The true conductance curve lies below the algorithmic upper bounds but above the lower-bound curves.
- For large networks, the ratio between SDP and spectral lower bounds is high, indicating that good clusters tend to be relatively small rather than half-network partitions.Small networks show the opposite pattern, with lower ratios and stronger conductance near larger partitions.
6. CONCLUSION
The paper systematically compares community-detection methods, objectives, and algorithms across networks and size scales. It finds that algorithms often approach theoretical bounds, but performance and metric behavior vary substantially by network and objective.
- Across a wide range of methods, algorithms generally optimize community scores well over multiple size scales and obtain clusters close to theoretical lower bounds.
- Some network classes cause particular algorithms to perform sub-optimally, so community-detection performance is not uniform across networks.
- Many objectives favor very small clusters, whereas metrics such as modularity exhibit qualitatively different behavior.
- Aggressive conductance optimization can produce disconnected or barely connected clusters that conflict with intuitive notions of communities.
- Approximate optimization introduces systematic bias that can trade boundary conductance against internal compactness, sometimes producing more intuitive clusters.