PaperlayerView exact revision on arXiv

Source-linked AI summary

Estimating the number of communities in networks by spectral methods

Can M. Le, Elizaveta Levina

arXiv:1507.00827v2stat.MLcs.SImath.STstat.TH

TL;DR

Most community-detection methods require the number of communities in advance, although it is often unknown. This paper estimates that number using spectral properties of the Bethe Hessian and non-backtracking matrices. The estimators perform well across models and parameter ranges and are computationally efficient compared with existing approaches.

  • Problem

    Most methods for community detection require the number of communities K as input, although K is often unknown in practice.

    Source: §1 · p. 1

  • Method

    The paper estimates K by counting informative eigenvalues of the non-backtracking matrix or negative eigenvalues of Bethe Hessian variants.

    Source: §1 · p. 2, §3.1 · p. 4, §3.2 · p. 4

  • Results

    The spectral methods perform well across network models and parameter ranges, and the paper reports better accuracy and computational efficiency than existing approaches.

    Source: §1 · p. 2

  • Takeaways & Limitations

    For networks with substantially different community sizes, spectral estimates can serve as a lower bound on K and a starting point for likelihood-based estimation.

    Source: §6 · pp. 10–11

    With substantially different community sizes, spectral methods can underestimate K by combining small communities.

    Source: §6 · pp. 10–11

Abstract

from arXiv · show

Community detection is a fundamental problem in network analysis with many methods available to estimate communities. Most of these methods assume that the number of communities is known, which is often not the case in practice. We study a simple and very fast method for estimating the number of communities based on the spectral properties of certain graph operators, such as the non-backtracking matrix and the Bethe Hessian matrix. We show that the method performs well under several models and a wide range of parameters, and is guaranteed to be consistent under several asymptotic regimes. We compare this method to several existing methods for estimating the number of communities and show that it is both more accurate and more computationally efficient.

1. Introduction

Community detection groups nodes by connectivity, but estimating the number of communities is difficult because most methods require K as input. The paper introduces a fast spectral approach to estimate K and compares it with existing methods.

1. Introduction

  • Community detection groups network nodes so that nodes in the same community have similar connectivity.The stochastic block model assigns node labels and draws edges according to the labels; its degree-corrected version adds node-specific degree parameters to accommodate hubs.Source: §1 · p. 1
  • Most community-detection methods require K in advance, while likelihood-based BIC methods can be computationally challenging on large networks.Other approaches use eigenvalue hypothesis tests with costly bootstrap corrections or cross-validation over many random network splits.Source: §1 · pp. 1–2
  • Counting informative eigenvalues of the Bethe Hessian or non-backtracking matrix estimates K, performs well across network models and parameter ranges, and is computationally efficient.The method requires computing only a few leading eigenvalues of one typically sparse matrix.Source: §1 · p. 2
  • The paper presents its spectral estimators as more accurate than existing methods designed for SBM or DCSBM, while describing concurrent alternatives as computationally intensive or competitive in accuracy.Its theoretical analysis covers sparse, dense, assortative, and disassortative networks.Source: §1 · p. 2

2. Preliminaries

The preliminaries introduce network quantities and two graph operators used to estimate community structure. The non-backtracking spectrum separates informative eigenvalues from the bulk, while negative Bethe Hessian eigenvalues can correspond to communities.

2. Preliminaries

  • The preliminaries identify A as the symmetric adjacency matrix, define node degree from its row sum, and use d for the average expected degree.The degree matrix is D = diag(d_i).Source: §2 · p. 2, §2.1 · p. 3

2.1. The non-backtracking matrix.

  • The non-backtracking matrix indexes directed edges and permits a transition from one edge to another when the next edge does not immediately reverse direction.Its spectrum can be represented using eigenvalues of a 2n × 2n matrix, alongside ±1.Source: §2.1 · pp. 2–3
  • When a network has K communities, the K largest-magnitude eigenvalues of the non-backtracking matrix are real and separated from the bulk, making them informative for community structure.The cited result places the bulk within a circle of radius ∥B∥^1/2.Source: §2.1 · p. 3

2.2. The Bethe Hessian matrix.

  • In graph theory, r ∈ R is a parameter, and the determinant of H(r) vanishes if r is an eigenvalue of the non-backtracking matrix [16, 6, 5].Source: §2.2 · p. 3
  • For assortative sparse networks, the K community-encoding eigenvalues of the Bethe Hessian are negative while the bulk is positive, so the negative-eigenvalue count corresponds to K.The paper states consistency for graphs with d ≫ log n.Source: §2.2 · p. 3

3. Spectral estimates of the number of communities

The paper estimates the number of communities by counting eigenvalues of the non-backtracking or Bethe Hessian matrices. Bethe Hessian variants use different parameter choices and a correction that performs well, especially on unbalanced networks.

3. Spectral estimates of the number of communities

  • The proposed estimators count eigenvalues of either the non-backtracking or Bethe Hessian matrix, without adjustment for SBM versus DCSBM.Source: §3 · pp. 3–4

3.1. Estimating K from the non-backtracking matrix.

  • NB estimates K by counting real non-backtracking eigenvalues at least as large as the square root of the matrix norm; its accuracy drops for unbalanced networks.Computing its eigenvalues is slightly more demanding than computing Bethe Hessian eigenvalues on large networks.Source: §3.1 · p. 4

3.2. Estimating K from the Bethe Hessian matrix.

  • BHm sets r to the square root of estimated average degree, while BHa uses mean degree; computing the former is less demanding than using the matrix norm.Source: §3.2 · p. 4
  • On balanced networks, NB, BHm, and BHa perform similarly; on unbalanced networks, BHa produces better results.Source: §3.2 · p. 4
  • Corrected Bethe Hessian methods BHmc and BHac perform well, especially on unbalanced networks, by counting informative positive eigenvalues near zero.The correction addresses underestimation when some informative eigenvalues become positive; the paper sets its tuning parameter t to 5.Source: §3.2 · pp. 4–5

4. Consistency

The section establishes consistency results for estimating community counts with non-backtracking and Bethe Hessian spectra under sparse and semi-dense regimes. The guarantees depend on model and spectral assumptions, with an additional degree restriction for Erdős–Rényi graphs.

4. Consistency

  • In the sparse stochastic block model, consistency of the non-backtracking estimate follows from, whose proof does not extend to other regimes or the Bethe Hessian.The sparse two-community example has condition (a − b)^2 > 2(a + b), matching the stated sparse detectability threshold [29].Source: §4 · p. 5
  • The semi-dense analysis assumes equal expected degrees, while the authors note that unequal-degree communities can be separated by degree and analyzed in sub-networks.For degree-corrected block models, the equal-degree condition also holds when the underlying block model satisfies it and degree parameters share a distribution.Source: §4 · p. 6
  • For Erdős–Rényi graphs, Assumption 4.3 is equivalent to d ≤ n^2/13, and whether this restriction can be removed is unclear.The assumption supplies a sharp bound on ∥A−E A∥ used in the proofs of Theorems 4.2 and 4.3.Source: §4 · p. 6
  • With probability at least 1−1/n, the non-backtracking matrix has exactly K real eigenvalues separated from the remaining spectrum in the semi-dense regime.The separation holds for d ≫ log n, with ε vanishing; K may depend on n.Source: §4 · p. 6
  • The spectral connection used to prove the semi-dense non-backtracking result improves on an earlier Erdős–Rényi result requiring d ≫ n^5/6.Theorem A.1 extends the result beyond Erdős–Rényi graphs and requires only d ≫ log n.Source: §4 · p. 6
  • Under the stronger Bethe Hessian assumptions, BHm and BHa consistently estimate K = rank(E A) by counting negative eigenvalues.The theorem gives exactly K negative eigenvalues with probability at least 1−1/n and requires nonnegative nonzero eigenvalues of E A.Source: §4 · pp. 6–7

5. Numerical results

The section compares spectral estimators with cross-validation and a likelihood-based criterion on synthetic and real-world networks. Results vary with edge-density balance, community sizes, and whether a method applies to the network model.

5. Numerical results

  • The numerical comparison includes NB and Bethe Hessian variants, NCV variants for SBM and DCSBM, and VLH for SBM; simulations allow unequal expected degrees despite simplifying equal-degree assumptions in theory.NCV and VLH choose K from prespecified candidate sets.Source: §5 · p. 7, §5.1 · p. 8

5.1. Synthetic networks.

  • Synthetic networks vary average degree, within-community density, community proportions, and degree correction, with accuracy measured over 200 replications at n = 1200.The tested community counts are K = 2, 4, and 6; DCSBM settings include γ = 0.9, corresponding to 10% hubs.Source: §5.1 · pp. 7–8
  • With balanced communities and within-community densities, spectral methods perform similarly and outperform NCV and VLH.For larger K, especially under DCSBM, corrected versions are somewhat better than uncorrected ones, and the best Bethe Hessian methods outperform the non-backtracking estimator.Source: Figure 1 · p. 8, §5.1 · p. 8
  • For unbalanced within-community densities, BHac is the best spectral method overall and the best overall for DCSBM, where VLH is not applicable.For the SBM, VLH is comparable to BHac; cross-validation performs poorly, while corrected spectral versions improve on uncorrected ones.Source: §5.1 · p. 8, Figure 2 · p. 9
  • As community sizes become more equal, VLH is less sensitive to their ratio than spectral methods, while spectral methods generally dominate cross-validation except at very small ratios.VLH is unavailable for DCSBM; Bethe Hessian corrections give a slight improvement, though spectral methods perform similarly overall.Source: §5.1 · p. 9, Figure 3 · p. 10

5.2. Real world networks.

  • All spectral methods estimate the correct community count for dolphins and karate club, and perform reasonably on college football and political books.On political blogs, all methods except NCV and VLH estimate many more communities, which may correspond to smaller, more degree-uniform subcommunities; ground-truth labels are a reasonable baseline but can reflect only one node attribute.Source: §5.2 · pp. 9–10

6. Discussion

Spectral methods are fast and reliable for estimating K in balanced networks, with the corrected Bethe Hessian method using threshold r_a the best choice in most scenarios. Their estimates can underestimate K for communities of significantly different sizes, while semi-dense networks permit estimating K below the exact recovery threshold.

6. Discussion

  • The corrected Bethe Hessian method with threshold r_a is the best choice in most scenarios, while spectral methods provide fast, reliable estimates for balanced networks.The real-world-network table reports estimates of the number of communities.Source: §6 · p. 10, Table 2 · p. 11
  • With communities of significantly different sizes, spectral methods tend to underestimate K by combining small communities.The authors describe this as an intrinsic limitation and suggest using estimates as a lower bound and starting point for likelihood-based estimation.Source: §6 · pp. 10–11
  • A small set of plausible K values can reduce computational cost and improve the accuracy of estimating the number of communities.Source: §6 · p. 11
  • For semi-dense networks, estimating the number of communities is possible below the exact recovery threshold.Source: §6 · p. 11
  • The exact condition under which estimating the number of communities is possible remains an open question.Source: §6 · p. 11

Appendix A. Proof of Theorem 4.2

The appendix proof connects the spectra of H + E and H, then uses adjacency-matrix concentration bounds to support the result for Theorem 4.2. A sharper bound replaces a cruder assumption under stronger assumptions.

Appendix A. Proof of Theorem 4.2

  • Theorem A.1 connects the spectra of H + E and H, whose spectrum is closely related to that of the adjacency matrix.Source: Appendix A · p. 11
  • The proof of Theorem A.1 uses a crude bound on ∥A−E A∥ that applies to general graph models, including SBM, DCSBM, and inhomogeneous Erdős–Rényi models.Source: Appendix A · p. 11
  • The proof of Theorem 4.2 replaces that crude bound with a sharper bound that holds under stronger assumptions.Source: Appendix A · p. 11

A.1. Spectrum of H.

The appendix describes H's eigenstructure through the adjacency matrix: each adjacency eigenvalue determines a pair of eigenvalues of H, and the associated two-dimensional subspaces are invariant under H.

A.1. Spectrum of H.

  • For each adjacency-matrix eigenvalue λ_i, H has two eigenvalues that solve μ^2 − λ_i μ + 1 = 0.Source: §A.1 · p. 11
  • The passage gives the corresponding left and right eigenvectors of H and notes that the right eigenvectors are not unit vectors.Source: §A.1 · p. 12
  • The space C^2n decomposes into orthogonal two-dimensional subspaces that are invariant under H.Source: §A.1 · p. 12

A.2. Spectrum of H + E.

This appendix analyzes how perturbation affects the spectrum of H and uses adjacency-matrix concentration to establish spectral separation for the non-backtracking matrix. It addresses the difficulty that H and E are not symmetric, so standard Weyl inequalities do not apply.

A.2. Spectrum of H + E.

  • A direct analysis shows that the spectrum of H + E is close to that of H for much sparser graphs than the earlier Bauer–Fike analysis required.The earlier result for Erdős–Rényi graphs required average degree at least of order n^5/6.Source: §A.2 · p. 12
  • Theorem A.1 states that, with probability at least 1 − 1/n, each eigenvalue of H + E has an eigenvalue of H nearby.Source: §A.2 · p. 12
  • Theorem A.2 provides a concentration bound for the adjacency matrix under its stated assumptions.Source: §A.2 · p. 13
  • The proof concludes that the K largest-magnitude eigenvalues of B are real and lie outside the circle containing its complex eigenvalues.Source: §A.2 · p. 14

Appendix B. Proof of Theorem 4.3

The proof establishes that H(r) has K negative eigenvalues and that its remaining eigenvalues are positive. It uses a decomposition of H(r) and eigenvalue bounds to show the required signs.

Appendix B. Proof of Theorem 4.3

  • The proof decomposes H(r) into ˆH(r) − r E A and shows that ˆH(r)'s eigenvalues are non-negative and smaller in order than the non-zero eigenvalues of r E A.Source: Appendix B · p. 20
  • H(r) has K negative eigenvalues and its remaining eigenvalues are positive.The proof establishes negativity of the K smallest eigenvalues and non-negativity of the other n − K eigenvalues.Source: Appendix B · p. 20
  • The Courant min-max principle shows that the n − K largest eigenvalues of H(r) are non-negative.The proof bounds the Rayleigh quotient on the orthogonal complement of the column space of E A.Source: Appendix B · p. 20

Related papers

Loading 1507.00827v2…