Fast community detection by SCORE

Jiashun Jin

Source-linked AI summary

Fast community detection by SCORE

Jiashun Jin

arXiv:1211.5803v2Nov 25, 2012stat.MEcs.SIphysics.soc-ph

TL;DR

The paper addresses community detection under the degree-corrected block model, where unknown labels must be estimated despite degree heterogeneity. It proposes SCORE, which clusters entry-wise ratios of leading eigenvectors, and reports favorable empirical comparisons plus consistency under mild conditions. The method's theory assumes the number of communities is known and relies on regularity conditions concerning eigenvalue gaps.

Problem
Community detection under the DCBM is challenging because the model allows substantial degree heterogeneity while community labels remain unknown.
Method
SCORE obtains the K leading eigenvectors of the adjacency matrix, forms entry-wise ratios of the non-leading eigenvectors to the first, and clusters the resulting rows with k-means.
Results
SCORE has smaller reported error rates than competing methods on the web blogs and karate club data and is theoretically weakly consistent under regularity conditions.
Takeaways & Limitations
Degree heterogeneity can be largely removed through eigenvector ratios, avoiding direct estimation of node-level heterogeneity parameters for community detection.
Takeaways & Limitations
The analysis assumes the number of communities K is known, while unknown-K community detection is left as an unsolved problem for future work.

Abstract

from arXiv · show

Consider a network where the nodes split into $K$ different communities. The community labels for the nodes are unknown and it is of major interest to estimate them (i.e., community detection). Degree Corrected Block Model (DCBM) is a popular network model. How to detect communities with the DCBM is an interesting problem, where the main challenge lies in the degree heterogeneity. We propose a new approach to community detection which we call the Spectral Clustering On Ratios-of-Eigenvectors (SCORE). Compared to classical spectral methods, the main innovation is to use the entry-wise ratios between the first leading eigenvector and each of the other leading eigenvectors for clustering. Let $A$ be the adjacency matrix of the network. We first obtain the $K$ leading eigenvectors of $A$, say, $\hatη_1,\ldots,\hatη_K$, and let $\hat{R}$ be the $n\times (K-1)$ matrix such that $\hat{R}(i,k)=\hatη_{k+1}(i)/\hatη_1(i)$, $1\leq i\leq n$, $1\leq k\leq K-1$. We then use $\hat{R}$ for clustering by applying the $k$-means method. The central surprise is, the effect of degree heterogeneity is largely ancillary, and can be effectively removed by taking entry-wise ratios between $\hatη_{k+1}$ and $\hatη_1$, $1\leq k\leq K-1$. The method is successfully applied to the web blogs data and the karate club data, with error rates of $58/1222$ and $1/34$, respectively. These results are more satisfactory than those by the classical spectral methods. Additionally, compared to modularity methods, SCORE is easier to implement, computationally faster, and also has smaller error rates. We develop a theoretic framework where we show that under mild conditions, the SCORE stably yields consistent community detection. In the core of the analysis is the recent development on Random Matrix Theory (RMT), where the matrix-form Bernstein inequality is especially helpful.

1. Introduction.

The paper studies community detection in networks using the degree-corrected block model, which accommodates degree heterogeneity more realistically than the stochastic block model. It motivates a tractable approach because community labels are unknown and richer network models are harder to analyze.

Community detection estimates unknown labels for nodes partitioned into a small number of disjoint communities.
The paper seeks a network model that is both realistic and mathematically tractable.
The stochastic block model assumes equal expected degrees within communities and Poisson degree distributions, conflicting with power-law degree patterns in many natural networks.
The DCBM introduces a free parameter for each node's degree, allowing degree heterogeneity and greater realism.
Compared with the p∗ model and ERGM, the DCBM is presented as easier to analyze because its heterogeneity parameters are largely ancillary for community detection.

1.2. Where is the information: Spectral analysis heuristics.

The spectral heuristic identifies community information in eigenvector ratios rather than in estimated degree-heterogeneity parameters. Coordinate-wise ratios largely remove heterogeneity, and the sign of the ratio vector directly carries label information.

The sign vector of the eigenvector-ratio vector is identified as the location of the most direct community-label information.
For community detection, the degree-heterogeneity parameters are largely ancillary and need not be estimated.
The coordinate-wise ratio of the leading eigenvectors largely removes heterogeneity, with residual dependence only through overall community degree intensities.
Estimating heterogeneity for low-degree nodes can produce large errors that propagate into subsequent analyses.
The proposed SCORE procedure is motivated by this ratio-based removal of degree heterogeneity.

1.3. SCORE: A new approach to spectral community detection.

SCORE clusters nodes using ratios of leading adjacency-matrix eigenvectors, extending the two-community procedure to K communities. For two communities, the ratio vector can equivalently be thresholded, and theory supports weak consistency under regularity conditions.

For two communities, SCORE computes the coordinate-wise ratio of the second eigenvector to the first and clusters the resulting vector with k-means.
For K≥2 communities, SCORE uses the K leading eigenvectors and applies a scaling-invariant row mapping before clustering.
Because the two-community ratio is one-dimensional, k-means and hierarchical clustering are equivalent to thresholding it.
The computational cost of SCORE is dominated by obtaining the leading eigenvectors and is only slightly larger than O(n^2) for sparse social-network adjacency matrices using the power method.
Under regularity conditions, SCORE is weakly consistent, with Hamming error much smaller than n.

1.4. Consistency of SCORE.

The theory targets uniform consistency over broad classes of degree-heterogeneity parameters without imposing much structural modeling. Empirical studies use web blogs and karate club networks, while the analysis distinguishes these assumptions from prior work.

The consistency analysis avoids strong structural assumptions on heterogeneity parameters, requiring conditions based on ℓq-norms and extreme coordinates instead.
This choice reflects that heterogeneity structure is difficult to model and that its role in community detection is largely ancillary.
The theoretical framework differs from prior studies using scaled i.i.d. heterogeneity or the uncorrected block model.
The empirical evaluation studies the web blogs network and the karate club network, using manually labeled blogs as ground truth.

1.5. Applications to the web blogs data and the karate club data.

SCORE separates the two communities in both real networks using the ratio vector, achieving low reported error rates with straightforward clustering or thresholding.

The web blogs ratio vector shows two modes and near-complete separation between liberal and conservative nodes.The histogram and indexed plot both support simple thresholding for the two communities.
58/1222 error rate is obtained for SCORE on the web blogs data using the stated procedure.
55/1222 error rate is obtained with the ideal threshold t = −0.6, compared with 82/1222 for t = 0.The k-means procedure is equivalent to simple thresholding with t = −0.7.
1/34 error rate is obtained on the karate network using either k-means or thresholding with t = 0.The ideal threshold gives 0/34.

1.6. Comparison with classical spectral clustering methods.

Classical spectral clustering performs poorly on these data because degree inhomogeneity distorts eigenvector coordinates, whereas SCORE supplies a preprocessing step based on eigenvector ratios.

oPCA and nPCA apply k-means directly to leading eigenvectors of A or a normalized matrix.oPCA uses the two leading eigenvectors of A; nPCA uses the corresponding normalized construction.
437/1222 and 600/1222 are the web blogs error rates for oPCA and nPCA, respectively; both methods obtain 1/34 on karate.
Degree inhomogeneity heavily skews the coordinates of the leading eigenvectors, undermining direct clustering.The web blogs eigenvector plot shows the two coordinates highly skewed to the left.
nPCA’s degree correction is not particularly successful on the sparse web blogs adjacency matrix, with some normalized second-eigenvector entries very large.
SCORE provides a convenient preprocessing approach that makes eigenvector-derived data cluster-able.
69/1222 and 1/34 are Newman’s Spectral Modularity error rates on web blogs and karate, versus 58/1222 and 1/34 for SCORE.

1.7. Comparison with other spectral methods.

The paper compares SCORE with profile likelihood and modularity-related methods, emphasizing SCORE’s lower computational burden and more stable behavior in the reported experiments.

Profile likelihood searches over community partitions and is computationally NP-hard in principle, motivating heuristic approximations such as tabu search.
PL is computationally much more expensive and increasingly so with network size or complexity; its stability depends on the initial partition.
9 out of 100 web blogs repetitions and 19 out of 100 karate repetitions fail to converge to the true partition and yield poor results.
62 ± 0.0 web blogs errors result when PL is initialized with SCORE labels, while all three tested starts give 2 ± 0.0 karate errors.The corresponding web blogs errors are 62±2.0 for oPCA and 569.4 ± 3.7 for nPCA starts.
SCORE yields NMI 0.725 on web blogs and ARI 0.819 and 0.8823 on web blogs and karate, respectively.
SCORE uses coordinate-wise leading-eigenvector ratios to remove much of the degree-heterogeneity effect without estimating heterogeneity parameters.

1.9. Summary.

The paper evaluates SCORE against spectral, PCA, modularity, and likelihood-based methods on karate club and web blogs data. SCORE is presented as simpler to implement and computationally faster, while remaining open to future extensions.

SCORE performs more satisfactorily than the two PCA approaches on the karate club and web blogs data.
SCORE differs from Newman’s SM in both its idea and algorithm, especially when K > 2, and has a smaller web blogs error rate.
SCORE outperforms PL because PL can be unstable when its starting point is poor and is comparably slower without lower error rates.
SCORE is conceptually simple and easy to implement, leaving room for future extensions.
The paper’s analysis differs from related work by focusing on DCBM with small K and allowing nonstructured degree-heterogeneity parameters θ(i).

2. Main results.

For a known K-community network under DCBM, the paper analyzes SCORE through spectral approximations and ratios of leading eigenvectors. Under regularity conditions, these results establish stable, weakly consistent community detection, with stronger recovery possible under stronger assumptions.

Problem: SCORE targets community detection in a network partitioned into K communities, with K ≥ 2 treated as known.
Theory: The spectral theory controls eigenvalue and eigenvector perturbations by comparing A with its signal matrix and bounding noise through regularity conditions.
Scope: The framework allows broad degree heterogeneity because its regularity conditions depend only on norms and extreme entries of θ, rather than strong structural assumptions.
Method: The estimated ratio matrix is approximated by a matrix with at most K distinct rows, whose row assignments define the estimated communities.
Method: For K = 2, SCORE reduces to one-dimensional thresholding; for larger K, it uses heuristic implementations of computationally hard k-means.
Results: Under mild conditions, Theorem 2.2 establishes weak consistency, with Hamming error much smaller than n.
Results: With stronger conditions, SCORE can achieve exact recovery with overwhelming probabilities, described as having the oracle property.

3. Simulations.

The simulations compare SCORE with spectral, profile-likelihood, modularity, and pseudo-likelihood methods across six experiments. SCORE is often strongest or competitive, while profile likelihood is less stable and computationally slower in reported settings.

Simulation design: Six simulation experiments compare SCORE, oPCA, nPCA, profile likelihood, Newman’s spectral modularity, and pseudo-likelihood.The experiments vary network size, community count, degree heterogeneity, separation, balance, and initialization.
Experiment 1: In Experiment 1, all methods perform satisfactorily with similar error rates, although profile likelihood reaches a 49.8% error rate in one repetition.The experiment uses a two-community stochastic block model with n=1000 and 50 repetitions.
Experiment 2: In Experiment 2, SCORE outperforms nPCA and oPCA, while its error rates are similar to profile likelihood and more stable.The experiment contains three communities; the SCOREq variant used is generally similar to SCORE but slightly better in this setting.
Experiments 3(a)–3(b): Under varying degree heterogeneity, oPCA and nPCA usually have higher error rates, whereas profile likelihood and SCORE have similar averages but profile likelihood has larger standard deviation.Profile-likelihood instability is attributed to random initialization and possible failure to converge from a bad initial guess.
Experiments 5–6: SCORE has smaller error rates than several competitors in Experiments 5 and 6, but nPCA is best in one setting and PL-SCORE is strongest in Experiment 6.PL-SCORE’s improvements over SCORE are negligible in Experiment 6(a) and mild in 6(b), while PL-SCORE is more computationally demanding.
Experiment 4: As d0 decreases, the problem becomes harder and SCORE has the best performance among the four methods compared in Experiment 4.Figure 6 reports Hamming errors against d0; profile likelihood is omitted because it is time consuming at n=4000.
Overall findings: The simulations conclude that SCORE is often better than oPCA, nPCA, and Newman’s SM, similar to profile likelihood in some settings, and not always best.Profile likelihood is computationally slower than several alternatives, whereas SCORE is conceptually simple and easy to implement.

4. Discussion.

The discussion argues that SCORE removes much of DCBM degree heterogeneity without estimating heterogeneity parameters and supports consistent community detection under stated conditions. It also identifies extensions and important scope boundaries, including known K and regularity assumptions.

Discussion: SCORE uses a scaling-invariant row mapping of leading eigenvectors to remove much of degree heterogeneity without estimating its parameters.The method is motivated by treating DCBM heterogeneity parameters as largely ancillary for community detection.
Discussion: Avoiding heterogeneity estimation is especially useful for sparse networks, where inaccurate estimates can propagate errors and heterogeneity correction can inflate noise.The paper connects sparse-node estimation errors with a smaller signal-to-noise ratio after correction.
Discussion: The theory allows heterogeneity parameters to vary with network size and imposes fewer structural assumptions than some prior analyses.The resulting regularity conditions generally have more complicated forms.
Extensions: The framework extends to scaling-invariant spectral mappings, more realistic network models, bipartite networks, and linkage prediction.The authors report work in progress applying the method to Senate and House voting networks.
Limitations: The paper assumes K is known, while community detection with unknown K remains unsolved even for low-dimensional clustering problems.Trying multiple K values is suggested as a possible but nontrivial future approach.
Limitations: Two regularity conditions ensure eigenvalue gaps needed to control differences between population and observed eigenvalues and eigenvectors.The authors note that these conditions and the resulting lower bound may be relaxable.
Connections: The work contrasts careful spectral adjustment with replacing spectral clustering by nuclear-norm penalization in low-rank matrix recovery.The discussion also relates this perspective to spectral clustering with feature selection in cancer micro-array data.

Supplementary material for “Fast communication detetion by SCORE”

The supplementary document contains technical material supporting the paper, including SCORE variants, proofs of the main theorems, and proofs of secondary lemmas.

Supplementary material: The supplementary document has three parts: Appendix A discusses SCORE variants, Appendix B proves the main theorems, and Appendix C proves secondary lemmas.The technical proofs are placed in the supplementary document because of space constraints.