Source-linked AI summary
Hypothesis Testing for Automated Community Detection in Networks
Peter J. Bickel, Purnamrita Sarkar
TL;DR
The paper tackles the problem that network clustering commonly requires the number of clusters k to be known beforehand. It develops a random-matrix-based hypothesis test and recursive bipartitioning algorithm, outperforming an existing overlapping-cluster method on nine labeled Facebook networks and revealing nested structure in unlabeled networks.
Problem
Most network clustering algorithms require the number of clusters k to be specified in advance, although determining community structure is important across network applications.
Method
The paper tests an Erdős-Rényi one-cluster null using the limiting distribution of a centered and scaled largest adjacency-matrix eigenvalue, then recursively bipartitions the graph.
Results
On nine real datasets with Facebook ground truth, recursive bipartitioning outperforms the existing method reported as best among state-of-the-art algorithms for finding overlapping clusters, while also revealing nested clusters in two unlabeled networks.
Takeaways & Limitations
The approach provides automatic cluster-number selection together with a multiscale view of communities with different densities nested inside larger communities.
Abstract
from arXiv · showhide
Community detection in networks is a key exploratory tool with applications in a diverse set of areas, ranging from finding communities in social and biological networks to identifying link farms in the World Wide Web. The problem of finding communities or clusters in a network has received much attention from statistics, physics and computer science. However, most clustering algorithms assume knowledge of the number of clusters k. In this paper we propose to automatically determine k in a graph generated from a Stochastic Blockmodel. Our main contribution is twofold; first, we theoretically establish the limiting distribution of the principal eigenvalue of the suitably centered and scaled adjacency matrix, and use that distribution for our hypothesis test. Secondly, we use this test to design a recursive bipartitioning algorithm. Using quantifiable classification tasks on real world networks with ground truth, we show that our algorithm outperforms existing probabilistic models for learning overlapping clusters, and on unlabeled networks, we show that we uncover nested community structure.
1 Introduction
The paper addresses automatic determination of the number of network clusters using a hypothesis-testing framework grounded in random matrix theory. The resulting recursive bipartitioning algorithm supports hierarchical structure discovery and performs well on labeled real-world networks.
- Most network clustering algorithms assume that the number of clusters k is known in advance.
- The framework naturally yields a recursive bipartitioning algorithm that produces hierarchical clustering.
- The paper uses random matrix theory to test whether a graph contains more than one cluster, avoiding reliance on a prespecified k.The null model is an Erdős-Rényi graph, and the test uses the limiting distribution of a suitably centered and scaled largest adjacency-matrix eigenvalue.
- The limiting Tracy-Widom result also holds when the edge probability p is unknown and centering and scaling use an estimate of p.
- On real-world networks with ground truth, the method outperforms an existing algorithm for learning overlapping clusters.
- The authors note that the theory applies to the dense asymptotic regime, while sparse or small graphs require experimentally obtained Bartlett-type corrections.
2 Preliminaries and Proposed Method
The paper develops a Tracy-Widom-based hypothesis test for deciding whether a network has one or multiple communities, then uses it recursively for hierarchical clustering. Bootstrap moment corrections improve finite-sample agreement with the limiting law, especially when graphs are small or sparse.
- The Hypothesis Test: The method tests whether a graph is Erdős-Rényi, representing the one-community null, to determine whether additional blocks are present.The test uses the largest eigenvalue of a suitably centered and scaled adjacency matrix.
- The Hypothesis Test: The centered adjacency matrix has extreme eigenvalues following the Tracy-Widom law after suitable shifting and scaling.The result extends the relevant random-matrix limit to the matrix formed using an estimated edge probability.
- The Hypothesis Test: Under a Stochastic Blockmodel with more than one block and diagonally dominant B, the test statistic diverges rather than following the Tracy-Widom null law.Diagonal dominance corresponds to higher within-cluster than across-cluster linkage probabilities.
- Recursive Bipartitioning: The hypothesis test is applied recursively through bipartitioning, producing a hierarchical clustering; the partitioning method itself is orthogonal to the test.The paper specifies regularized Spectral Clustering for one algorithmic step but permits other partitioning methods.
- Finite-Sample Correction: Bootstrap corrections shift and scale the statistic using estimated moments so its empirical distribution better matches the Tracy-Widom law.With 50 samples, the corrected fit is somewhat worse than with 1000 samples but not much worse.
3 Proof of Main Result
The proof establishes Tracy–Widom behavior for the centered adjacency matrix by combining Wigner-matrix results, eigenvector control, and eigenvalue comparisons. It also handles the no-self-loop setting and derives the contrasting growth of eigenvalues under community structure.
- Random-matrix inputs: The proof applies semicircle-law and edge-universality results for generalized Wigner matrices to establish Tracy–Widom behavior for extreme eigenvalues.The argument invokes prior results giving local semicircle control and necessary and sufficient conditions for the Tracy–Widom limit.
- Tracy–Widom limit: The centered Bernoulli adjacency matrix satisfies the required moment condition, yielding λ1(H) = 2 + n^-2/3 TW1 + oP(n^-2/3).The scaling adjustment contributes only a 1 + O(1/n) factor, which does not obscure the n^-2/3 Tracy–Widom scale.
- Eigenvector control: The proof extends eigenvector delocalization to the no-self-loop adjacency matrix by replacing an unavailable semicircle-law condition with an entry-wise result applicable to this setting.For this matrix, the diagonal variance terms satisfy sii = 0, so the first half of the cited condition does not hold directly.
- Eigenvalue comparison: Weyl’s interlacing inequality controls how adding a rank-one all-ones perturbation changes the ordered eigenvalues of the centered adjacency matrix.The proof treats positive and negative perturbation cases separately and uses interlacing to relate the two spectra.
- Community-structure regime: Under dense community structure, the k largest eigenvalues of E[A|Z] scale as C_i n, while adjacency fluctuations are O_P(√(n log n)).Consequently, the leading eigenvalues remain positive with high probability, and the residual leading eigenvalue grows at least proportionally to √n.
4 Experiments
Experiments show that the hypothesis test detects planted structure, while recursive bipartitioning performs well on sparse simulations and reveals nested communities in real networks.
- Simulated networks: p-values decrease as the planted cluster grows and increase as between-cluster linkage rises, matching easier detection and weaker block structure.The planted cluster size increases from thirty to one hundred, while B12 increases from 0.04 to 0.1.
- Simulated networks: Adjusted Rand Index grows with average degree, showing that recursive bipartitioning works empirically on sparse graphs despite dense-regime theory.Simulation experiments use a p-value cutoff of 0.01.
- Simulated networks: In the nested block model, recursive bipartitioning outperforms sequential Community Extraction because recursive splitting preserves smaller communities nested within larger ones.Community Extraction first extracts the community containing communities one and two, then performs poorly on the remainder.
- Facebook ego networks: On nine Facebook ego-networks, recursive bipartitioning obtains better or comparable F-measures for most networks than the comparison method.The evaluation uses manually collected networks with overlapping ground-truth circles and excludes zero-degree nodes.
- Karate Club and Political Books: For the Karate Club network, recursive bipartitioning achieves perfect clustering at p-value cutoff 0.0001, while the larger cutoff further splits one community.The dark blue group has p-value about 0.003, motivating the alternative cutoff.
- Karate Club and Political Books: On the unlabeled Political Books network, recursive bipartitioning produces six parts and reveals hierarchically nested denser subgraphs.The splits separate blue, yellow, green, and subsequent smaller clusters.
5 Discussion
The paper presents a hypothesis-test-based recursive bipartitioning method that detects block structure and produces hierarchical clusters. Experiments report strong performance on labeled networks and nested structure discovery on unlabeled networks, while clarifying the scope of those evaluations.
- Contributions: The hypothesis test provably detects whether a Stochastic Blockmodel graph contains more than one block and supports recursive bipartitioning.The test uses the largest eigenvalue of a suitably shifted and scaled adjacency matrix.
- Empirical results: On nine real datasets with ground truth, RB outperforms an existing method reported to perform best among state-of-the-art overlapping-cluster algorithms.
- Empirical results: RB uncovers nested cluster structures of varied densities in the karate club and political books networks without requiring k.These experiments are presented as matching existing interesting structure rather than demonstrating higher cluster quality.