Source-linked AI summary
Community detection and graph partitioning
M. E. J. Newman
TL;DR
Community inference has promising, mathematically principled methods, but searching all group assignments is computationally challenging. This paper maps two inference methods to minimum-cut partitioning and adapts Laplacian spectral partitioning; the resulting algorithm rivals previous methods in speed and result quality.
Problem
Community inference methods have strong practical results and mathematical foundations, while maximizing over exponentially many group assignments is infeasible for all but the smallest networks.
Source: §I · p. 1Method
The paper maps stochastic block model and degree-corrected inference to minimum-cut partitioning, then adapts Laplacian spectral partitioning to find candidate community divisions.
Source: §I · p. 1, §II · p. 2, B. Degree-corrected block model · p. 3Results
The adapted spectral algorithm's result quality and speed rival the best previous methods, and it identifies most vertices correctly across a large portion of the tested parameter space.
Source: §I · p. 1, §III · pp. 4–5Takeaways & Limitations
The mapping allows well-understood graph-partitioning heuristics to be applied directly to maximum-likelihood community detection.
Source: §II · p. 3
Abstract
from arXiv · showhide
Many methods have been proposed for community detection in networks. Some of the most promising are methods based on statistical inference, which rest on solid mathematical foundations and return excellent results in practice. In this paper we show that two of the most widely used inference methods can be mapped directly onto versions of the standard minimum-cut graph partitioning problem, which allows us to apply any of the many well-understood partitioning algorithms to the solution of community detection problems. We illustrate the approach by adapting the Laplacian spectral partitioning method to perform community inference, testing the resulting algorithm on a range of examples, including computer-generated and real-world networks. Both the quality of the results and the running time rival the best previous methods.
I. INTRODUCTION
Community detection is subtle and computationally challenging, and statistical inference methods have attracted interest for their strong practical results and mathematical foundations. The paper maps two inference methods to minimum-cut partitioning and demonstrates a spectral community-detection algorithm.
I. INTRODUCTION
- Community detection is computationally challenging and connects to machine learning, signal processing, and spin-glass theory.Statistical inference methods have drawn particular interest for strong results, mathematical foundations, and, in some cases, provable optimality.Source: §I · p. 1
- The paper maps inference methods based on the stochastic block model and its degree-corrected variant to minimum-cut graph partitioning.This mapping makes available graph-partitioning methods applicable to community detection.Source: §I · p. 1
- An adapted Laplacian spectral method produces community-detection results competitive with the best available algorithms in both speed and quality.Source: §I · p. 1
II. LIKELIHOOD MAXIMIZATION FOR THE STOCHASTIC BLOCK MODEL
For the stochastic block model, community detection can be expressed as likelihood maximization over group assignments, but the assignment space grows exponentially. Reversing the optimization order turns fixed-size assignments into minimum-cut problems, after which profile likelihood selects among candidate group sizes.
II. LIKELIHOOD MAXIMIZATION FOR THE STOCHASTIC BLOCK MODEL
- Directly searching all group assignments remains infeasible for all but the smallest networks because their number grows exponentially.Source: §II · p. 2
- With model parameters fixed, maximizing over group labels is equivalent to minimum-cut partitioning; optimizing the remaining parameter is a simple one-parameter step.This reverses the usual order of maximizing likelihood over parameters before group assignments.Source: §II · p. 2
- Holding group sizes fixed removes the unknown γn1n2 term, leaving cut-size minimization for divisions of those sizes.The full objective also includes a penalty favoring equal-sized groups, similar but not identical to ratio cut.Source: §II · p. 2
- Profile likelihood selects the best candidate among the n+1 solutions produced by considering each possible group-size split.The model considers two communities with different within- and between-group connection rates; its Poisson version is preferred for simpler analysis and is indistinguishable from the common version for sufficiently sparse networks.Source: §II · pp. 1–3
- The approach reduces exponentially many assignments to n+1 candidate solutions indexed by group size, each obtainable through standard minimum-cut partitioning.Well-studied partitioning heuristics can therefore be applied directly to maximum-likelihood community detection.Source: §II · p. 3
A. Spectral algorithm
The spectral algorithm approximates fixed-size minimum-cut divisions using the graph Laplacian's Fiedler vector. One vector calculation yields candidate splits across all group sizes, and profile likelihood selects the approximate maximum-likelihood division.
A. Spectral algorithm
- The Fiedler vector, the graph Laplacian eigenvector for the second-smallest eigenvalue, provides an approximate minimum-cut division into specified group sizes.Vertices with the largest vector elements are assigned to the first group; the remainder form the second.Source: A. Spectral algorithm · p. 3
- Although it approximates rather than guarantees the global minimum cut, the method gives good answers under commonly occurring conditions.Source: A. Spectral algorithm · p. 3
- A single Fiedler-vector calculation yields all n+1 candidate divisions, and the highest profile-likelihood score identifies the approximate maximum-likelihood split.The algorithm sorts vector elements and considers each possible cut between them.Source: A. Spectral algorithm · p. 3
B. Degree-corrected block model
The degree-corrected model modifies expected edge counts to account for broad degree distributions, then reduces inference to a generalized minimum-cut problem. A spectral approximation uses a degree-weighted eigensystem and profile likelihood to select a partition.
B. Degree-corrected block model
- The standard block model performs poorly on most real-world networks because it misses their broad degree distributions.Source: B. Degree-corrected block model · p. 3
- Degree correction replaces each expected edge count ωij with kikjωij, where ki and kj are vertex degrees.Source: B. Degree-corrected block model · p. 3
- The resulting objective is a generalized minimum-cut problem with a κ1κ2 penalty that favors balanced groups.Source: B. Degree-corrected block model · p. 3
- With κ1 and κ2 fixed, the spectral approximation uses the second eigenvector of Lv = λDv and selects among n + 1 partitions by profile likelihood.Source: B. Degree-corrected block model · p. 3
III. RESULTS
On synthetic networks, spectral inference identifies group sizes and classifies most vertices correctly across much of the tested parameter space, failing below the detectability threshold. It also closely matches accepted divisions in two real-world networks, with running time comparable to leading competitors.
III. RESULTS
- The profile likelihood peaks at the correct group sizes, and the algorithm classifies most vertices correctly down to near the detectability threshold before failing below it.Source: Figure 1 · p. 4, §III · p. 4
- The spectral algorithm's divisions of Zachary’s karate club and the political-blog network closely match their accepted communities.Source: Figure 2 · p. 4, §III · p. 4
- The candidate-division scan takes O(m) time, and total running time scales as m times the typically small number of Lanczos iterations, comparable to the best competing algorithms.Source: §III · pp. 4–5
IV. CONCLUSIONS
Maximum-likelihood community detection can be reduced to searching a small family of minimum-cut solutions. This mapping permits the use of established partitioning heuristics, including an adapted Laplacian spectral method.
IV. CONCLUSIONS
- Maximum-likelihood community detection reduces to searching a small family of candidate partitions, each solving a minimum-cut problem.Source: §IV · p. 5
- The reduction lets community detection use well-understood graph-partitioning heuristics.Source: §IV · p. 5
- The paper illustrates the mapping by adapting Laplacian spectral partitioning for likelihood maximization.Source: §IV · p. 5