Community Detection in Random Networks

Introduction

In recent years, the problem of detecting communities in networks has received a large amount of attention, with important applications in the social and biological sciences, among others (Fortunato, 2010). The vast majority of this expansive literature focuses on developing realistic models of (random) networks (Albert and Barabási, 2002; Barabási and Albert, 1999), on designing methods for extracting communities from such networks (Newman, 2006; Reichardt and Bornholdt, 2006; Girvan and Newman, 2002) and on fitting models to network data (Bickel et al., 2011).

The underlying model is that of graph $\mathcal{G}=(\mathcal{E},\mathcal{V})$, where $\mathcal{E}$ is the set of edges and $\mathcal{V}$ is the set of nodes. For example, in a social network, a node would represent an individual and an edge between two nodes would symbolize a friendship or kinship of some sort shared by these two individuals. In the literature just mentioned, almost all the methodology has concentrated on devising graph partitioning methods, with the end goal of clustering the nodes in $\mathcal{V}$ into groups with strong inner-connectivity and weak inter-connectivity (Lancichinetti and Fortunato, 2009; Newman and Girvan, 2004; Bickel and Chen, 2009).

In this euphoria, perhaps the most basic problem of actually detecting the presence of a community in an otherwise homogeneous network has been overlooked. From a practical standpoint, this sort of problem could arise in a dynamic setting where a network is growing over time and monitored for clustering. From a mathematical perspective, probing the limits of detection (i.e., hypothesis testing) often offers insight into what is possible in terms of extraction (i.e., estimation).

Many existing community extraction methods can be turned into community detection procedures. For example, one could decide that a community is present in the network if the modularity of Newman and Girvan (2004) exceeds a given threshold. To set this threshold, one needs to define a null model. Newman and Girvan (2004) implicitly assume a random graph conditional on the node degrees. Here, we make the simplest assumption that the null model is an Erdös-Rényi random graph (Bollobás, 2001).

In this context, we also touch on another line of work, that of detecting a clique in a random graph — the so-called Planted (or Hidden) Clique Problem (Feige and Ron, 2010; Alon et al., 1998; Dekel et al., 2011). Although the emphasis there is to find the detection performance of computationally tractable algorithms, we mostly ignore computational consideration and simply establish the absolute detection limits of any algorithm whatsoever.

We study detectability in this framework in asymptotic regimes where $n,N\to\infty$, and $p_{0},p_{1}$ may also change; all these parameters are assumed to be functions of $N$. A test $T$ is a function that takes $\boldsymbol{W}$ as input and returns $T=1$ to claim there is a community in the network, and $T=0$ otherwise. The (worst-case) risk of a test $T$ is defined as

2 Closely related work

We take the beaten path, following the standard approach in statistics for analyzing such composite hypothesis testing problems, in particular, the work of Ingster (1997) and others (Donoho and Jin, 2004; Ingster and Suslina, 2002; Hall and Jin, 2010) on the detection of a sparse (normal) mean vector. Most closely related to our work is that of Butucea and Ingster (2011). Specializing their results to our setting, they derive lower bounds and upper bounds for the same detection problem when the graph is directed and the probability of connection under the null (denoted $p_{0}$) is fixed, which is a situation where the graph is extremely dense. Their work leaves out the interesting regime where $p_{0}\to 0$, which leads to a null model that is much more sparse.

3 Main Contribution

Our main contribution in this paper is to derive a sharp detection boundary for the problem of detecting a community in a network as described above. We focus here on the quasi-normal regimeThe quasi-Poisson regime where $np_{0}\to 0$ polynomially fast is qualitatively different and necessitates different proof arguments. This is beyond the scope of this paper and will appear somewhere else. where $np_{0}$ is either bounded away from zero, or tends to zero slowly, specifically,

On the one hand, we derive an information theoretic bound that applies to all tests, meaning conditions under which all tests are powerless. On the other hand, we display a test that basically achieves the best performance possible. The test is the combination of the two natural tests that arise in Butucea and Ingster (2011) and much of the work in that field (Ingster et al., 2010; Arias-Castro et al., 2011):

Total degree test. This test rejects when the total number of edges is unusually large. This is global in nature in that it cannot be directly turned into a method for extraction.

Scan (or maximum modularity) test. This test amounts to turning modularity into a test statistic by rejecting when its maximum value is unusually large. It is strictly speaking the generalized likelihood ratio test under our framework.

We also consider the situation, common in practice, where $p_{0}$ is unknown. Interestingly, the detection boundary becomes larger than in the former setting when $n$ is moderately sparse. We derive the corresponding lower bound in this situation and design a test that achieves this bound. The test is again the combination of the two tests:

Degree variance test. This test is based on the differences between two estimates for the degree variance, an analysis of variance of sorts. (Note that the total degree test cannot be calibrated without knowledge of $p_{0}$.)

Scan test. This test can be calibrated in various ways when $p_{0}$ is unknown, for example by estimation of $p_{0}$ based on the whole graph, or by permutation. We study the former.

Finally, we consider various polynomial-time algorithms, the main one being a convex relaxation of the scan test based on a sparse eigenvalue problem formulation. Our inspiration there comes from the recent work of Berthet and Rigollet (2012). We discuss the discrepancy between the performances of the scan test and the relaxed scan test and compare it with other polynomial-time tests.

We summarize our findings in Tables 1 and 2, where

is (up to $\sqrt{n/2}$ factor) the SNR for detecting the dense subgraph when it is known.

4 Finding a clique

We start the paper by addressing the problem of detecting the presence of a large clique in the graph, and treat it separately, as it is an interesting case in its own right. It is simpler and allows us to focus on the regime where $n/\log N\to\infty$ in the rest of the paper. We establish a lower bound and prove that the following (obvious) test achieves that bound:

Clique number test. This tests rejects when the size of the clique number of the graph is unusually large. It can be calibrated without knowledge of $p_{0}$, for example by permutation, but we do not know of a polynomial-time algorithm that comes even close.

5 Content

In Section 2, we consider the problem of detecting the presence of a large clique and analyze the clique number test. In Section 3, we consider the more general problem of detecting a densely connected subgraph and analyze the total degree test and the scan test. The more realistic situation of unknown $p_{0}$ is handled in Section 4. In Section 5.2, we investigate polynomial-time tests. We then discuss our results and the outlook in Section 6. The technical proofs are postponed to Section 7.

6 General assumptions and notation

We assume throughout that $N\to\infty$ and the other parameters $n,p_{0},p_{1}$ (and more) are allowed to change with $N$, unless specified otherwise. This dependency is left implicit. In particular, we assume that $n/N\to 0$, emphasizing the situation where the community to be detected is small compared to the size of the whole network. (When $n$ is of the same order as $N$, the total degree test is basically optimal.) We assume that $p_{0}$ is bounded away from 1, which is the most interesting case by far, and that $N^{2}p_{0}\to\infty$, the latter implying that the number of edges in the network (under the null) is not bounded. We also hypothesize that either $p_{1}=1$ or $n\to\infty$ with $n^{2}p_{1}\to\infty$, there is a non-vanishing chance that the community does not contain any edges, precluding any test to be powerful.

We use standard notation such as $a_{n}\sim b_{n}$ when $a_{n}/b_{n}\to 1$; $a_{n}=o(b_{n})$ when $a_{n}/b_{n}\to 0$; $a_{n}=O(b_{n})$ when $a_{n}/b_{n}$ is bounded; $a_{n}\asymp b_{n}$ when $a_{n}=O(b_{n})$ and $b_{n}=O(a_{n})$; $a_{n}\prec b_{n}$ when there exists a positive constant $C$ such that $a_{n}\leq Cb_{n}$ and $a_{n}\succ b_{n}$ when there exists a positive constant $C$ such that $a_{n}\geq Cb_{n}$. For an integer $n$ let $n^{(2)}=n(n-1)/2$. For two distributions $L_{1}$ and $L_{2}$ on the real line, let $L_{1}*L_{2}$ denote their convolution, which is the distribution of the sum two independent random variables $X_{1}\sim L_{1}$ and $X_{2}\sim L_{2}$.

Because of its importance in describing the tails of the binomial distribution, the following function — which is the relative entropy or Kullback-Leibler divergence of ${\rm Bern}(q)$ to ${\rm Bern}(p)$ — will appear in our results:

Detecting a large clique in a random graph

We start with specializing the setting to that of detecting a large clique, meaning we consider the special case where $p_{1}=1$. In this section, $n$ is not necessarily increasing with $N$.

We establish the detection boundary, giving sufficient conditions for the problem to be too hard for any test, meaning that all tests are asymptotically powerless.

All tests are asymptotically powerless if

The result is, in fact, very intuitive. Condition (3) implies that, with high probability under the null, the clique number is at least $n$, which is the size of the implanted clique under the alternative. This is a classical result in random graph theory, and finer results are known — see (Bollobás, 2001, Chap. 11). The arguments underlying Theorem 1 are, however, based on studying the likelihood ratio test when a uniform prior is assumed on the implanted clique $S$, which is the standard approach in detection settings; see (Lehmann and Romano, 2005, Ch. 8). In this specific setting, the second moment method — which consists in showing that the variance of the likelihood ratio tends to 0 — suffices.

2 The clique number test

Computational considerations aside, the most natural test for detecting the presence of a clique is the clique number test defined in the Introduction. We obtain the following.

The proof is entirely based on the fact that, when (4) holds, the clique number under the null is at most $n-1$ with high probability (Bollobás, 2001, Th. 11.6), while it is at least $n$ under the alternative. (Thus the proof is omitted.) We conclude that the clique number test is seen to achieve the detection boundary established in Theorem 1.

Detecting a dense subgraph in a random graph

We now consider the more general setting of detecting a dense subgraph in a random graph. We start with an information bound that applies to all tests, regardless of their computational requirements. We then study the total degree test and the scan test, showing that the test that combines them with a simple Bonferroni correction is essentially optimal.

When assuming infinite computational power, what is left is the purely statistical challenge of detecting the subgraph. For simplicity, we assume that $n$ is not too small, specifically,

though our result below partially extends to this, particularly when $p_{1}$ is constant. As usual, a minimax lower bound is derived by choosing a prior over the composite alternative. Assuming that $p_{0}$ and $p_{1}$ are known, because of symmetry, the uniform prior over the community $S$ is least favorable, so that we consider testing

Assuming (5) and (1) hold, all tests are asymptotically powerless if

Conditions (7) and (8) have their equivalent in the work of Butucea and Ingster (2011). That said, (8) is more complex here because of the different behaviors of the entropy function according to whether $p_{1}/p_{0}$ is small or large — corresponding to the difference between large deviations and moderate deviations of the binomial distribution. Only in the case where $p_{1}/p_{0}\to 1$ is the normal approximation to the binomial in effect.

To better appreciate (8), note that it is equivalent to

In (9), $np_{0}$ is larger and only the moderate deviations of the binomial distribution are involved, while in (10), $np_{0}$ is smaller and the large deviations come into play.

Theorem 2 happens to be sharp because, as we show next, the test that combines the total degree test and the scan test is asymptotically powerful when the conditions (7) and (8) are — roughly speaking — reversed.

2 The total degree test

The total degree test rejects for large values of

The resulting test is exceedingly simple to analyze, since

It is equally straightforward to show that the total degree has risk strictly less than one — meaning has some non-negligible power — when the same ratio tends to a positive and finite constant, while it is asymptotically powerless when that ratio tends to zero.

3 The scan test

The scan test is another name for the generalized likelihood ratio test, and corresponds to the test that is based on the maximum modularity. It is particularly simple when $p_{0}$ is known, as it rejects for large values of

Unlike the total degree (11), the scan statistic (14) has an intricate distribution as the partial sums $W_{S}$ are not independent. Nevertheless, the union bound and standard tail bounds for the binomial distribution lead to the following result.

4 The combined test

Having studied these two tests individually, we are now in a position to consider them together, by which we mean a simple Bonferroni combination which rejects when either of the two tests rejects. Looking back at our lower bound and the performance bounds we established for these tests, we come to the following conclusion. When the limit in (7) is infinite — yielding (13) — then the total degree test is asymptotically powerful by Proposition 2. When the limit inferior in (8) exceeds one — yielding (15) — then the scan test is asymptotically powerful by Proposition 3.

5 Adaptation to unknown n𝑛n

The scan statistic in (14) requires knowledge of $n$. When this is unknown, the common procedure is to combine the scan tests at all different sizes $n$ using a simple Bonferroni correction. This is done in (Butucea and Ingster, 2011), with the conclusion that the resulting test is essentially as powerful as the individual tests. It is straightforward to see that, here too, the tail bound used in the proof of Proposition 3 allows for enough room to scan over all subgraphs of all sizes.

Although it leads to interesting mathematics, the setting where $p_{0}$ is known is, for the most part, impractical. In this section, we evaluate how not knowing $p_{0}$ changes the difficulty of the problem. In fact, it makes the problem strictly more difficult in the denser regime.

There are (at least) two ways of formalizing the situation where $p_{0}$ is unknown. In the first option, we still consider the exact same hypothesis testing problem, but maximize the risk over relevant subsets of $p_{0}$’s and $p_{1}$’s, since now even the null hypothesis is composite. In the second option — which is the one we detail — for a given pair of probabilities $0<p^{\prime}_{0}\leq p_{1}<1$, we consider testing

Note that, in this setting, we still assume that $p_{0},p_{1},n$ are known to the statistician. By design, the graph has the same expected total degree under the null and under the alternative hypotheses, that is we have

The risk of a test $T$ for this problem is defined as

We say that the a sequence of tests $(T_{N})$ is asymptotically powerful for the problem with fixed expected total degree (resp. powerless) if $\gamma_{N}^{\prime}(T_{N})\rightarrow 0$ (resp. $\gamma_{N}^{\prime}(T_{N})\rightarrow 1$).

We first compute the detection boundary for this problem and then exhibit some tests achieving this detection boundary. Interestingly, these tests do not require the knowledge of $p_{0}$ and $p_{1}$, or even $n$, so that they can be used in the original setting (6) when these parameters are unknown.

all tests are asymptotically powerless for the problem (16) if

Comparing with Theorem 2, where $p_{0}$ is assumed to be known, the condition (18) is substantially weaker than the corresponding condition (7), while we shall see in the proof that (19) is comparable to (8). That said, when $n^{2}<N$, the entropy condition (8) is a stronger requirement than either (7) or (18), implying that the setting where $p_{0}$ is known and the setting where unknown are asymptotically as difficult in that case.

2 Degree variance test

By construction, the total degree $W$ has the same expectation under the null and under the alternative in the testing problem with fixed expected total degree — and same variance also up to second order — making it difficult to see how to fruitfully use this statistic in this context.

We design instead a test based on comparing the two estimators for the node degree variance, not unlike an analysis of variance. Let

denote the degree of node $i$ in the whole network. The first estimate is simply the maximum likelihood estimator under the null

The second estimator is some sort of sample variance, modified to account for the fact that the $W_{i\cdot}$ are not independent

Assume that $p_{0}\succ 1/N$. The degree variance test is asymptotically powerful under fixed expected total degree if

The test based on $V^{*}$ achieves the part (18) of the detection boundary. We note that computing $V^{*}$ does not require knowledge of $p_{0}$, $p_{1}$ or $n$, and in fact, its calibration can be done without any knowledge of these parameters via a form of parametric bootstrap, as we do for the scan test below.

3 The scan test

When $p_{0}$ is not available a priori, we have at least three options:

Estimate $p_{0}$. We replace $p_{0}$ with its maximum likelihood estimator under the null, i.e., $\hat{p}_{0}=W/N^{(2)}$, and then compare the magnitude of the observed scan statistic (14) with what one would get under a random graph model with probability of connection equal to $\hat{p}_{0}$.

Generalized likelihood ratio test. We simply implement the actual generalized likelihood ratio test (Kulldorff, 1997), which rejects for large values of

where $h(p):=p\log p+(1-p)\log(1-p)$, $\hat{p}_{0}$ as above, and

which are the maximum likelihood estimates of $p_{1}$ and $p_{0}$ for a given subset $S$.

Calibration by permutation. We compare the observed value of the scan statistic to simulated values obtained by generating a random graph with either the same number of edges — which leads to a calibration very similar to the first option — or the same degree distribution — which is the basis for in the modularity function of Newman and Girvan (2004).

Assume that $\lim\inf p_{0}N^{2}/n>1$. The scan test calibrated by estimation of $p_{0}$ is asymptotically powerful for fixed expected total degree if

Hence, the scan test calibrated by estimation of $p_{0}$ achieves the entropy condition (8) without requiring the knowledge of $p_{0}$ or $p_{1}$. We mention that adaptation to unknown $n$ may be achieved as described in Section 3.5.

A combination of the degree variance test and of the scan test calibrated by estimation of $p_{0}$ is seen to achieve the detection boundary established in Theorem 3, without requiring knowledge of $p_{0}$ or $p_{1}$, or even $n$.

Testing in polynomial-time

While computing the total degree (11) or the degree variance statistic (21) can be done in linear time in the size of the network, i.e., in $O(N^{2})$ time, computing the scan statistic (14) is combinatorial in nature and there is no known polynomial-time algorithm to compute it. To see this, note that the ability to compute (14) in polynomial-time implies the ability to compute the size of the largest clique in the graph, since this is equal to

and computing the size of the largest clique in a general graph in known to be NP-hard (Karp, 1972), and even hard to approximate (Zuckerman, 2006).

A question of particular importance in modern times is determining the tradeoff between statistical performance and computational complexity. At the most basic level, this boils down to answering the following question: What can be done in polynomial-time?

We now suggest a convex relaxation to the problem of computing the scan statistic. To do so, we follow the footsteps of Berthet and Rigollet (2012), who consider the problem of detecting a sparse principal component based on a sample from a multivariate Gaussian distribution in dimension $N$. Assuming the sparse component has at most $n$ nonzero entries, they show that a near-optimal procedure is based on the largest eigenvalue of any $n$-by-$n$ submatrix of the sample covariance matrix. Computing this statistic is NP-hard, so they resort to the convex relaxation of d’Aspremont et al. (2007), which they also study. We apply their procedure to $\boldsymbol{W}^{2}$.

where $\boldsymbol{B}_{S}$ denotes the principal submatrix of $\boldsymbol{B}$ indexed by $S\subset\{1,\dots,N\}$ and $\lambda^{\rm max}(\boldsymbol{B})$ the largest eigenvalue of $\boldsymbol{B}$. d’Aspremont et al. (2007) relaxed this to

When $p_{0}$ is unknown, we estimate $p_{0}$ as we did for the scan test in Proposition 5, and then calibrate the statistic by Monte Carlo, effectively using a form of parametric bootstrap.

Assume that (1) holds and $n\leq N^{1/2-t}$ for some $t>0$. Then, the relaxed scan test is powerful if

To gain some insights on the relative performance of the scan test and the relaxed scan test, let us assume that $n^{2}\ll N$, and $np_{0}\gg\log(N/n)$. Applying Proposition 3 (or Proposition 5) in this setting, we find that the scan test is asymptotically powerful when

Thus, comparing with (25), we lose a factor $\sqrt{N/\log(N)}$ when using the relaxed version. In the denser regime where $n^{2}\gg N\log(N)$, the total degree test and degree variance test both have stronger theoretical guarantees established in Proposition 2 and Proposition 4 respectively. Below we explain why the $\sqrt{N/\log(N)}$ loss is not unexpected.

More generally, we may want to characterize the sequences $(n,N,p_{0},p_{1})$ for which there are asymptotically powerful tests running in polynomial time. In our findings, the only situation where we found this to be true was in the dense regime, where the total degree test is both powerful in the large-sample limit and computable in polynomial time. (Replace this with the degree variance test when $p_{0}$ is unknown.)

2 Other polynomial-time tests

Perhaps the first computationally-feasible test that comes to mind in the sparse regime is the test based on the maximum degree

where $W_{i\cdot}$ is the degree of node $i$ in the graph, defined in (20).

The maximal degree test is asymptotically powerful if $p_{0}\gg\log(N)/N$ and

Under condition (1), the maximal degree test is asymptotically powerless if $\lim\sup\log(n)/\log(N)<1$ and

Comparing with Propositions 2 and 6, we observe that the maximum degree test is either less powerful than the relaxed scan test (when $n\leq N^{1/2-t}$ for any $t>0$) or less powerful that the total degree test (when $n\gg\sqrt{N/\log(N)}$). For unknown $p_{0}$, the maximum degree test is also less powerful than the degree variance test.

2.2 Densest subgraph test

Another possible avenue for designing computationally tractable tests for the problem at hand lies in algorithms for finding dense subgraphs of a given size. We follow (Khuller and Saha, 2009), where the reader will find appropriate references and additional results. Define the density of a subgraph $S\subset\mathcal{V}$ as

Finding $S\subset\mathcal{V}$ that maximizes $h(S)$ may be done in polynomial-time.

The densest subgraph test is powerful if $\lim\inf\frac{np_{1}}{Np_{0}}>1$.

The condition $\lim\inf\frac{np_{1}}{Np_{0}}>1$ is stronger than what we have obtained for the relaxed scan test (25) in the sparser case ($n\leq N^{1/2-t}$ for any $t>0$) and than what we have obtained for the total degree test (13) and the degree variance test (22) in the less sparse case $(n\gg\sqrt{N})$. If $np_{1}/Np_{0}\rightarrow 0$, then the densest subgraph statistic seems to behave like the total degree statistic and we therefore expect similar performances although we have no proof of this statement.

In order to improve the power, we would like to restrict our attention to subgraphs of size $n$ (assumed known for now) and use $\max_{|S|=n}h(S).$ Computing this, however, is NP-hard, and there is no known polynomial-time approximation within a constant factor. Nevertheless, the following variant statistic $\max_{|S|\geq n}h(S)$ can be approximated within a constant factor in polynomial-time. However, the power of the resulting test is not improved. Since the statistic $\max_{|S|\geq n}h(S)$ may only be approximated within a constant factor, the resulting test is powerful only if $np_{1}\geq CNp_{0}$ where $C$ is positive constant that depends on this approximation factor.

Discussion

With this paper, we have established the fundamental statistical (information theoretic) difficulty of detecting a community in a network, modeled as the detection of an unusually dense subgraph within an Erdös-Rényi random graph, in the quasi-normal regime where $np_{0}$ is not too small as made explicit in (1). The quasi-Poisson regime, where $np_{0}$ is smaller, requires different arguments and the application of somewhat different tests, and this will be detailed in a separate paper under preparation.

For the time being, in the quasi-normal regime, we learned the following. In the moderately sparse setting — $n\gg N^{2/3})$ for known $p_{0}$ and $n\gg N^{3/4}$ for unknown $p_{0}$ — this detection boundary is achieved by polynomial-time tests. In the sparser setting, there is a large discrepancy between the information theoretic boundaries and performances of known polynomial tests, which in view of the Planted Clique Problem, is not surprising.

It is of great interest to study this optimal detection boundary, this time under computational constraints, a theme of contemporary importance in statistics, machine learning and computer science. This promisingly rich line of research is well beyond the scope of the present paper.

Proofs

The following is Chernoff’s bound for the binomial distribution. Remember the definition of $H$ in (2).

For any positive integer $n$, any $q,p_{0}\in(0,1)$, we have

A consequence of Chernoff’s bound is Bernstein’s inequality for the binomial distribution.

For positive integer $n$, any $p_{0}\in(0,1)$ and any $x>0$, we have

We will need the following basic properties of the entropy function.

For $p_{0}\in(0,1)$, $H(q)$ is convex in $q\in$. Moreover,

We will also use the following upper bound on the binomial coefficients.

The next result bounds the hypergeometric distribution with the corresponding binomial distribution. Let ${\rm Hyp}(N,m,n)$ denotes the hypergeometric distribution counting the number of red balls in $n$ draws from an urn containing $m$ red balls out of $N$.

${\rm Hyp}(N,m,n)$ is stochastically smaller than ${\rm Bin}(n,m/(N-m))$.

Suppose the balls are picked one by one without replacement. At each stage, the probability of selecting a red ball is smaller than $m/(N-m)$. The result follows. ∎

2 Proof of Theorem 1

Following standard lines, we start by reducing the composite alternative to a simple alternative by considering the uniform prior $\pi$ on subsets $S\subset[N]:=\{1,\dots,N\}$ of size $|S|=n$. The resulting likelihood ratio is

which is the observed number of cliques of size $n$ divided by the expected number under the null.

The risk of any test for the original problem is well-known to be bounded from below by the risk of the likelihood ratio test $\{L>1\}$ for this ‘averaged’ problem, which is equal to

Therefore, it suffices to show that $\gamma_{L}\to 1$. Here we use arguably the simplest method, a second moment argument, which is based on the fact that

where $\pi[\cdot]$ denotes the expectation with respect to $\pi$. Hence, by Fubini’s theorem, we have

where $K:=|S_{1}\cap S_{2}|$. Indeed, the event $\{W_{S_{1}}=W_{S_{2}}=n^{(2)}\}$ means that all edges between pairs of nodes in $S_{1}$ exist, and similarly for $S_{2}$, and there are a total of $n(n-1)+K(K-1)/2$ such edges.

Before going further, note that (3) and (30) imply that

In particular, this means that $n\leq 3\log N$, eventually, and therefore

Since $K\sim{\rm Hyp}(N,n,n)$, by Lemma 5, $K$ is stochastically bounded by $\text{Bin}(n,\rho)$, where $\rho:=n/(N-n)$. Hence, with and Lemma 1, we have

Now, using Lemma 3 and (33), for $k\geq 2$ we get

For $a>0$ fixed, the function $x\to ax-\log x$ is decreasing on $(0,1/a)$ and increasing on $(1/a,\infty)$. Therefore,

By (32), the second term in the maximum tends to $\infty$. This also the case of the first term, since

with the second difference bounded from below. Hence, $\omega\to\infty$. Hence, the sum in (35) is bounded by

3 Proof of Theorem 2

We assume that (1), (7) and (8) hold. We reduce the composite alternative to a simple alternative by considering the uniform prior $\pi$ on subsets $S\subset[N]:=\{1,\dots,N\}$ of size $|S|=n$. The resulting likelihood ratio is

where $\pi[\cdot]$ is the expectation with respect to $S\sim\pi$, $A=(W_{i,j}:1\leq i<j\leq N)$ and

which is the moment generating function of ${\rm Bern}(p_{0})$.

Still leaving $p_{0}$ implicit, let $H_{p_{0}}(q)$ be short for $H(q)$. It is well-known that $H$ is the Fenchel-Legendre transform of $\Lambda$; more specifically, for $q\in(p_{0},1)$,

The second moment argument used in Section 7.2 is also applicable here, though it does not yield sharp bounds. In Case 1 below (see Subsection 7.3.3), which is the regime where the moderate deviations of the binomial come into play, this method leads to a requirement that the limit superior in (8) be bounded by $1/2$ instead of 1. And, worse than that, in Case 3 below, which is the regime where the large deviations of the binomial are involved, it does not provide any useful bound whatsoever.

Fortunately, a finer approach was suggested by Ingster (1997). The refinement is based on bounding the first and second moments of a truncated likelihood ratio. Here we follow Butucea and Ingster (2011). They work with the following truncated likelihood

for some $\eta_{0}\in(0,1)$ fixed. Notice that (5) and (8) imply that $H(p_{1})\to 0$, which by Lemma 3 forces either $p_{1}/p_{0}\to 1$ or $p_{1}\to 0$; in any case, $p_{1}$ is bounded away from 1 this time.

In what follows, we provide the general arguments while the proof of the technical results (Lemmas 6-8) is postponed to the end of the section. To show these technical results, we divide the analysis depending on the behaviour of $p_{1}/p_{0}$

In regime (41), the moderate deviations of the binomial distribution dominate and these are asymptotically equivalent to normal (Gaussian) deviations; in particular, it is in this setting (with $p_{0}$ constant) that Butucea and Ingster (2011) successfully reduce the binary setting to the normal setting. In regime (43), the large deviations of the binomial distribution dominate, which are not alike the normal deviations and lead to a completely different regime. Regime (42) is intermediary and requires special treatment.

First, we need some notations to introduce $\Gamma_{S}$. Define the numbers

We have $k_{\min}\rightarrow\infty$, $k_{\min}\sim k_{*}$, and $\log(n/k_{\min})=o\left[\log(N/n)\right]$.

This construction is possible by the following lemma, which serves as a definition.

For any integer $k$ between $k_{\min}+1$ and $n$, there exists a unique $q_{k}\in(p_{0},1)$ such that

Moreover, $q_{k}$ satisfies $\theta_{q_{k}}\leq 2\theta$.

3.2 Second truncated moment

and note that $W_{S}=W_{S\times S}$. We use the decomposition

and the independence of the random variables on the RHS of (49), to get

The first two equalities are due to the fact that the likelihood integrates to one.

To bound ${\rm III}$, we follow Butucea and Ingster (2011), with a twist. When $K\leq k_{\rm min}$, we will use the obvious bound:

When $K>k_{\rm min}$, we use a different bound. For any $\xi\in(0,2\theta)$, we have

where the expectation is with respect to $\pi^{\otimes 2}$.

Let $b$ be an integer sequence such that $b\to\infty$ so slowly that

which is possible because of (7). Recall that $\rho=n/(N-n)$ and define $k_{0}=\lceil bn\rho\rceil$. We divide the expectation into two parts: $K\leq k_{0}$ and $k_{0}+1\leq K\leq n$. When $k_{0}=1$, we simply have

When $k_{0}\geq 2$, we use the expression (50) of $\Delta$ to derive

When $k_{0}+1\leq K\leq\lfloor k_{\rm min}\rfloor$, we use the bound (34) and the identity $(1-x)\log(1-x)\geq-x$, to get

For $a>0$ fixed, the function $f(x)=ax-\log x$ is decreasing on $(0,1/a)$ and increasing on $(1/a,\infty)$. Therefore, for $k_{0}+1\leq k\leq n$,

From what we did previously, we know that $\Delta(k_{0}-1)=o(1)$, so that the first term in the maximum tends to $\infty$. Therefore, it suffices to look at the second term in the maximum. In fact, $k_{\min}$ has been precisely defined in (45) to make this second term diverge. Indeed, by (45) and (50), we have

By Lemma 6 and since $\rho\asymp n/N=o(1)$, we get $\log(k_{\min}/(n\rho))-\log\left(\frac{Nk^{*}}{n^{2}}\right)=o(1)$. Consequently,

which goes to $-\infty$ uniformly over all $k$ between $\lfloor k_{\min}\rfloor+1$ and $n$ by the definition (47) of $q_{k}$ and by the control of $H_{p_{1}}(q_{k})$ from Lemma 8. Hence, the sum above tends to zero.

3.3 Proof of Lemma 6

We only need to prove that $k_{*}\rightarrow\infty$ and that $\log(n/k_{*})=o\left[\log(N/n)\right]$ since

We divide the analysis into three cases depending on the behaviour of $p_{1}/p_{0}$.

CASE 1: $p_{1}/p_{0}\rightarrow 1$. Then, Lemma 3 tells us $\log\left(1+\frac{(p_{1}-p_{0})^{2}}{p_{0}(1-p_{0})}\right)\sim 2H(p_{1})$, so that

since $H(p_{1})<2(1-\eta_{0})\log(N/n)/n$ by (40). Hence $k^{*}\to\infty$ and $\log(n/k^{*})=O(1)$.

CASE 2: $p_{1}/p_{0}\to r$ with $r\in(1,\infty)$. Since $H(p_{1})$ goes to , this enforces $p_{0}\to 0$. Using Lemma 3 and (40), we derive that

Hence, $\log(N/n)/p_{0}\succ n$. Going back to the definition of $k_{*}$, we derive that

CASE 3: $p_{1}/p_{0}\to\infty.$ Again, we have $p_{0}\to 0$. By Lemma 3 and (40),

where the last part comes from (1). Hence,

Since (54) also implies that $p_{1}\prec\log(N/n)/n$, we have

so that $\log(n/k^{*})\leq\log\left[\log(N/n)/(np_{0})\right]\vee 0+O(1)=o[\log(N/n)]$ by (1).

3.4 Proof of Lemma 7

which implies $\theta_{\widetilde{q}}=2\theta$. Because $H$ is strictly increasing and continuous on $(p_{0},\widetilde{q})$, to prove the existence of $q_{k}$ it suffices to show that

As in the proof of the previous lemma, we consider different cases depending on the convergence of $p_{1}/p_{0}$ and of $p_{1}^{2}/p_{0}$. In all cases, except the last one, we show that

for some fixed $\varepsilon>0$, which suffices by Lemma 6. If $k_{*}<n$, so that $k_{*}\geq\frac{2}{\Delta}\log(N/n)$ (with $\Delta$ defined in (50)). If $k^{*}=n$ and $k_{\min}<n$, we have $k_{*}\geq\frac{2}{\Delta}\log(N/n)(1+o(1))$. Hence, it is enough the prove that

The last case, Case 3(c) below — which corresponds to $p_{0}=o(\log(N/n)/n)$ and $\log(n)=o(\log(N))$ — requires a more delicate treatment.

CASE 1: $p_{1}/p_{0}\rightarrow 1.$ By the definition of $\widetilde{q}$, we have $\widetilde{q}-p_{0}=(p_{1}-p_{0})\left[1+\frac{p_{1}(1-p_{1})}{p_{0}-2p_{0}p_{1}+p_{1}^{2}}\right]\sim 2(p_{1}-p_{0})$ and Lemma 3 tells us that

CASE 2: $p_{1}/p_{0}\to r$ with $r\in(1,\infty).$ Note that this forces $p_{1}\rightarrow 0$. Here (55) implies that $\widetilde{q}/p_{0}\sim(p_{1}/p_{0})^{2}$, so that $H(\widetilde{q})\sim p_{0}\left(r^{2}\log(r^{2})-r^{2}+1\right)$ by Lemma 3. At the same time, $\Delta\sim p_{0}(r-1)^{2}$, so that

CASE 3(a): $p_{1}/p_{0}\to\infty$ and $p_{1}^{2}/p_{0}\to 0.$ We have $\widetilde{q}/p_{0}\sim(p_{1}/p_{0})^{2}\to\infty$, implying that $H(\widetilde{q})\sim\widetilde{q}\log(\widetilde{q}/p_{0})\sim 2(p_{1}^{2}/p_{0})\log(p_{1}/p_{0})$ by Lemma 3. Also, $\Delta\sim\log(1+p_{1}^{2}/p_{0})\sim\frac{p_{1}^{2}}{p_{0}}$. Hence, $H(\widetilde{q})\gg\Delta$.

CASE 3(b): $p_{1}/p_{0}\to\infty$ and $p_{1}^{2}/p_{0}\to r_{2}\in(0,\infty).$ Here $\widetilde{q}\to 1/(1+r_{2})$, so that $\widetilde{q}/p_{0}\to\infty$, implying that $H(\widetilde{q})\sim\widetilde{q}\log(\widetilde{q}/p_{0})\asymp\log(1/p_{0})\to\infty$. Also, $\Delta\to\log(1+r_{2})$. Hence, $H(\widetilde{q})\gg\Delta$.

CASE 3(c): $p_{1}^{2}/p_{0}\to\infty$. By Definition (44) of $k_{*}$, this implies $k_{*}<n$. By definition of $\widetilde{q}$, we have $\widetilde{q}=1-o(1)$, so that $H(\widetilde{q})\sim\log(1/p_{0})$. On the other hand, $\Delta\sim\log(p_{1}^{2}/p_{0})$. Therefore,

so that we are done if $\log(p_{1})/\log(p_{0})$ is bounded away from 0. When $\log(p_{1})/\log(p_{0})=o(1)$, we need to work a little harder and perform a second order analysis. From the definition of $\widetilde{q}$, we derive $1-\widetilde{q}\leq\frac{p_{0}}{p_{1}^{2}}$, so that

since $p_{1}^{2}/p_{0}\to\infty$. We use this lower bound to get

where we used Lemma 6 in the second inequality. In order to conclude, because of (5), it suffices to show that

The bound (54), coupled with $p_{1}\gg\sqrt{p_{0}}$, implies that $2\log\log(N/n)-\log(n)+\log(1/(np_{0}))\to\infty$. This, together with (1), forces $\log(n)=o\left[\log(N/n)\right]$. Hence,

so that, because of (5) and (54), we have

3.5 Proof of Lemma 8

Hence, we may lower bound $H_{p_{1}}(q_{k})$as follows:

where the last inequality follows from Lemma 6 and the fact that $k\geq k_{\rm min}$.

where $f(x):=x\log(x)-x+1$. Since $f$ is convex and satisfies $f^{\prime}(x)=\log(x)$, we have $f(x)-f(r)\leq(x-r)\log(x)$ for $x\geq r\geq 1$. Taking $x=q_{k}/p_{0}$ and using (59), we derive that

eventually. As a consequence, $q_{k}/p_{0}$ is also lower bounded away from $r$. Thus, $\log(q_{k}/p_{1})/\log(q_{k}/p_{0})$ is bounded away from by a constant that only depends on $r$ and $\eta_{0}$. We then derive,

Now, for the entropy $H_{p_{1}}(q_{k})$, by Lemma 3 we have

as $\log(1+x)\leq x$. Since $H(p_{1})\sim p_{0}f(r)$, we get by (59) and (60)

where the third line follows from the fact that the $q_{k}/p_{0}$ is lower bounded away from $r$ and that $f(x)\sim x\log(x)$ when $x\rightarrow\infty$. Thus,

CASE 3: $p_{1}/p_{0}\rightarrow\infty$. As in the proof of Lemma 7 (Case 2), we have $p_{1}\to 0$. We start as in the two previous cases, again using Lemma 3 to get the asymptotic expressions of the entropies. By (57), $q_{k}/p_{0}\geq p_{1}/p_{0}\to\infty$, so that

Turning to the entropy $H_{p_{1}}(q_{k})$, we have $H_{p_{1}}(q_{k})\geq q_{k}\log(q_{k}/p_{1})-q_{k}+(1-q_{k})p_{1}$. Using Lemma 7 and Lemma 3, we get

We saw in the proof of Lemma 6 (Case 3) that $\log(p_{1}/p_{0})=o[\log(N/n)]$, so we conclude that

4 Proof of Theorem 3

Under conditions (17), (18) and (19), we have

As in the proof of Theorem 2, for $n$ large enough, we may assume that there exists $\eta_{0}>0$ such that

We consider the likelihood ratio under the uniform prior:

All these expectations only depend on $S_{1}$ and $S_{2}$ through $K$.

The term ${\rm III}$ already appeared in the proof of Theorem 2, where we saw that ${\rm III}\leq\exp\left(\Delta K^{(2)}\right)$ for $K\leq k_{\min}$, and that ${\rm III}\leq\exp\left(\Delta_{K}K^{(2)}\right)$ for $K>k_{\min}$ where $k_{\min}$ is defined in (45), while $\Delta$ and $\Delta_{k}$ are defined in (50) and (51), respectively.

Since the expectations inside ${\rm I}$ and ${\rm II}$ are not thresholded, we easily compute these terms:

Since $(p_{1}-p^{\prime}_{0})=(p_{1}-p_{0})(1-n^{(2)}/N^{(2)})^{-1}$, we derive

By Lemma 10, $\Delta n^{2}/N\rightarrow 0$ and by (63), $\Delta n^{3}/N^{3/2}\rightarrow 0$. Hence, there exists $b\rightarrow\infty$ such that $\Delta\frac{n^{3}}{N^{3/2}}b^{2}\rightarrow 0$ and $\Delta b\frac{n^{2}}{N}\to 0$. Define $k^{\prime}_{0}=\lfloor\frac{n^{2}}{N}+\frac{n}{N^{1/2}}b\rfloor$ and $k_{0}=\lfloor b\frac{n^{2}}{N}\rfloor$. We can take $b$ small enough to constrain $k_{0}\leq n/2$.

Under the entropy condition (64), the bounds (70) and (71) hold.

In fact the main difference between the proof of Theorem 2 and the current proof lies in the control of the two expectations in (68) and (69). Here, we need to carefully upper bound $V_{K}$ in order to balance $\Delta K^{(2)}$. Using the identity $\log(1+x)\leq x$, the property $\log(V_{k})\leq 0$ for $k\leq n/2$ — easily verified from the definition (67) — and $k_{0}\leq n/2$, we get

for $k\leq k_{0}$. In the sequel, we note

so that $2\Delta^{\prime}\sim\Delta$. Thus, we get for any $k\leq k_{0}$,

since $\Delta^{\prime}n^{3}/N^{2}\prec\Delta n^{3}/N^{2}\leq\frac{(p_{1}-p_{0})^{2}}{p_{0}(1-p_{0})}\frac{n^{3}}{N^{2}}=o(n/N)=o(1)$ by Lemma 10.

Using this upper bound (72), we consider the expectation in (68)

since $\Delta^{\prime}\frac{b^{2}n^{2}}{N}\prec\Delta\frac{b^{2}n^{2}}{N}=o(1)$ and $\Delta^{\prime}\frac{bn^{3}}{N^{3/2}}\ll\Delta\frac{b^{2}n^{3}}{N^{3/2}}=o(1)$ by definition of $b$. We have proved (68).

To prove (69), we apply the Cauchy-Schwarz inequality and we upper bound $K$ by $k_{0}\leq bn^{2}/N$,

since $\Delta^{\prime}b(\frac{n^{2}}{N}\vee\frac{n^{3}}{N^{3/2}})=o(1)$ by definition of $b$. All in all, we have proved (69).

The second convergence is a straightforward consequence of the definition of $p_{0}$, (18) and (19), so that we focus on the first result. Let us compute the difference between the two entropies $H_{p^{\prime}_{0}}(p_{1})$ and $H_{p_{0}}(p_{1})$.

Arguing as in the proof of Lemma 10, we note that, under conditions (17) and (64),

so that $H_{p^{\prime}_{0}}(p_{1})-H_{p_{0}}(p_{1})=o(1/N)=o\left(\log(N/n)/n\right)$, since $n\leq N$.

4.2 Proof of Lemma 10

CASE 1: $p_{1}/p_{0}\rightarrow 1$. By condition (64),

CASE 2: $p_{1}/p_{0}\rightarrow c\in(1,\infty)$. Similarly,

CASE 3: $p_{1}/p_{0}\rightarrow\infty$. We have

By condition (64) and $p_{1}\log(p_{1}/p_{0})\sim H(p_{1})\prec\frac{1}{n}\log(N/n)$. Dividing this inequality by $p_{0}$ and then taking the logarithm leads to $\log(p_{1}/p_{0})\prec\log\log(N/n)+\log(1/np_{0})=o(\log(N/n))$ by (17). It follows that $p_{1}/p_{0}=o(\sqrt{N/n})$ and $p_{1}=o(\log(N/n)/n)$. All in all, we conclude that

4.3 Proof of Lemma 11

Let us first consider (71). Using the upper bound $\log(V_{k})=o(k)$, we only have to prove that

We have shown in the proof of Theorem 2 (only using the entropy condition) that

tends to zero since all the terms $\Delta_{k}\frac{k-1}{2}-\log\left(\frac{k}{n\rho}\right)+1$ simultaneously go to $-\infty$ for $k=\lfloor k_{\min}\rfloor+1,\ldots,n$. Consequently,

Let us turn to (70) following again the same arguments as in the proof of Theorem 2.

Hence, as in the previous proof, we only need to prove that

goes to $\infty$. By definition of $k_{0}$, we have $\Delta k_{0}=o(1)$, while we showed in the previous proof that $\log\left(\frac{k_{\rm min}}{n\rho}\right)-\Delta k_{\rm min}\to\infty$. With this, we conclude.

5 Proof of Proposition 2

We start with a useful result for proving that a test is asymptotically powerful based on the first two moments of the corresponding test statistic.

Suppose that for testing $H_{0}$ versus $H_{1}$, a statistic $T$ satisfies

Then there is a test based on $T$ that is asymptotically powerful.

For the probability of type II error, we have

We now apply Lemma 12 to the total degree test. From (12), under the null,

Recalling the definition of $R_{W}$ in (73), under (13) we have

Therefore, the total degree test is powerful when (13) holds.

6 Proof of Proposition 3

We use the union bound, Chernoff’s bound (28) and (30) to get

Choose $a=\eta p_{0}+(1-\eta)p_{1}$ with $\eta\in(0,1)$ fixed, sufficiently small that

This is possible because of how $H$ varies, which is described in Lemma 3. We then consider the test that rejects when $W_{[n]}^{*}\geq an^{(2)}$. We just chose $a$ so that its level tends to zero. Under the alternative, let $S$ denote the community. By definition, $W_{[n]}^{*}\geq W_{S}$, and since $W_{S}\sim\text{Bin}(n^{(2)},p_{1})$ and $p_{1}n^{(2)}\to\infty$, $W_{S}=p_{1}n^{(2)}+O_{P}(\sqrt{p_{1}n^{(2)}})$. Therefore, the test is powerful when $p_{1}-a\gg\sqrt{p_{1}n^{(2)}}$. Since $p_{1}-a=\eta(p_{1}-p_{0})$ and $\eta>0$ is constant, this is the same as $(p_{1}-p_{0})n^{2}\gg\sqrt{p_{1}n^{2}}$. Now, if $p_{1}/p_{0}$ is bounded away from 1, this is true because $p_{1}-p_{0}\asymp p_{1}$ and $p_{1}n^{2}\to\infty$; while if $p_{1}/p_{0}\to 1$, we use Lemma 3 and (15) to get that $(p_{1}-p_{0})^{2}n/p_{0}\geq{\rm cst}\log(N/n)$, implying that $(p_{1}-p_{0})n^{2}/\sqrt{p_{1}n^{2}}\sim(p_{1}-p_{0})n/p_{0}\to\infty$.

7 Proof of Proposition 4

The arguments are based on cumbersome, but pedestrian moment calculations.

Under the null. We first show that $V^{*}$ remains bounded under the null. Rewrite $V$ as

since $p_{0}\succ 1/N$. Therefore, by Chebyshev’s inequality, $V=O_{P}(\sqrt{N}p_{0})$. Under the null, $N^{(2)}\hat{p}_{0}=W\sim\text{Bin}(N^{(2)},p_{0})$, and because $N^{(2)}p_{0}\to\infty$, we have $\hat{p}_{0}\geq\frac{1}{2}p_{0}$ with probability tending to 1 as $N\to\infty$. We conclude that, under the null, $V^{*}=O_{P}(1)$.

so that, using the fact that $p_{0}\succ 1/N$, we get

We already argued that the first one holds, while the second and third are easily seen to be implied by the first condition and the fact that $p_{0}\succ 1/N$.

8 Proof of Proposition 5

First note that $\widehat{p}_{0}=W/N^{(2)}$ is concentrated around its mean. Indeed, we have

Since $p_{0}\gg N^{-2}$, we have $\sqrt{p_{0}}/N=o(p_{0})$. If $a\geq p_{0}$, then $p_{0}\gg N^{-2}$ impies that $\sqrt{a}/N=o(a)$. All in all, we get $\sqrt{p_{0}+a}/N=o(p_{0}+a)$ and $\widehat{p}_{0}\sim_{P}p_{0}+a$. As in the previous proofs, we can assume that $p_{1}/p_{0}\to r\in[1,\infty]$. In the three following case, we prove that

CASE 1: $p_{1}/p_{0}\rightarrow 1$. In that case, we have $a=o(p_{0})$ and $\sqrt{p_{0}}/N=o(p_{1}-p_{0})$ since

Hence, $\widehat{p}_{0}-p_{0}=o(p_{1}-p_{0})$ and we conclude that

CASE 2: $p_{1}/p_{0}\rightarrow r\in(1,\infty)$. Hence, $a=o(p_{0})$ and $p_{0}\sim_{P}\widehat{p}_{0}$. It follows that

CASE 3: $p_{1}/p_{0}\rightarrow\infty$. Since $\widehat{p}_{0}\sim_{P}p_{0}+a$, we derive

It remains to prove that $\lim\inf np_{1}>1$ when $\lim\inf nH(p_{1})/\log(N/n)>2$. Assume that $\lim\inf np_{1}\leq 1$ so that there exists a subsequence satisfying

It follows that $\lim\inf\log(1/(np_{0}))/\log(N/n)>2$ and $\lim\sup N^{2}p_{0}/n\leq 1$, which contradicts the assumption of the proposition.

9 Proof of Proposition 6

We prove the result when $p_{0}$ is known. The situation when $p_{0}$ is unknown can be dealt with in a similar way; see, for example, the proof of Proposition 5. Let $\boldsymbol{B}=\boldsymbol{W}^{2}$. We first lower bound ${\rm SDP}_{n}(\boldsymbol{W}^{2})$ from below under the alternative where $S$ is the anomalous subset of indices. We have

and, after some tedious but straightforward calculations,

By Chebyshev’s inequality, under the alternative, ${\rm SDP}_{n}(\boldsymbol{B})\geq\mu_{S}-O_{P}(\sigma_{S})$.

Under the null, we bound ${\rm SDP}_{n}(\boldsymbol{B})$ from above as Berthet and Rigollet (2012) do. Specifically, they use a result of Bach et al. (2010), which says that

Fix $\varepsilon>0$. Using Bernstein’s inequality (Lemma 2) and the union bound, we find that the following inequalities happen simultaneously with probability tending to one under the null:

Hence, choosing $z=(N-2)p_{0}^{2}+x_{00}$, we have

with high probability under the null. In order to conclude, we need to prove that $\mu_{S}-O(\sigma_{S})>\zeta$ with probability going to one.

Before proceeding, we note that (25) implies that, for some $\eta>0$,

and (1) implies that either $np_{0}\geq 1$, or $(N/n)^{-a}<np_{0}<1$, for some sequence $a\to 0$. In particular, this implies

so that $n\geq N^{1/4-a}$. It also follows that $n\sqrt{p_{0}}>\sqrt{n}(N/n)^{-a}\to\infty$.

We have $\mu_{S}-\zeta\geq(1+o(1))n^{2}p_{1}^{2}-Np_{0}^{2}-x_{0}-nx_{00}$, with

since $Np_{0}^{2}>Nn^{-2}(N/n)^{-2a}>N^{2t-2a}$ with $2t-2a\to 2t>0$. Assuming that $\eta>\varepsilon$, it remains to show that $n^{2}p_{1}^{2}\gg\sigma_{S}$ to prove that $\mu_{S}-O(\sigma_{S})>\zeta$ with probability going to one in the asymptote.

We have $\sigma_{S}^{2}\asymp Np_{0}/n+Nnp_{0}^{3}+n^{2}p_{1}^{3}$, and

10 Proof of Proposition 7

Fix $\delta>0$ arbitrarily small. Applying Berntein’s inequality (Lemma 2) and using $Np_{0}\gg\log(N)$ and $np_{1}\gg\log(n)$, we derive that

with probability going to one since we assume that $n(p_{1}-p_{0})=o(\sqrt{N\log(N)p_{0}})=o(Np_{0})$.

Let us consider a consider a subset $T\subset S^{c}$ of size $N^{1-\kappa}$ with some $\kappa>0$. As the $W_{i\cdot}$ are not independent, it is not straightforward to directly lower bound their supremum. This is why we compare it to independent variables. Let us call the $i^{*}_{T}$ the smallest $i$ in $T$ that achieves $\max_{i\in T}\sum_{j\in T^{c}}W_{i,j}$