Estimating the number of communities in networks by spectral methods
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.
\section{Introduction}
\input{introduction}

\section{Preliminaries}
\input{preliminaries}

\section{Spectral estimates of the number of communities}
\input{methods}

\section{Consistency}
\input{consistency}

\section{Numerical results}\label{sec: simulation}
\input{simulation}

\section{Discussion}\label{sec: discussion}
\input{discussion}
















\subsection{Estimating $K$ from the non-backtracking matrix}\label{sec: NB}
Under the SBM, the informative eigenvalues of the non-backtracking matrix are real-valued and separated from the bulk of radius $\|\tilde{B}\|^{1/2}$ \cite{Bordenave.et.al2015non-backtracking}.
Therefore we can estimate $K$ by counting the number of real eigenvalues of $\tilde{B}$ that are at least $\|\tilde{B}\|^{1/2}$.
We denote this method by NB (for non-backtracking).
As shown by numerical results in Section~\ref{sec: simulation}, this estimate of $K$ also works under the DCSBM.
When the network is balanced (communities have similar sizes and edge densities), NB performs well;
however, the accuracy of NB drops if the communities are unbalanced in either size or edge density.  Computationally, since $\tilde{B}$ is not symmetric, computing the eigenvalues of $\tilde{B}$ is more demanding for large networks.   Thus we focus instead on the Bethe Hessian matrix, which is symmetric.


\subsection{Estimating $K$ from the Bethe Hessian matrix}\label{sec: BH}
The number of communities corresponds to the number of negative eigenvalues of $H(r)$;  the challenge is in choosing an appropriate value of $r$.

It was argued in \cite{Saade&Krzakala&Zdeborova2014} that when $r=\|\tilde{B}\|^{1/2}$,
the informative eigenvalues of $H(r)$ are negative, while the bulk are positive;
by \cite{Krzakala.et.al2013spectral}, $\|\tilde{B}\|$ can be approximated by $\tilde{d}$ from \eqref{eq: non-bactracking spectral norm}.
Following these results, we first choose $r$ to be $r_m = \tilde{d}^{1/2}$
and denote the corresponding method by BHm.
Simulations show that using $r=r_m$ and $r=\|\tilde{B}\|^{1/2}$ produce similar results;
we choose $r = r_m$ because computing $r_m$ is less demanding than computing $\|\tilde{B}\|^{1/2}$.

Another choice of $r$ is $r_a = \sqrt{(d_1+\cdots+d_n)/n}$, which was proposed in \cite{Saade&Krzakala&Zdeborova2014} for recovering the community structure under the SBM; we denote the corresponding method by BHa.
We have found that when the network is balanced , NB, BHm, and BHa perform similarly;
when the network is unbalanced, BHa produces better results. 

Both BHm and BHa tend to underestimate the number of communities, especially when the network is unbalanced.
In that setting, some informative eigenvalues of $H(r)$ become positive, although they may still be far from the bulk.
Based on this observation, we correct BHm and BHa by also using positive eigenvalues of $H(r)$ that are much close to zero than to the bulk.
Namely, we sort eigenvalues of $H(r)$ in non-increasing order $\rho_1\ge \rho_2\ge\cdots\ge\rho_n$, and estimate $K$ by
\begin{equation}\label{eq: K correction}
  \hat{K} = \max\{k: t\rho_{n-k+1} \le \rho_{n-k} \},
\end{equation}
where $t>0$ is a tuning parameter.
Note that if $\rho_{n-k_0+1}<0$ then $\hat{K} \ge k_0$ because $\rho_{n-k_0+1} \le \rho_{n-k_0}$,
therefore the number of negative eigenvalues of $H(r)$ is always upper bounded by $\hat{K}$.
Heuristically, if the bulk follows the semi-circular law and $\rho_{n-k}\ge 0$ is given,
then the probability that $0 \le \rho_{n-k+1} \le \rho_{n-k}/t$ is less than $1/t$.
When $1/t$ is sufficiently small, we may suspect that $\rho_{n-k+1}$ is an informative eigenvalue.
In practice we find that $t\in [4,6]$ works well; we will set $t=5$ for all computations in this paper.
Simulations show that $\hat{K}$ performs well, especially for unbalanced networks.
The resulting methods are denoted by BHmc and BHac, respectively.
We will also use BH to refer to all the methods that use the Bethe Hessian matrix.



\subsection{The non-backtracking matrix}\label{sec: nonbacktracking}
Let $m$ be the number of edges in the undirected network.  To construct the  non-backtracking matrix $B$,  we represent the edge between node $i$ and node $j$  by two directed edges,  one from $i$ to $j$ and the other from $j$ to $i$.
The $2m \times 2m$ matrix $B$,  indexed by these directed edges, is defined by
\begin{equation*}
  B_{i \ra j, k \ra l} =
  \left\{
    \begin{array}{ll}
      1 & \hbox{if } j = k \text{ and } i \neq l \\
      0 & \hbox{otherwise.}
    \end{array}
  \right.
\end{equation*}
It is well-known \cite{Angel&Friedman&Hoory2007}\cite{Krzakala.et.al2013spectral} that the spectrum of $B$ consists of $\pm 1$ and eigenvalues of an $2n\times 2n$ matrix
\begin{equation*}
  \tilde{B} =
\left(
  \begin{array}{cc}
    0_n & D - I_n \\
    -I_n & A \\
  \end{array}
\right).
\end{equation*}
Here $0_n$ is the $n\times n$ matrix of all zeros, $I_n$ is the $n\times n$ identity matrix,
and $D = \mathrm{diag}(d_i)$ is $n \times n$ diagonal matrix with degrees $d_i$ on the diagonal.
It was observed in \cite{Krzakala.et.al2013spectral} that if a network has $K$ communities then
the first $K$ largest eigenvalues in magnitude of $\tilde{B}$ are real-valued and well separated from the bulk,
which is contained in a circle of radius $\|\tilde{B}\|^{1/2}$.
We will refer to these $K$ eigenvalues as informative eigenvalues of $\tilde{B}$.
It was also shown in \cite{Krzakala.et.al2013spectral} that the spectral norm of the non-backtracking matrix
is approximated by
\begin{equation}\label{eq: non-bactracking spectral norm}
  \tilde{d} = \Big(\sum_{i=1}^n d_i\Big)^{-1} \Big(\sum_{i=1}^n d_i^2\Big) - 1.
\end{equation}
For the special case of the SBM, \cite{Bordenave.et.al2015non-backtracking} proved
that the leading eigenvalues of $\tilde{B}$ concentrate around non-zero eigenvalues of $\bar{A}$
and the bulk is contained in a circle of radius $\|\tilde{B}\|^{1/2}$, and used the corresponding leading eigenvectors to recover the community labels.

\subsection{The Bethe Hessian matrix}\label{sec: bethe hessian}
The Bethe Hessian matrix is defined as
\begin{equation}\label{eq: bethe hessian}
  H(r) = (r^2 -1) I - r A + D,
\end{equation}
where $r \in \R$ is a parameter.
In graph theory, the determinant of $H(r)$ is the Ihara-Bass formula for the graph zeta function.
It vanishes if $r$ is an eigenvalue of the non-backtracking matrix \cite{Hashimoto1989,Bass1992,Angel&Friedman&Hoory2007}.
Saade et al \cite{Saade&Krzakala&Zdeborova2014} used the Bethe Hessian for community detection.
Under the SBM, they argued that the best choice of $r$ is $|r_c|=\sqrt{\l_n}$,
depending on whether the network is assortative or disassortative;
for a more general network, their choice of $r$ is $|r_c| = \|\tilde{B}\|^{1/2}$.
For assortative sparse networks with $K$ communities and bounded $\l_n$,
they showed that the $K$ eigenvalues of $H(r_c)$ whose corresponding eigenvectors encode the community structure
are negative, while the bulk of $H(r_c)$ are positive.
Thus, the number of negative eigenvalues of $H(r_c)$ corresponds to the number of communities.
We will refer to these negative eigenvalues of $H(r_c)$ as informative eigenvalues.

\subsection{Synthetic networks}

To generate test case networks, we fix the label vector $c \in \{1,...,K\}^n$ so that $c_i = k$ if $n\pi_{k-1} + 1 \le i < n\pi_k$, where $\pi_0=0$.
The label matrix $Z \in \R^{n\times K}$ encodes $c$ by representing each node with a row of $K$ elements, exactly one of which is equal to 1 and the rest are equal to 0:  $Z_{ik}={\mathbf 1}(c_i=k)$.
Let $\tilde{P}$ be an $K \times K$ matrix with diagonal $w=(w_1,...,w_K)$ and off-diagonal entries $\beta$, and $M = ZPZ^T$.
Under the stochastic block model, we generate $A$ according to an edge probability matrix $\bar{A} = \E A$ proportional to $M$;
the average degree $\l_n$ is controlled by appropriately rescaling $M$.
The parameter $w$ controls the relative edge densities within communities, and $\beta$ controls the out-in probability ratio.   Smaller values of $\beta$ and larger values of $\lambda_n$ make the problem easier.
For the DCSBM, we generate the degree parameters $\theta_i$ from a distribution that takes two values,  $\P(\theta=1)=1-\gamma$ and $\P(\theta=0.2)=\gamma$.
Parameter $\gamma$ controls the fraction of ``hubs'', the high-degree nodes in the network, and setting $\gamma = 0$ gives back the regular SBM.
Given $\theta=(\theta_i,...,\theta_n)$, the edges are generated independently with
probabilities $\bar{A} = \E A$ proportional to $\mathrm{diag}(\theta)M\mathrm{diag}(\theta)$,
where $\mathrm{diag}(\theta)$ is a diagonal matrix with $\theta_i$'s on the diagonal.



The number of nodes is set to $n=1200$,
the out-in probability ratio $\beta = 0.2$,
and we vary the average degree $\l_n$, weights $w$, and community sizes.   We consider three different values for the number of communities, $K = 2$, 4, and 6.
For each setting, we generate $200$ replications of the network and record the accuracy, defined as
the fraction of the times a method correctly estimates the true number of communities $K$.   The methods NCV and VLH require a pre-specified set of $K$ values to choose from;  we use the set $\{1,2,...,8\}$ for synthetic networks
and $\{1,2,...,15\}$ for real-world networks.

We start by varying the average degree $\l_n$, which controls the overall difficulty of the problem, and keeping all community sizes equal.    Figure~\ref{fig:sparsity}  shows the performance of all methods when all edge density weights are also equal, $w_i=1$ for all $1\le i \le K$;  in Figure~\ref{fig:unbalanced w}, $w=(1,2)$ for $K=2$, $w=(1,1,2,3)$ for $K=4$, and $w=(1,1,1,1,2,3)$ for $K=6$, resulting in communities with varying edge density.  In all figures, the top row corresponds to the SBM ($\gamma = 0$) and the bottom row to the DCSBM ($\gamma=0.9$, which means that 10\% of nodes are hubs).

In general, we see that when everything is balanced (Figure~\ref{fig:sparsity}), all spectral methods perform fairly similarly and outperform both cross-validation (NCV) and the BIC-type criterion (VLH).  Also, for larger $K$ and especially under DCSBM, we can see that the corrected versions are slightly better than the uncorrected ones, and the best Bethe Hessian based methods are better than the non-backtracking estimator.

For networks with equal size communities but different edge densities within communities (Figure~\ref{fig:unbalanced w}), cross-validation performs poorly, but VLH relatively improves.   For larger $K$ the spectral methods are also distinguishable, with all BH methods dominating NB, and corrected versions providing improvement.  Overall, BHac is the best spectral method, comparable to VLH for the SBM, and best overall for DCSBM where VLH is not applicable.
\begin{figure}[!ht]
  \centering
  \includegraphics[trim=110 10 100 10,clip,width=1\textwidth]{sparsity_comparison}\\
  \caption{The accuracy of estimating $K$  as a function of the average degree.
  All communities have equal sizes, and $w_i=1$ for all $1\le i \le K$.}
  \label{fig:sparsity}
\end{figure}

\begin{figure}[!ht]
  \centering
  \includegraphics[trim=110 10 100 10,clip,width=1\textwidth]{unbalanced_w_comparison}\\
  \caption{The accuracy of estimating $K$ as a function of the average degree.
  All communities have equal sizes; $w=(1,2)$ for $K=2$, $w=(1,1,2,3)$ for $K=4$, and $w=(1,1,1,1,2,3)$ for $K=6$.}
  \label{fig:unbalanced w}
\end{figure}

Communities of different sizes present a challenge for community detection methods in general, and the presence of relatively small communities makes the problem of estimating $K$ difficult.  To test the sensitivity of all the methods to this factor, we change the proportions of nodes falling into each community
setting $\pi_1 = r/K$, $\pi_K = (2-r)/K$, and $\pi_i = 1/K$ for $2 \le i \le K-1$, and varying $r$ in the range $[0.2, 1]$.
As $r$ increases, the community sizes become more similar, and are all equal when $r=1$.
Figure \ref{fig:community_ratio} shows the performance of all methods as a function of $r$.
The top row corresponds to the SBM ($\gamma = 0$), the bottom row to the DCSBM ($\gamma=0.9$), and the within-community edge density parameters
$w_i = 1$ for all $1 \le i \le K$.  Here we see that VLH is less sensitive to $r$ than the spectral methods, but unfortunately it is not available under the DCSBM.   Cross-validation is still dominated by spectral methods except for very small values of $r$, where all methods perform poorly.    The corrections still provide a slight improvement for Bethe Hessian based methods, although all spectral methods perform fairly similarly in this case.

\begin{figure}[!ht]
  \centering
  \includegraphics[trim=110 10 100 10,clip,width=1\textwidth]{community_ratio_comparison}\\
  \caption{The accuracy of estimating  $K$ as a function of the community-size ratio  $r$:
  $\pi_1 = r/K$, $\pi_K = (2-r)/K$, and $\pi_i=1/K$ for $2 \le i \le K-1$. In all plots, $w_i=1$ for $1\le i \le K$;
  the average degrees are $\l_n = 10$ (left), $15$ (middle), and $20$ (right).}
  \label{fig:community_ratio}
\end{figure}



\subsection{Real world networks}
Finally, we test the proposed methods on several popular network datasets.
In the college football network \cite{Girvan&Newman2002}, nodes represent 115 US college football teams, and edges represent the games played in 2000.
Communities are the 12 conferences that the teams belong to.
The political books network \cite{Newman2006}, compiled around 2004,  consists of 105 books about US politics;  an edge is ``frequently purchased together'' on Amazon.  Communities are ``conservative'', ``liberal'', or ``neutral'', labelled manually based on contents.
The dolphin network \cite{Lusseau2003} is a social network of 62 dolphins, with
edges representing social interactions, and communities based on a split which happened after one dolphin left the group.
Similarly, the karate club network  \cite{Zachary1977} is a social network of 34 members of a karate club,  with
edges representing friendships, and communities based on a split following a dispute.   Finally, the political blog network \cite{Adamic05}, collected around 2004,
 consists of blogs about US politics, with edges representing web links, and communities are manually assigned as ``conservative'' or ``liberal''.  For this dataset, as is commonly done in the literature, we only consider its largest connected component of 1222 nodes.

Table~\ref{Table:real data} shows the estimated number of communities in these networks.
All spectral methods estimate the correct number of communities for dolphins and the karate club, and do a reasonable job for the college football and political books data.   For political blogs, all methods but NCV and VLH estimate a much larger number of communities, suggesting the estimates correspond to smaller sub-communities with more uniform degree distributions that have been perviously detected by other authors.   We also found that the VLH method was highly dependent on the tuning parameter, and the estimates of NCVbm and NCVdc varied noticeably from run to run due to their use of random partitions.
\begin{table}[!ht]
\renewcommand{\arraystretch}{1.2}
\centering
\begin{tabular}{l|ccccccccc}
  \hline
   \textbf{Dataset} & NB & BHm  & BHmc & BHa & BHac & NCVbm & NCVdc & VLH & Truth\\ \hline
  \text{College football } & 10 & 10 & 10 & 10 & 10 & 14 & 13 & 9 & 12\\
  \text{Political books }   & 3 & 3 & 4 & 4 & 4 & 8 & 2 & 6 & 3\\
  \text{Dolphins}   & 2 & 2 & 2 & 2 & 2 & 4 & 3 & 2 & 2\\
  \text{Karate club}   & 2 & 2 & 2 & 2 & 2 & 3 & 3 & 4 & 2\\
  \text{Political blogs}   & 8 & 7 & 8 & 7 & 8 & 10 & 2 & 1 & 2\\ \hline
\end{tabular}
\caption{Estimates of the number of communities in real-world networks.}
\label{Table:real data}
\end{table}



2015-07-06T02:04:54.000
1507
1507.00827
en
https://arxiv.org/abs/1507.00827
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.
Machine Learning (stat.ML); Social and Information Networks (cs.SI); Statistics Theory (math.ST)
Estimating the number of communities in networks by spectral methods
Qwen/Qwen-72B
1. YES
2. YES

