An Eigengap Ratio Test for Determining the Number of Communities in Network Data

Consider a network of $n$ nodes with the symmetric adjacency matrix $A$ generated from (1.1). The aim of this paper is to test the following hypothesis:

$$H_{0}:K=K_{0}\quad\text{v.s.}\quad{H_{1}:K_{0}<K\leq K_{\max}},$$

(2.1)

where $K$ and $K_{0}$ denote the true and the hypothetical ranks of $P$, respectively, and $K_{\max}$ is a pre-specified maximum value of $K$. In this paper, we set $K_{\max}=\max\{K_{0}+4,n^{2/5}\}$; see discussions after Condition (C2). We consider the one-sided alternative, $K>K_{0}$, since a network with $K$ communities can also be represented as a network with $K_{0}>K$ communities by splitting one or more true communities. The one-sided alternative was also considered in Lei (2016), Chen & Lei (2018), Wang & Bickel (2017) and Hu et al. (2021).

Recall $A=(A_{ij})\in\mathbb{R}^{n\times n}$ is the adjacency matrix with no self-loops. We define

$$\tilde{A}=A-E(A),$$

(2.2)

where $E(A)$ is the expected value of $A$, and $\tilde{A}$ is the noise matrix with zero-mean entries and zero diagonals elements. It is straightforward to see that entries of $\tilde{A}$ have finite variances. Given $E(A)=P-\text{diag}(P)$, (2.2) can then be rewritten as

$$A=P+\tilde{A}-\text{diag}(P),$$

(2.3)

where $\text{diag}(P)$ represents the diagonal matrix constructed from $(P_{11},\cdots,P_{nn})^{\top}$.

Under the null hypothesis of $H_{0}$: $K=K_{0}$, the rank of $P$ is $K$, which implies that $P$ has $K$ nonzero eigenvalues. Let $\lambda_{k}(A)$ denote the $k$-th largest eigenvalue of matrix $A$. We can show that the eigenvalues $\lambda_{k}(A)$ for $k\geq K+1$ are determined by an $n-K$ principal submatrix of $\tilde{A}$, denoted by $\tilde{A}_{G_{I}}$, whose eigenvalues follow the type-I Tracy-Widom distribution. This result motivates the proposal of an eigengap-ratio test statistic, defined as:

$$T=\frac{\lambda_{K_{0}+1}(A)-\lambda_{K_{\max}+1}(A)}{\lambda_{K_{\max}+1}(A)-\lambda_{K_{\max+2}}(A)}.$$

(2.4)

Given that the true rank is $K$, if $K_{0}<K\leq K_{\max}$, we expect $\lambda_{K_{0}+1}(A)-\lambda_{K_{\max}+1}(A)$ to be much larger than $\lambda_{K_{\max}+1}(A)-\lambda_{K_{\max}+2}(A)$. In contrast, when $K_{0}=K$, the ratio of these two eigengaps is not expected to be large. In Theorem 1 of Section 2.3, we show that the asymptotic distribution of $T$ under $K_{0}=K$ is a function of the type-I Tracy-Widom distribution. Specifically, we first carefully bound the difference between $\lambda_{k}(A)$ and $\lambda_{k-K}(\tilde{A}_{G_{I}})$ for $k\geq K+1$, and then demonstrate that the distribution of $n^{2/3}(\sigma_{2}\lambda_{k-K}(\tilde{A}_{G_{I}})-L)$ converges to the type-I Tracy-Widom distribution, where $\sigma_{2}$ and $L$ are scaling and location parameters that do not depend on $k$.

The construction of $T$ in (2.4) offers two key advantages. First, both $\lambda_{k}(A)-\lambda_{k-K}(\tilde{A}_{G_{I}})$ and the asymptotic distribution of $n^{2/3}(\sigma_{2}\lambda_{k-K}(\tilde{A}_{G_{I}})-L)$ involve scaling and location parameters that are very difficult to characterize or estimate. However, these parameters do not depend on $k$ and can be directly cancelled out in the eigengap-ratio statistic, eliminating the need for their estimation. Second, by using the eigengap ratio rather than individual eigenvalues, we avoid the requirement that $\lambda_{k}(A)$ converge to $\lambda_{k-K}(\tilde{A}_{G_{I}})$ (up to a scaling parameter) faster than $n^{2/3}$ for $k\geq K+1$. This simplifies the theoretical analysis and relaxes the assumptions necessary to establish the asymptotic null distribution.

The Tracy-Widom law, introduced by Tracy & Widom (1994, 1996) to characterize the distributions of the eigenvalues of Wigner matrices, has been extensively studied in a series of papers (Lee & Yin, 2014; Lee & Schnelli, 2015; Schnelli & Xu, 2022). Specifically, let $W$ be a symmetric Wigner matrix wtih iid Gaussian entires of mean zero and variance $n^{-1}$. Then, $n^{2/3}(\lambda_{1}(W)-2)$ converges to the Tracy-Widom distribution. Under the null hypothesis $H_{0}$, we employ the Tracy-Widom law to derive the asymptotic null distribution of $T$. In addition, we reparameterize $P$ as $P=\rho_{n}P_{n}$, where $\rho_{n}\rightarrow 0$ and $P_{n}$ is fixed. This allows the connecting probability matrix to scale with $n$, a commonly approach in the literature (Bickel & Chen, 2009; Zhao et al., 2012). We next present some regularity conditions.

• (C1)

  Assume the connecting probability matrix $P=(P_{ij})_{n\times n}$ is symmetric with $P_{ij}\in(0,1)$ for any $1\leq i,j\leq n$.

• (C2)

  Assume $n^{2/3}\rho_{n}\to\infty$, and $K=O(n^{1/12-\psi})$, where $\psi$ is a constant satisfying $0<\psi\leq 1/12$.

• (C3)

  Assume that $\tilde{\lambda}_{K}(P)\geq c^{*}_{3}n/K$, where $\tilde{\lambda}_{K}(P)$ is the $K$-th largest eigenvalue of $P$ in absolute value and $c^{*}_{3}>0$ is a constant.

Condition (C1) requires the entries of the edge probability matrix $P$ to be in $(0,1)$, a condition similarly considered in Lei (2016), Wang & Bickel (2017) and Hu et al. (2021). Condition (C2) allows the edge probabilities $P_{ij}$s to decay to zero slower than $O(n^{-2/3})$, accommodating sparse networks. This condition is less restrictive than those of Lei (2016) and Hu et al. (2021), which assume dense networks where $P_{ij}=O(1)$. However, it is stronger than the conditions in Han et al. (2023) and Jin et al. (2023) to ensure that the distribution of $n^{2/3}(\sigma_{2}\lambda_{k-K}(\tilde{A}_{G_{I}})-L)$ converges to the type-I Tracy-Widom distribution. It also allows the number of communities $K$ to diverge at a rate no faster than $O(n^{1/12})$, which is less stringent than the fixed $K$ considered in Han et al. (2023). By setting $K_{\max}=\max\{K_{0}+4,n^{2/5}\}$, it holds that $K\leq K_{\max}$. Condition (C3) imposes a lower bound on $\tilde{\lambda}_{K}(P)$, so it is bounded away from zero as $n\to\infty$. A similar condition was also considered in Theorem 3.1 of Lei & Rinaldo (2015).

Based on the above conditions, we show the asymptotic null distribution of the test statistic $T$ in the following theorem.

The above theorem indicates that the distribution of the test statistic $T$ is asymptotically equivalent to that of $T_{W}$. This allows us to employ a function of the Tracy-Widom distributions to test the null hypothesis $H_{0}$. Specifically, for a given nominal level $\alpha$, let $c_{\alpha}=F_{T_{W}}^{-1}(1-\alpha)$ be the upper $\alpha$-quantile of $T_{W}$. We then tabulate the critical value $c_{\alpha}$ by approximating $F_{T_{W}}$ via a numerical method, such as Monte Carlo simulation, and reject $H_{0}$ if $T>c_{\alpha}$.

Under the alternative hypothesis $H_{1}:K_{0}<K\leq K_{\max}$, the eigenvalue $\lambda_{K_{0}+1}(A)$ is expected to be large, and the limiting distribution of $T$ no longer converges to that of $T_{W}$. Indeed, we demonstrate that $T$ diverges with $n$ under $H_{1}$, with strong discriminatory power against the alternative hypothesis.

The above theorem implies that for a given nominal level $\alpha$, $P(T>c_{\alpha})\to 1$ under the alternative hypothesis $H_{1}$. In particular, Theorem 2 indicates that $T$ diverges at a rate no slower than $n^{2/3}$ under the alternative, making our test more powerful than those of Han et al. (2023) and Hu et al. (2021). Specifically, the test statistic in Han et al. (2023) is greater than a constant under the alternative, while the test statistic of Hu et al. (2021) diverges at an order of $O(\log n)$ under the alternative. Additionally, the test statistic of Hu et al. (2021) lacks power under the planted partition stochastic block model, that is, a stochastic block model with equal community sizes, equal $Q_{ll}$s, and equal $Q_{lk}$s for $l\neq k$. We next demonstrate through simulation studies that $T$ performs well in both size and power.

We consider two dense edge probability matrices, modified from Hu et al. (2021) and Han et al. (2023), denoted as $Q_{1}$ and $Q_{2}$, respectively. In $Q_{1}$, the edge probability between any two communities $u$ and $v$ is set to $0.1(1+4\times I(u=v))$. In $Q_{2}$, we define $Q_{2,kl}=0.1^{|k-l|}$ if $l\neq l$, and $Q_{2,kl}=(K+1-k)/K$ otherwise. The edge probabilities in $Q_{1}$ and $Q_{2}$ do not decrease with $n$, and represent dense network scenarios. We implement $Q_{1}$ for SBM and DCSBM, incorporating the methods of Lei (2016), Hu et al. (2021), and Han et al. (2023) for comparison. Additionally, we implement $Q_{2}$ for DCMM, and compare with Han et al. (2023).

Tables 2-3 report the empirical sizes and powers for SBM and DCSBM, respectively, under the edge probability matrix $Q_{1}$. The simulation results reveal two important findings. First, the empirical sizes of $T$, $T_{Han}$ and $T^{aug}_{Hu,boot}$ are close to the 5% nominal level, although $T^{aug}_{Hu,boot}$ performs slightly worse than $T$ and $T_{Han}$. Under SBM, when $K>5$, the sizes of $T_{Hu}$, $T_{Lei}$ and $T_{Lei,boot}$ deviate notably from the nominal level. Under DCSBM, when $K>5$, $T_{Hu}$ exhibits size distortions, which can be much larger than 5%. Additionally, the empirical sizes of $T_{Lei}$ and $T_{Lei,boot}$ deviate significantly from the 5% nominal level, except for $T_{Lei,boot}$ under $K=K_{0}=3$ in Table 3. This is because $T_{Lei}$ and $T_{Lei,boot}$ are not designed for DCSBM. Second, the empirical powers of $T$ and $T^{aug}_{Hu,boot}$ are generally equal to 1, with $T$ performs more powerfully than $T^{aug}_{Hu,boot}$, while $T_{Hu}$ is less powerful. Notably, $T_{Han}$ shows almost no power. This could be due to the fact that the assumptions in Theorem 3.2 of Han et al. (2023) for ensuring the asymptotic power of $T_{Han}$ are not satisfied under the edge probability matrix $Q_{1}$. In addition, under SBM, the powers. of $T_{Lei}$, and $T_{Lei,boot}$ are generally equal to 1. However, under DCSBM, due to the size distortions of $T_{Lei}$ and $T_{Lei,boot}$, we do not further analyze their empirical powers.

Table 4 reports the empirical sizes and powers of DCMM under the edge probability matrix $Q_{2}$. The simulation results show two findings. First, the empirical sizes of $T$ are close to the nominal level 5%. However, $T_{Han}$ exhibits size distortion when $K>5$. This finding indicates that the test $T_{Han}$ may not be suitable for large $K$. Second, the empirical powers of $T$ get larger as $K-K_{0}$ increases. Since the sizes of $T_{Han}$ are distorted for $K>5$ and the powers of $T_{Han}$ are not steady for $K\leq 5$, we do not further analyze their empirical powers. In sum, our proposed test generally outperforms other competing methods under SBM, DCSBM and DCMM with dense networks.

In this section, we consider two types of sparse edge probability matrix $\tilde{Q}_{1}$ and $\tilde{Q}_{2}$. In $\tilde{Q}_{1}$, the edge probability between any two communities $u$ and $v$ is $n^{-5/9}(1+4\times I(u=v))$. In $\tilde{Q}_{2}$, we set $\tilde{Q}_{2,kl}=5n^{-5/9}0.1^{|k-l|}$ if $k\not=l$, and $\tilde{Q}_{2,kl}=5n^{-5/9}(K+1-k)/K$ otherwise. Analogous to Section 3.1, we implement $\tilde{Q}_{1}$ for SBM and DCSBM and $\tilde{Q}_{2}$ for DCMM.

Tables 5-6 report the empirical sizes and powers for SBM and DCSBM, respectively, under the edge probability matrix $\tilde{Q}_{1}$. The results reveal the following two important findings. First, both $T$ and $T_{Han}$ control sizes well. In addition, the sizes of $T_{Hu}$ and $T_{Lei}$ deviate notably from the nominal level. This is likely due to the fact that the tests in Lei (2016) and Hu et al. (2021) are not designed for sparse networks. After applying a bootstrap correction and an augmented-bootstrap procedure, although $T_{Lei,boot}$ and $T^{aug}_{Hu,boot}$ give several reasonable empirical sizes, though both tests lack theoretical justification in sparse networks. Second, our proposed test $T$ is powerful against alternatives, and its empirical power steadily increases as $K-K_{0}$ gets large. This is consistent with our theoretical findings. In contrast, the empirical powers of $T_{Han}$ are low since the two assumptions in Theorem 3.2 of Han et al. (2023) for ensuring the asymptotic power of $T_{Han}$ are not satisfied under $\tilde{Q}_{1}$. Since most of the empirical sizes of the tests proposed by Lei (2016) and Hu et al. (2021) are distorted, we do not further analyze their empirical powers.

Under the sparse DCMM, the results in Table 7 show similar qualitative findings as in Table 4. For example, the empirical sizes of $T$ are close to the nominal level 5% and the empirical sizes of $T_{Han}$ are distorted when $K>5$. In addition, the empirical powers of $T$ get larger as $K-K_{0}$ increases. Since the sizes of $T_{Han}$ are distorted for $K>5$ and the powers of $T_{Han}$ are not steady for $K\leq 5$, we do not further analyze their empirical powers.

To make a more comprehensive comparison, we also carry out simulation studies with different network settings in the supplementary material. Specifically, we consider equal-sized communities with $n_{k}=300$ and the total number of nodes in the network is $n=Kn_{k}$, with $K\in\{2,4,6,8,10\}$. The simulation results of SBM and DCSBM under this network setting and the simulation results of DCMM under edge probabilities $Q_{1}$ and $\tilde{Q}_{1}$ are given in Tables S.1-S.6 of the supplementary material, which show similar findings as in Tables 2-7. In summary, simulation studies demonstrate that our proposed test performs well across three block models under both dense and sparse networks. These findings are consistent with our theoretical results.