Source-linked AI summary
Spectral methods for network community detection and graph partitioning
M. E. J. Newman
TL;DR
The paper asks whether modularity maximization, likelihood-based community detection, and normalized-cut partitioning are fundamentally distinct network-structure problems. It derives spectral formulations for all three and shows that, under the chosen spectral approximation, they use the same algorithm and produce identical results for the community-detection methods. Applications to computer-generated and real-world networks indicate good practical performance.
Problem
Community detection and normalized-cut partitioning involve difficult optimization problems, motivating comparison of their spectral formulations.
Method
The paper derives spectral algorithms for modularity maximization, degree-corrected block-model likelihood maximization, and normalized-cut partitioning using network-matrix eigenvectors.
Results
The three spectral algorithms are identical within the paper’s formulation, and modularity and maximum-likelihood community detection give identical results.
Takeaways & Limitations
Within this spectral approximation, the three problems have no difference, while the method performs well on computer-generated and real-world networks.
Abstract
from arXiv · showhide
We consider three distinct and well studied problems concerning network structure: community detection by modularity maximization, community detection by statistical inference, and normalized-cut graph partitioning. Each of these problems can be tackled using spectral algorithms that make use of the eigenvectors of matrix representations of the network. We show that with certain choices of the free parameters appearing in these spectral algorithms the algorithms for all three problems are, in fact, identical, and hence that, at least within the spectral approximations used here, there is no difference between the modularity- and inference-based community detection methods, or between either and graph partitioning.
I. INTRODUCTION
Community structure is a major network property, but detecting it is computationally difficult. The paper examines spectral approaches to modularity, likelihood-based community detection, and normalized-cut partitioning, showing that their algorithms coincide.
- Community structure consists of densely connected node groups with sparser connections between groups.
- Modularity maximization and maximum-likelihood inference are widely used community-detection approaches based on optimizing objective functions over network divisions.
- These optimization problems are generally computationally hard, so practical methods use polynomial-time heuristics to find approximate optima.
- The paper formulates modularity and likelihood community detection as spectral algorithms using eigenvectors of the normalized Laplacian matrix.
- The resulting spectral algorithms for modularity, likelihood inference, and normalized-cut graph partitioning are identical within the paper’s spectral formulation.
- The paper derives the three algorithms in Sections II–IV and evaluates them on computer-generated and real-world networks in Section V.
II. MODULARITY MAXIMIZATION
The paper rewrites two-group modularity maximization using spin variables, relaxes their discrete constraints, and solves the relaxed problem spectrally. A degree-weighted hyperellipsoidal constraint yields a generalized eigenvector method whose rounded second eigenvector partitions the network.
- Modularity measures the fraction of within-group edges minus the expected fraction under a randomized null model.
- The configuration model preserves observed vertex degrees while placing edges randomly in other respects, providing modularity’s common null model.
- For two groups, each vertex receives an Ising spin: +1 for group 1 and −1 for group 2.
- The modularity matrix is symmetric and has rows and columns summing to zero.
- The original spin optimization is NP-complete in general, motivating a spectral optimization strategy.
- Relaxing discrete spins to real values simplifies optimization, but a constraint is required to prevent uninformative divergence of the variables.
- The standard spherical relaxation is replaced by a hyperellipsoid whose coefficients are set to the observed vertex degrees, ai = ki.
- The relaxed problem is solved exactly with a Lagrange multiplier, producing a generalized eigenvector equation involving the degree matrix D.
III. STATISTICAL INFERENCE
Statistical inference formulates community detection as maximum-likelihood optimization under stochastic block models. Its spectral approximation becomes identical to modularity maximization, using an eigenvector of the normalized Laplacian under the stated assumptions.
- Statistical inference: Stochastic block models provide a mathematically grounded framework for community inference by fitting a generative model to observed network data.The standard model generates synthetic networks; community detection fits the model using maximum likelihood.
- Model limitations: The standard stochastic block model often fits real networks poorly because it produces Poisson degree distributions unlike those typically observed.The degree-corrected block model addresses this mismatch by accommodating non-Poisson degree distributions.
- Spectral formulation: Degree-corrected block-model likelihood maximization is computationally difficult but can be approximated with spectral methods identical to those used for modularity maximization.The degree-corrected model incorporates desired vertex degrees and group-dependent parameters.
- Spectral formulation: Under the two-group assortative model, maximum likelihood becomes an optimization involving A − νkk^T, closely paralleling the modularity matrix.Here ωin > ωout, and ν depends on the within- and between-group parameters.
- Parameter independence: The unknown parameter ν does not affect the resulting eigenvector equation, which matches the maximum-modularity formulation.The constraint k^T s = 0 removes ν from the equation.
- Result: The optimal division is obtained from the signs of the normalized-Laplacian eigenvector associated with the second most positive eigenvalue.Within the spectral approximation, maximum modularity and maximum likelihood give identical results.
IV. GRAPH PARTITIONING
Normalized-cut partitioning minimizes a degree-normalized cut and admits a standard spectral relaxation. With the common choice of degree-weighted group variables, its algorithm becomes the same as the community-detection algorithms based on modularity or maximum likelihood.
- Normalized-cut objective: Normalized cut minimizes R/κ1κ2, favoring groups with equal total degree rather than equal vertex counts.This normalization is particularly useful for networks with broad degree distributions.
- Spectral relaxation: The normalized-cut problem is hard to solve exactly, but approximate solutions can be obtained using a standard spectral method.The method defines degree-weighted index variables rather than simple ±1 group labels.
- Spectral relaxation: Minimizing normalized cut is equivalent to maximizing s^TAs subject to the degree-based constraints on the group variables.The matrix formulation follows from expressing the cut size in terms of the adjacency and degree matrices.
- Eigenvector solution: The relaxed solution is the eigenvector corresponding to the second-largest eigenvalue, because the leading eigenvector fails the required constraint.The leading eigenvector is 1, which does not satisfy the zero-degree-weighted-sum condition.
- Rounding: Rounding by vertex signs usually gives good partitions when group degree totals are roughly equal, and results are typically insensitive to the exact threshold.The discrete group values are then approximately ±1.
- Equivalence: With the common normalized-cut choice, the algorithm is the same as the modularity-maximization and maximum-likelihood community-detection algorithms.This establishes the paper’s claimed equivalence across the three spectral formulations.
V. EXAMPLES
The spectral algorithm detects planted and real-world two-community structure, remaining effective across unequal group sizes and down to the detectability threshold. Its performance is essentially identical to a standard modularity-matrix spectral method in the tested block-model networks, while real examples reveal occasional higher-eigenvector structure.
- Stochastic block-model tests: The second eigenvector’s zero crossing identifies planted groups across a wide range of unequal community sizes.The crossing occurs near the planted group-size boundary in stochastic block-model networks.
- Stochastic block-model tests: Changing the cut point has little effect because the eigenvector curve passes nearly vertically through zero.This makes the resulting division insensitive to moderate shifts in the threshold.
- Stochastic block-model tests: For equally sized groups, the community signal weakens as planted structure decreases and disappears at the detectability threshold.Below that threshold, the paper states that all algorithms must fail to detect the structure.
- Stochastic block-model tests: The algorithm performs better than random guessing down to the detectability threshold, and its results are essentially identical to the standard modularity spectral algorithm.The comparison uses n = 10 000, equally sized groups, and mean degree 50.
- Real-world networks: The method recovers clear two-way divisions in dolphin social and political-book networks.The eigenvector steps cross zero at points producing divisions aligned with the networks’ recognized community structure.
- Real-world networks: In the political-weblog network, the accepted division appears in the third rather than the second normalized-Laplacian eigenvector.The second eigenvector is localized around a few high-degree vertices rather than correlated with the communities.
VI. CONCLUSIONS
The paper shows that spectral algorithms for three network problems are identical within its formulation and reports good practical performance on generated and real-world networks. It identifies extension beyond two communities as a clear direction for future work.
- Main conclusion: Modularity maximization, degree-corrected block-model likelihood maximization, and normalized-cut bisection use the same spectral algorithm.The algorithm computes the leading normalized-Laplacian eigenvector and divides vertices by the signs of its elements.
- Main conclusion: Applications to computer-generated and real-world networks indicate that the algorithm performs well in practice.The paper presents these applications as evidence across a range of network types.
- Future extension: Generalizing the calculations to networks with more than two groups or communities is identified as a clear extension.