# Modularity of the ABCD Random Graph Model
with Community Structure

Bogumił Kamiński Decision Analysis and Support Unit, SGH Warsaw School of
Economics, Warsaw, Poland; e-mail<EMAIL_ADDRESS>Bartosz
Pankratz Department of Mathematics, Ryerson University, Toronto, ON, Canada;
e-mail<EMAIL_ADDRESS>Paweł Prałat Department of Mathematics,
Ryerson University, Toronto, ON, Canada; e-mail<EMAIL_ADDRESS>François
Théberge Tutte Institute for Mathematics and Computing, Ottawa, ON, Canada;
email<EMAIL_ADDRESS>
###### Abstract

The Artificial Benchmark for Community Detection (ABCD) graph is a random
graph model with community structure and power-law distribution for both
degrees and community sizes. The model generates graphs with similar
properties as the well-known LFR one, and its main parameter $\xi$ can be
tuned to mimic its counterpart in the LFR model, the mixing parameter $\mu$.

In this paper, we investigate various theoretical asymptotic properties of the
ABCD model. In particular, we analyze the modularity function, arguably, the
most important graph property of networks in the context of community
detection. Indeed, the modularity function is often used to measure the
presence of community structure in networks. It is also used as a quality
function in many community detection algorithms, including the widely used
_Louvain_ algorithm.

##  1 Introduction

One of the most important features of real-world networks is their community
structure, as it reveals the internal organization of nodes [12]. In social
networks communities may represent groups by interest, in citation networks
they correspond to related papers, in the Web communities are formed by pages
on related topics, etc. Being able to identify communities in a network could
help us to exploit this network more effectively.

Unfortunately, there are very few datasets with ground-truth identified and
labelled. As a result, there is need for synthetic random graph models with
community structure that resemble real-world networks in order to benchmark
and tune clustering algorithms that are unsupervised by nature. The LFR
(Lancichinetti, Fortunato, Radicchi) model [29, 27] generates networks with
communities and at the same time it allows for the heterogeneity in the
distributions of both node degrees and of community sizes. It became a
standard and extensively used method for generating artificial networks.

In this paper, we analyze the Artificial Benchmark for Community Detection
(ABCD graph) [23] that was recently introduced and
implemented***https://github.com/bkamins/ABCDGraphGenerator.jl/, including a
fast implementation that uses multiple threads
(ABCDe)†††https://github.com/tolcz/ABCDeGraphGenerator.jl/. Undirected variant
of LFR and ABCD produce graphs with comparable properties but ABCD/ABCDe is
faster than LFR and can be easily tuned to allow the user to make a smooth
transition between the two extremes: pure (disjoint) communities and random
graph with no community structure. More importantly from the perspective of
this paper, it is easier to analyze theoretically. See Subsection 2.3 for a
definition of the model.

The key ingredient for many clustering algorithms is _modularity_ , which is
at the same time a global criterion to define communities, a quality function
of community detection algorithms, and a way to measure the presence of
community structure in a network. The definition of modularity for graphs was
first introduced by Newman and Girvan in [35]. We present the definition in
Subsection 2.4.

Despite some known issues with this function such as the “resolution limit”
reported in [13], many popular algorithms for partitioning nodes of large
graphs use it [11, 34, 28] and perform very well. The list includes one of the
mostly used unsupervised algorithms for detecting communities in graphs, the
_Louvain_ (hierarchical) algorithm [7]. For more details we direct the reader
to any book on complex networks, including the following recent additions [24,
26].

###  1.1 Summary of Results

In this paper, we investigate the modularity function for the ABCD model
$\mathcal{A}$. The paper is structured as follows. The ABCD model is
introduced in Subsection 2.3 and the modularity function is defined in
Subsection 2.4. Results for other random graph model in the context of the
modularity function are summarized in Section 3. Some useful general
observations are made in Section 4: concentration results that are used in
almost all of our proofs are outlined in Subsection 4.1, useful expansion
properties of random $d$-regular graphs are presented in Subsection 4.2.

We start analyzing the ABCD model by investigating some basic properties—see
Section 5. These properties will be needed to establish results for the
modularity function but they are important on their own. Lemma 5.2 shows that
the degree distribution is well concentrated around the corresponding
expectations. Corollary 5.5 shows a concentration for the number of
communities and well as the distribution of their sizes. The same generating
process is applied in LFR so the two results hold for that model as well. The
ABCD model assigns nodes to communities randomly. Clearly, there is no hope to
predict the volumes of small communities of constant size but sufficiently
large communities have their volumes as well as the number of internal edges
well concentrated around the corresponding expectations—see Lemma 5.6.

Then we move to the results for the modularity function. By design of the ABCD
model, $1-\xi$ fraction of edges should become community edges and so should
end up in some part of the ground truth partition $\mathbf{C}$. ($\xi$ is the
main parameter of the model responsible for the level of noice.) It is indeed
the case but it turns out that a negligible fraction of the background graph
join them there. As a result, the modularity function of the ground-truth
partition $\mathbf{C}$ is asymptotic to $1-\xi$, as proved in Theorem 6.1.

Analyzing the maximum modularity is much more complex. We have two types of
results. The first result (Theorem 6.2) shows that when the level of noise is
sufficiently large ($\xi$ close to one), then the maximum modularity
$q^{*}(\mathcal{A})$ is asymptotically larger than $q(\mathbf{C})$, the
modularity of the ground-truth. In this regime, the number of edges within
community graphs $G_{i}$ is relatively small so a partition of the background
graph into small connected pieces yields a better modularity function. To show
this result, we need to investigate the degree distribution of the background
graph (Lemma 6.3) which might be of independent interest.

The second set of results is concerned with graphs with low level of noise
($\xi$ close to zero). For these graphs, the situation is quite opposite. It
turns out that the ground truth partition is asymptotically the best possible,
that is, the maximum modularity $q^{*}(\mathcal{A})$ is only $o(1)$ away from
$q(\mathbf{C})$, the modularity of the ground truth partition $\mathbf{C}$;
both of them are asymptotic to $1-\xi$ (see Theorem 6.7). For some technical
reason, it is assumed that $\delta$, the minimum degree of $\mathcal{A}$, is
sufficiently large: the lower bound of $100$ easily works but it may be
improved with more detailed treatment. Having said that, it seems that one
needs a different approach to uncover the real bottleneck. On the other hand,
the above property is not true if $\delta=1$ (see Theorem 6.8): if $\delta=1$,
then $q^{*}(\mathcal{A})$ is substantially larger than $q(\mathbf{C})$,
regardless of how close to zero $\xi$ is.

Finally, let us mention that the approach used to prove Theorem 6.7 utilize a
coupling of random graph $\mathcal{P}(\textbf{w})$ on $n^{\prime}$ nodes and a
given degree sequence with a random $b$-regular graph
$\mathcal{P}_{n^{\prime\prime},b}$ on $n^{\prime\prime}$ nodes. We use this
coupling to show that good expansion properties of
$\mathcal{P}_{n^{\prime\prime},b}$ imply good expansion properties for
$\mathcal{P}(\textbf{w})$. This coupling seems powerful and might be
potentially useful for some other applications.

###  1.2 Simulations

This paper focuses on asymptotic theoretical results of the ABCD model. Having
said that, we performed a number of simulations and compared asymptotic
predictions with graphs generated by computer. These simulations show that the
behaviour of small random instances is similar to what is predicted by the
theory. This is a good news for practitioners as it shows that, despite the
fact that the generative algorithm is randomized, the model has good
stability. The code is accessible on GitHub
repository‡‡‡https://github.com/tolcz/ABCDeGraphGenerator.jl/.

###  1.3 Open Problems

Theoretical results and simulations suggest that if $\delta$, the minimum
degree of $\mathcal{A}$, satisfies $\delta\geq\delta_{0}$ for some
$\delta_{0}\geq 2$, then there exists a constant $\xi_{0}=\xi_{0}(\delta)$
(that possibly depends also on other parameters of the ABCD model
$\mathcal{A}$) such that the following holds _w.h.p._ (that is, with
probability tending to one as $n\to\infty$):

  * •

if $0<\xi<\xi_{0}$, then $q^{*}(\mathcal{A})\sim q(\mathbf{C})$, where
$\mathbf{C}$ is the ground truth partition of the set of nodes of
$\mathcal{A}$,

  * •

if $\xi>\xi_{0}$, then $q^{*}(\mathcal{A})$ is separated by a constant from
$q(\mathbf{C})$.

Our results make the first step towards this conjecture by showing upper and
lower bounds for such threshold constant $\xi_{0}$, when $\delta_{0}=100$. The
bounds for $\xi_{0}$ are not close to each other. The next step would be to
narrow the gap down or perhaps to determine the threshold value exactly,
provided that $\delta_{0}$ is sufficiently large. Another natural direction
would be to decrease the lower bound for $\delta$, that is, to decrease the
value of $\delta_{0}$. We showed that $\delta=1$ does not have the desired
property but maybe $\delta_{0}=2$? Or maybe one can always construct a better
partition than $\mathbf{C}$ when $\delta=2$, regardless how small parameter
$\xi$ is? These questions are left as open questions for future investigation.

##  2 Definitions (of ABCD Model and Modularity)

###  2.1 Asymptotic Notation

Our results are asymptotic in nature, that is, we will assume that the number
of nodes $n\to\infty$. Formally, we consider a sequence of graphs
$G_{n}=(V_{n},E_{n})$ and we are interested in events that hold _with high
probability_ (_w.h.p._), that is, events that hold with probability tending to
1 as $n\to\infty$. It would be also convenient to consider events that hold
_with extreme probability_ (_w.e.p._), that is, events that hold with
probability at least $1-\exp(-\Omega((\log n)^{2}))$. An easy but convenient
property is that if a polynomial number of events hold _w.e.p._ , then
_w.e.p._ all of them hold simultaneously.

Given two functions $f=f(n)$ and $g=g(n)$, we will write
$f(n)=\mathcal{O}(g(n))$ if there exists an absolute constant
$c\in\mathbb{R}_{+}$ such that $|f(n)|\leq c|g(n)|$ for all $n$,
$f(n)=\Omega(g(n))$ if $g(n)=\mathcal{O}(f(n))$, $f(n)=\Theta(g(n))$ if
$f(n)=\mathcal{O}(g(n))$ and $f(n)=\Omega(g(n))$, and we write $f(n)=o(g(n))$
or $f(n)\ll g(n)$ if $\lim_{n\to\infty}f(n)/g(n)=0$. In addition, we write
$f(n)\gg g(n)$ if $g(n)=o(f(n))$ and we write $f(n)\sim g(n)$ if
$f(n)=(1+o(1))g(n)$, that is, $\lim_{n\to\infty}f(n)/g(n)=1$.

###  2.2 Other Notation

We will use $\log n$ to denote a natural logarithm of $n$. For a given
$n\in\mathbb{N}:=\\{1,2,\ldots\\}$, we will use $[n]$ to denote the set
consisting of the first $n$ natural numbers, that is,
$[n]:=\\{1,2,\ldots,n\\}$. Finally, as typical in the field of random graphs,
for expressions that clearly have to be an integer, we round up or down but do
not specify which: the choice of which does not affect the argument.

###  2.3 ABCD Model

Table 1: Parameters of the ABCD model parameter | range | description
---|---|---
$n$ | $\mathbb{N}$ | number of nodes
$\gamma$ | $(2,3)$ | power-law exponent of degree distribution
$\delta$ | $\mathbb{N}$ | minimum degree at least $\delta$
$\zeta$ | $(0,\frac{1}{\gamma-1}]$ | maximum degree at most $n^{\zeta}$
$\beta$ | $(1,2)$ | power-law exponent of distribution of community sizes
$s$ | $\mathbb{N}\setminus[\delta]$ | community sizes at least $s$
$\tau$ | $(\zeta,1)$ | community sizes at most $n^{\tau}$
$\xi$ | $(0,1)$ | level of noise

The ABCD model is governed by 8 parameters summarized in Table 1. For a fixed
set of parameters, we generate the ABCD graph
$\mathcal{A}=\mathcal{A}(n,\gamma,\delta,\zeta,\beta,s,\tau,\xi)$ following
the steps outlined below. Each time we refer to graph $\mathcal{A}$ in this
paper, we implicitly (or explicitly, but it happens rather rarely) fix all of
these parameters.

####  2.3.1 Degree Distribution

Let $\gamma\in(2,3)$, $\delta\in\mathbb{N}$, and $\zeta\in(0,1)$. Degrees of
nodes of ABCD graph $\mathcal{A}$ are generated randomly following the
(truncated) _power-law distribution_ $\mathcal{P}(\gamma,\delta,\zeta)$ with
exponent $\gamma$, minimum value $\delta$, and maximum value $D=n^{\zeta}$. In
order to make sure the sum of degrees is even, if needed, we decrease by one
the degree of one node of the largest degree.

It is easy to show (see Lemma 5.1) that for any $\omega=\omega(n)$ tending to
infinity as $n\to\infty$ _w.h.p._ the maximum degree of $\mathcal{A}$ is at
most $n^{1/(\gamma-1)}\omega$ (of course, by definition, it is
deterministically at most $n^{\zeta}$). As a result, for any two values of
$\zeta_{1},\zeta_{2}\in(\frac{1}{\gamma-1},1)$ one may couple the two
corresponding ABCD graphs $\mathcal{A}$ so that _w.h.p._ they produce exactly
the same graph. Hence, for convenience but without loss of generality, we will
later on assume that $\zeta\in(0,\frac{1}{\gamma-1}]$.

####  2.3.2 Distribution of Community Sizes

Let $\beta\in(1,2)$, $s\in\mathbb{N}\setminus[\delta]$, and
$\tau\in(\zeta,1)$. Community sizes of ABCD graph $\mathcal{A}$ are generated
randomly following the (truncated) _power-law distribution_
$\mathcal{P}(\beta,s,\tau)$ with exponent $\beta$, minimum value $s$, and
maximum value $S=n^{\tau}$. Communities are generated with this distribution
as long as the sum of their sizes is less than $n$, the desired number of
nodes. Suppose that the last community has size $z$ and after adding it to the
remaining ones, the sum of their sizes will exceed $n$ by
$k\in\mathbb{N}\cup\\{0\\}$. If $k=0$, then there is nothing else to do. If
$z-k\geq s$, then the size of the last community is reduced to $z-k$ so that
the total number of nodes is exactly $n$. Otherwise, we select $z-k<s$ old
communities at random, increase their sizes by one, and remove the last
community so that the desired property holds.

The assumption that $\tau>\zeta$ is introduced to make sure large degree nodes
have large enough communities to be assigned to. Similarly, the assumption
that $s\geq\delta+1$ is required to guarantee that small communities are not
too small and so that they can accommodate small degree nodes.

####  2.3.3 Assigning Nodes into Communities

At this point, the degree distribution $(w_{1}\geq w_{2}\geq\ldots\geq w_{n})$
and the distribution of community sizes $(c_{1}\geq c_{2}\geq\ldots\geq
c_{\ell})$ are already fixed. The final ABCD graph $\mathcal{A}$ will be
formed as the union of $\ell+1$ independent graphs: $\ell$ community graphs
$G_{i}=(C_{i},E_{i})$, $i\in[\ell]$, and a single background graph
$G_{0}=(V,E_{0})$, where $V=\bigcup_{i\in[\ell]}C_{i}$. Roughly $\xi w_{i}$
edges incident to node $i$ will, by definition, belong to its own community
but a few additional edges from the background graph might end up in that
community. In order to create enough room for these edges, node of degree
$w_{i}$ will be allowed to be assigned to a community of size $c_{j}$ if the
following inequality is satisfied:

$\lceil(1-\xi\phi)w_{i}\rceil\leq c_{j}-1,\hskip 28.45274pt\text{ where
}\phi=1-\sum_{k\in[\ell]}(c_{k}/n)^{2}.$

Note that this condition is equivalent to the following one:

$w_{i}\leq\frac{c_{j}-1}{1-\xi\phi}.$ (1)

An assignment of nodes into communities will be called _admissible_ if the
above inequality is satisfied for all nodes. We will show in Subsection 5.3
that there are many admissible assignments. In particular, there are linearly
many nodes of degree $\delta$ but, fortunately, _w.h.p._ communities of size
more than $n^{\zeta}$ (more than the maximum degree) have space for almost all
nodes. We select one admissible assignment uniformly at random. Sampling
uniformly one of such assignments turns out to be relatively easy from both
theoretical and practical points of view. We will discuss it in detail in
Subsection 5.3.

####  2.3.4 Distribution of Weights

Parameter $\xi\in(0,1)$ reflects the amount of noise in the network. It
controls the fraction of edges that are between communities. Indeed,
asymptotically (but not exactly) $1-\xi$ fraction of edges are going to end up
within one of the communities. Each node will have its degree $w_{i}$ split
into two parts: _community degree_ $y_{i}$ and _background degree_ $z_{i}$
($w_{i}=y_{i}+z_{i}$). Our goal is to get $y_{i}\approx(1-\xi)w_{i}$ and
$z_{i}\approx\xi w_{i}$. However, both $y_{i}$ and $z_{i}$ have to be non-
negative integers and for each community $C\subseteq V$, $\sum_{i\in C}y_{i}$
has to be even. Note that since $\sum_{i\in V}w_{i}$ is even, it will imply
that

$\sum_{i\in V}z_{i}=\sum_{i\in V}(w_{i}-y_{i})=\sum_{i\in
V}w_{i}-\sum_{C}\sum_{i\in C}y_{i}$

is even too.

For each community $C\subseteq V$ we identify the _leader_ , a node of the
largest degree $w_{i}$ associated with community $C$. (If many nodes in $C$
have the largest degree, then we arbitrarily select one of them to be the
leader.) For non-leaders we split the weights as follows:

$y_{i}=\Big{\lfloor}(1-\xi)w_{i}\Big{\rceil}\hskip 28.45274pt\text{ and
}\hskip 28.45274ptz_{i}=w_{i}-y_{i},$

where for a given integer $a\in\mathbb{Z}$ and real number $b\in[0,1)$ the
random variable $\lfloor a+b\rceil$ is defined as

$\lfloor a+b\rceil=\begin{cases}a&\text{ with probability }1-b\\\ a+1&\text{
with probability }b.\end{cases}$ (2)

(Note that $\mathbb{E}[\lfloor a+b\rceil]=a(1-b)+(a+1)b=a+b$.) For the leader
of community $C$ we round $(1-\xi)w_{i}$ up or down so that the sum of weights
in each cluster is even. If $(1-\xi)w_{i}\in\mathbb{N}$ and the sum of weights
$y_{i}$ in $C$ is odd, then we randomly make a decision whether subtract or
add one to make the sum to be even.

####  2.3.5 Creating Graphs

As already mentioned, the final ABCD graph $\mathcal{A}=(V,E)$ will be formed
as the union of $\ell+1$ independent graphs: $\ell$ community graphs
$G_{i}=(C_{i},E_{i})$, $i\in[\ell]$, and a single background graph
$G_{0}=(V,E_{0})$, where $V=\bigcup_{i\in[\ell]}C_{i}$, that is,
$E=\bigcup_{i\in[\ell]\cup\\{0\\}}E_{i}$. Each of these $\ell+1$ graphs will
be created independently. The partition
$\mathbf{C}=\\{C_{1},C_{2},\ldots,C_{\ell}\\}$ will be called a _ground-truth_
partition.

Suppose then that our goal is to create a graph on $n$ nodes with a given
degree distribution $\textbf{w}:=(w_{1},w_{2},\ldots,w_{n})$, where w is any
vector of non-negative integers such that $w:=\sum_{i\in[n]}w_{i}$ is even. We
define a random multi-graph $\mathcal{P}(\textbf{w})$ with a given degree
sequence known as the configuration model (sometimes called the pairing
model), which was first introduced by Bollobás [8]. (See [6, 38, 39] for
related models and results.) We start with $w$ _points_ that are partitioned
into $n$ _buckets_ labelled with labels $v_{1},v_{2},\ldots,v_{n}$; bucket
$v_{i}$ consists of $w_{i}$ points. It is easy to see that there are
$\frac{w!}{(w/2)!2^{w}}$ pairings of points. We select one of such pairings
uniformly at random, and construct a multi-graph $\mathcal{P}(\textbf{w})$,
with loops and parallel edges allowed, as follows: nodes are the buckets
$v_{1},v_{2},\ldots,v_{n}$, and a pair of points $xy$ corresponds to an edge
$v_{i}v_{j}$ in $\mathcal{P}(\textbf{w})$ if $x$ and $y$ are contained in the
buckets $v_{i}$ and $v_{j}$, respectively.

####  2.3.6 Simulation Corner

Note that the ABCD model $\mathcal{A}$ allows loops and multiple edges.
Indeed, they can occur both in any of the generated graphs $G_{i}$
($i\in[\ell]\cup\\{0\\}$) or after taking a union of their edge sets. In
general, however, there will not be very many of them. To keep the theoretical
model simple, in this paper we allow $\mathcal{A}$ be a multi-graph but,
alternatively, one may condition on $\mathcal{A}$ to be a simple graph. In
practice, the algorithm performs some kind of edges “switching” that is known
to generate a random graph that is very close to the uniform distribution
[18]. We will use simple graphs for our experiments to show that, indeed, the
difference is not detectable. Moreover, to get closed formulas in some
theoretical results proved in this paper we use the continuous variant of the
power law distribution. For example, if
$X\in\mathcal{P}(\gamma,\delta,\zeta)$, then for any
$k\in\\{\delta,\delta+1,\ldots,D\\}$ we assume that

$q_{k}=\Pr(X=k)=\frac{\int_{k}^{k+1}x^{-\gamma}dx}{\int_{\delta}^{D+1}x^{-\gamma}dx}.$

Alternatively, one may use the discrete counterpart, namely, assume that

$r_{k}=\Pr(X=k)=\frac{k^{-\gamma}}{\sum_{x=\delta}^{D}x^{-\gamma}}.$ (3)

All results proved in this paper hold for both variants. We state them for
continuous one but one may replace $q_{k}$ with $r_{k}$ to get the discrete
counterparts. Since the default implementation of the ABCD model uses the
discrete distribution, we use it for our simulations. For more details we
direct the reader to the original paper on the ABCD model [23].

###  2.4 Modularity Function

The modularity function favours partitions of the set of nodes of a graph $G$
in which a large proportion of the edges fall entirely within the parts but
benchmarks it against the expected number of edges one would see in those
parts in the corresponding Chung-Lu random graph model [10] which generates
graphs with the expected degree sequence following exactly the degree sequence
in $G$.

Formally, for a graph $G=(V,E)$ and a given partition
$\mathbf{A}=\\{A_{1},A_{2},\ldots,A_{\ell}\\}$ of $V$, the _modularity
function_ is defined as follows:

$\displaystyle q(\mathbf{A})$ $\displaystyle=$
$\displaystyle\sum_{A_{i}\in\mathbf{A}}\frac{e(A_{i})}{|E|}-\sum_{A_{i}\in\mathbf{A}}\left(\frac{\textrm{vol}(A_{i})}{\textrm{vol}(V)}\right)^{2},$
(4)

where for any $A\subseteq V$, $e(A)=|\\{uv\in E:u,v\in A\\}|$ is the number of
edges in the subgraph of $G$ _induced by_ set $A$, and
$\textrm{vol}(A)=\sum_{v\in A}\deg(v)$ is the _volume_ of set $A$. In
particular, $\textrm{vol}(V)=2|E|$. The first term in (4),
$\sum_{A_{i}\in\mathbf{A}}e(A_{i})/|E|$, is called the _edge contribution_ and
it computes the fraction of edges that fall within one of the parts. The
second one,
$\sum_{A_{i}\in\mathbf{A}}(\textrm{vol}(A_{i})/\textrm{vol}(V))^{2}$, is
called the _degree tax_ and it computes the expected fraction of edges that do
the same in the corresponding random graph (the null model). The modularity
measures the deviation between the two.

It is easy to see that for any partition $\mathbf{A}$, $q(\mathbf{A})\leq 1$.
On the other hand, it can be shown that $q(\mathbf{A})\geq-1/2$. Also, if
$\mathbf{A}=\\{V\\}$, then $q(\mathbf{A})=0$, and if
$\mathbf{A}=\\{\\{v_{1}\\},\\{v_{2}\\},\ldots,\\{v_{n}\\}\\}$, then
$q(\mathbf{A})=-\sum(\deg(v)/\textrm{vol}(V))^{2}<0$. The maximum _modularity_
$q^{*}(G)$ is defined as the maximum of $q(\mathbf{A})$ over all possible
partitions $\mathbf{A}$ of $V$; that is,
$q^{*}(G)=\max_{\mathbf{A}}q(\mathbf{A}).$ In order to maximize
$q(\mathbf{A})$ one wants to find a partition with large edge contribution
subject to small degree tax. If $q^{*}(G)$ approaches 1 (which is the trivial
upper bound), we observe a strong community structure; conversely, if
$q^{*}(G)$ is close to zero (which is the trivial lower bound), there is no
community structure. The definition in (4) can be generalized to weighted
edges by replacing edge counts with sums of edge weights. It can also be
generalized to hypergraphs [21, 22].

##  3 Related Results for Random Graphs

Analyzing the maximum modularity $q^{*}(G)$ for sparse random graphs is a
challenging task. The most attention was paid to random $d$-regular graphs
$\mathcal{G}_{n,d}$ but even for this family of graphs we only know upper and
lower bounds for $q^{*}(\mathcal{G}_{n,d})$ that are quite apart from each
other. For example, for random $3$-regular graph $\mathcal{G}_{n,3}$ we only
know that _w.h.p._

$0.667026\leq q^{*}(\mathcal{G}_{n,3})\leq 0.789998.$

These bounds were recently proved in [30] but the main goal of that paper was
to confirm the conjecture from [32] that _w.h.p._
$q^{*}(\mathcal{G}_{n,3})\geq 2/3+\varepsilon$ for some $\varepsilon>0$. We
refer the reader to [32, 37] for numerical bounds on
$q^{*}(\mathcal{G}_{n,d})$ for other values of $d\geq 3$ and for some explicit
but weaker bounds. It is also known that _w.h.p._
$q^{*}(\mathcal{G}_{n,2})\sim 1$ [32].

The binomial random graphs $\mathcal{G}(n,p)$ were studied in [33] where it
was shown that _w.h.p._ $q^{*}(\mathcal{G}(n,p))\sim 1$, provided that $pn\leq
1$ whereas _w.h.p._ $q^{*}(\mathcal{G}(n,p))=\Theta(1/\sqrt{pn})$, provided
that $pn\geq 1$ and $p<1-\varepsilon$ for some $\varepsilon>0$. The modularity
of the well-known Preferential Attachment (PA) model [5] and the Spatial
Preferential Attachment (SPA) model [1] was studied in [37]. Finally, the
modularity of a model of random geometric graphs on the hyperbolic plane [25],
known as the KPKBV model after its inventors, was recently studied in [9].

##  4 Preliminaries

###  4.1 Chernoff Bounds and Their Generalization

Let us first state a specific instance of Chernoff’s bound that we will find
often useful. Let $X\in\textrm{Bin}(n,p)$ be a random variable with the
binomial distribution with parameters $n$ and $p$. Then, a consequence of
_Chernoff’s bound_ (see e.g. [19, Corollary 2.3]) is that

$\mathbb{P}(|X-\mathbb{E}[X]|\geq\varepsilon\ \mathbb{E}[X])\leq
2\exp\left(-\frac{\varepsilon^{2}\ \mathbb{E}[X]}{3}\right)$ (5)

for $0<\varepsilon<3/2$. However, at some point we will need need a stochastic
upped bound for $X$ when $\mathbb{E}[X]$ is small. In such situations the
following bound can be applied instead of (5) (see e.g. [19, Theorem 2.1]):

$\mathbb{P}(X\geq\mathbb{E}[X]+u)\leq\exp\left(-\frac{u^{2}}{2(\mathbb{E}[X]+u/3)}\right).$
(6)

Let us mention that the above bounds hold for the general case in which
$X=\sum_{i=1}^{n}X_{i}$ and $X_{i}\in\textrm{Bernoulli}(p_{i})$ with
(possibly) different $p_{i}$ (e.g. see [19, Theorem 2.8]). Moreover, they also
hold for a hypergeometric distribution with parameters $n$, $z$, and $t$,
where $\max(z,t)\leq n$. Let $T$ be a subset of $[n]$ of size $t$ selected
uniformly at random. Then a random variable with a hypergeometric distribution
is defined as follows: $X=|T\cap[z]|$. Then the above inequalities hold with
$\mathbb{E}[X]=zt/n$ (again, e.g. see [19, Theorem 2.10]).

We will also need the following result which can be viewed as a generalization
of Chernoff bounds. In particular, the two inequalities above ((5 and (6)) are
special cases when $c=1$.

######  Lemma 4.1.

Let $(c_{1},c_{2},\ldots,c_{r})$ be a sequence of natural numbers with
$c=\max_{i}c_{i}$. Let $S_{j}=\sum_{i=1}^{j}c_{i}Z_{i}$, where $Z_{i},i\in[r]$
are independent Bernoulli($p$) random variables. Let
$\mu_{j}=\mathbb{E}[S_{j}]=p\sum_{i=1}^{j}c_{i}$, and let
$\mu=\mu_{r}=\mathbb{E}[S_{r}]$. Then for $u\geq 0$ we have that

$\displaystyle\mathbb{P}\left(\max_{1\leq j\leq r}(S_{j}-\mu_{j})\geq
u\right)$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{u^{2}}{2c(\mu+u/3)}\right)\mbox{ and }$
$\displaystyle\mathbb{P}\left(\max_{1\leq j\leq r}(\mu_{j}-S_{j})\geq
u\right)$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{u^{2}}{2c\mu}\right).$

In particular, for $\varepsilon\leq 3/2$ we have that

$\mathbb{P}\left(\max_{1\leq j\leq
r}|S_{j}-\mu_{j}|\geq\varepsilon\mu\right)\leq
2\exp\left(-\frac{\varepsilon^{2}\mu}{3c}\right).$

To prove this lemma, one can easily adjust the proof of the classic Chernoff
bound. Alternatively, the same bounds come from [31]. In that paper, the
counterpart of Lemma 4.1 is stated for $S_{r}-\mu$ (see Theorem 2.3); however,
the author comments that $S_{r}-\mu$ can be replaced with $\max_{1\leq j\leq
r}(S_{j}-\mu_{j})$ (which is a slightly stronger version than we need here) as
follows. A standard martingale bound shows that eg. for any $h>0$:

$\mathbb{P}\left(\max_{1\leq j\leq r}(S_{j}-\mu_{j})\geq u\right)\leq
e^{-hu}\mathbb{E}\left[e^{h(S_{r}-\mu)}\right].$

Then plugging this into the appropriate place in the proof of Theorem 2.3
yields the desired bounds.

###  4.2 Expansion Properties of Random $d$-regular graphs

Let $\mathcal{G}_{n,d}$ be the probability space of random $d$-regular simple
graphs with uniform probability distribution ($d\geq 2$ is fixed and $n$ is
even if $d$ is odd). It is an easy fact that the probability of a random
pairing $\mathcal{P}_{n,d}:=\mathcal{P}(\textbf{w})$ with
$\textbf{w}:=(d,d,\ldots,d)$ corresponding to a given simple $d$-regular graph
$G$ is independent of the graph. As a result, the restriction of the
probability space $\mathcal{P}_{n,d}$ to simple graphs is precisely
$\mathcal{G}_{n,d}$. Moreover, it is well known that a random pairing
generates a simple graph with probability asymptotic to $e^{(1-d^{2})/4}$
depending on $d$, so that any event holding _w.h.p._ over the probability
space of random pairings also holds _w.h.p._ over the corresponding space
$\mathcal{G}_{n,d}$. For this reason, asymptotic results over random pairings
can be immediately transferred to $\mathcal{G}_{n,d}$. For more information on
this model, see [39].

We will use the well-known expansion properties of random $d$-regular graphs
that follow from their eigenvalues. These expansion properties are known to
hold _w.h.p._ for $\mathcal{G}_{n,d}$ but, fortunately, they actually hold
_w.h.p._ for $\mathcal{P}_{n,d}$ (and so, by the argument mentioned above,
they immediately hold _w.h.p._ for $\mathcal{G}_{n,d}$ which is what is
typically used). In one of our proofs (see the proof of Theorem 6.7), we will
couple the ABCD model $\mathcal{A}$ with a random pairing $\mathcal{P}_{n,d}$.
This coupling will allow us to deduce some useful expansion properties of
$\mathcal{A}$ from the corresponding properties of $\mathcal{P}_{n,d}$.

The adjacency matrix $A=A(G)$ of a given a $d$-regular (multi)graph $G$ with
$n$ nodes, is an $n\times n$ real and symmetric matrix. Thus, the matrix $A$
has $n$ real eigenvalues which we denote by
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$. It is known that
certain properties of a $d$-regular graph are reflected in its spectrum but,
since we focus on expansion properties, we are particularly interested in the
following quantity: $\lambda=\lambda(G)=\max(|\lambda_{2}|,|\lambda_{n}|)$. In
words, $\lambda$ is the largest absolute value of an eigenvalue other than
$\lambda_{1}=d$. For more details, see the general survey [17] about
expanders, or [4, Chapter 9].

The value of $\lambda$ for random $d$-regular graphs has been studied
extensively. A major result due to Friedman [14] is the following:

######  Lemma 4.2 ([14]).

For every fixed $\varepsilon>0$ and for $G\in\mathcal{P}_{n,d}$ (and so also
for $G\in\mathcal{G}_{n,d}$), _w.h.p._

$\lambda(G)\leq 2\sqrt{d-1}+\varepsilon.$

The number of edges $|E(S,T)|$ between sets $S$ and $T$ is expected to be
close to the expected number of edges between $S$ and $T$ in a random graph of
edge density $d/n$, namely, $d|S||T|/n$. A small $\lambda$ (or large spectral
gap) implies that this deviation is small. The following useful bound is
essentially proved in [2] (see also [4]):

######  Lemma 4.3 (Expander Mixing Lemma).

Let $G=(V,E)$ be a $d$-regular (multi)graph with $n$ nodes and set
$\lambda=\lambda(G)$. Then for all $S,T\subseteq V$

$\left||E(S,T)|-\frac{d|S||T|}{n}\right|\leq\lambda\sqrt{|S||T|}\,.$

(Note that $S\cap T$ does not have to be empty; in general, $|E(S,T)|$ is
defined to be the number of edges between $S\setminus T$ to $T$ plus twice the
number of edges that contain only nodes of $S\cap T$.)

The Expander Mixing Lemma is very useful but for our purpose it is better to
apply a slightly stronger lower estimate for $|E(S,V\setminus S)|$, namely,

$|E(S,V\setminus S)|\geq\frac{(d-\lambda)|S||V\setminus S|}{n}$ (7)

for all $S\subseteq V$. This is proved in [3], see also [4]. Combining this
inequality with a simple averaging argument gives immediately the following
useful bound for the maximum modularity that was observed in [37].

######  Lemma 4.4 ([37]).

Let $G=(V,E)$ be a $d$-regular (multi)graph with $n$ nodes and set
$\lambda=\lambda(G)$. Then,

$q^{*}(G)\leq\frac{\lambda}{d}\,.$

##  5 Some Properties of ABCD

###  5.1 Degree Distribution

Let $\gamma\in(2,3)$, $\delta\in\mathbb{N}$, and $\zeta\in(0,1)$. We will show
soon that we may assume that $\zeta\leq\frac{1}{\gamma-1}$ but for now we
allow $\zeta$ to be any value from $(0,1)$. Recall that the degrees of nodes
of the ABCD model are generated randomly following the (truncated) _power-law
distribution_ $\mathcal{P}(\gamma,\delta,\zeta)$ with exponent $\gamma$,
minimum value $\delta$, and maximum value $D=n^{\zeta}$. More precisely, if
$X\in\mathcal{P}(\gamma,\delta,\zeta)$, then for any
$k\in\\{\delta,\delta+1,\ldots,D\\}$,

$\displaystyle q_{k}$ $\displaystyle=$
$\displaystyle\Pr(X=k)=\frac{\int_{k}^{k+1}x^{-\gamma}dx}{\int_{\delta}^{D+1}x^{-\gamma}dx}=\frac{k^{1-\gamma}-(k+1)^{1-\gamma}}{\delta^{1-\gamma}-(D+1)^{1-\gamma}}$
$\displaystyle=$
$\displaystyle(1+\mathcal{O}(n^{-\zeta(\gamma-1)}))\left(k^{-(\gamma-1)}-(k+1)^{-(\gamma-1)}\right)\delta^{\gamma-1}$
$\displaystyle=$ $\displaystyle(1+\mathcal{O}(n^{-\zeta(\gamma-1)}))\
k^{-(\gamma-1)}\left(1-(1+1/k)^{-(\gamma-1)}\right)\delta^{\gamma-1}$
$\displaystyle=$ $\displaystyle(1+\mathcal{O}(n^{-\zeta(\gamma-1)}))\
k^{-(\gamma-1)}\left(1-(1-(\gamma-1)/k+\mathcal{O}(1/k^{2}))\right)\delta^{\gamma-1}$
$\displaystyle=$
$\displaystyle(1+\mathcal{O}(n^{-\zeta(\gamma-1)})+\mathcal{O}(k^{-1}))\
k^{-(\gamma-1)}\frac{\gamma-1}{k}\delta^{\gamma-1}$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}(n^{-\zeta(\gamma-1)})+\mathcal{O}(k^{-1}))\
k^{-\gamma}(\gamma-1)\delta^{\gamma-1}.$ (9)

As promised earlier, we start with a proof of an upper bound for the maximum
degree, which justifies our future assumption that $\zeta\in(0,1/(\gamma-1)]$.

######  Lemma 5.1.

Let $\gamma\in(2,3)$, $\delta\in\mathbb{N}$, and $\zeta\in(0,1)$. Let
$\omega=\omega(n)$ be any function tending to infinity as $n\to\infty$. Then,
_w.h.p._ the maximum degree of $\mathcal{A}$ is at most
$\min(n^{\zeta},n^{1/(\gamma-1)}\omega)$.

###### Proof.

Trivially, by definition, the maximum degree is at most $D=n^{\zeta}$. Hence,
the desired property holds (deterministically) if $\zeta\leq 1/(\gamma-1)$.
Let us then assume that $\zeta>1/(\gamma-1)$. Our goal is to show that
_w.h.p._ the maximum degree of $\mathcal{A}$ is at most
$K:=n^{1/(\gamma-1)}\omega$. Note that the expected number of nodes with
degree at least $K$ is equal to

$n\sum_{k=K}^{D}q_{k}=n\
\frac{\int_{K}^{D+1}x^{-\gamma}dx}{\int_{\delta}^{D+1}x^{-\gamma}dx}=n\
\frac{K^{1-\gamma}-(D+1)^{1-\gamma}}{\delta^{1-\gamma}-(D+1)^{1-\gamma}}=\mathcal{O}(n\,K^{-(\gamma-1)})=\mathcal{O}(\omega^{-(\gamma-1)})=o(1).$

Hence, by the first moment method, _w.h.p._ there is no node with degree at
least $K$ and the proof of the lemma is finished. ∎

Now, we are ready to investigate the degree distribution.

######  Lemma 5.2.

Let $\gamma\in(2,3)$, $\delta\in\mathbb{N}$, and
$\zeta\in(0,\frac{1}{\gamma-1}]$. For $k\in\mathbb{N}$, let $Y_{k}$ be the
random variable counting the number of nodes in $\mathcal{A}$ that are of
degree $k$. For $k\in\mathbb{N}$ and $\eta=\eta(n)$, let $Y_{k}^{\eta}$ be the
random variable counting the number of nodes in $\mathcal{A}$ that are of
degree at least $k$ but at most $(1+\eta)k$.

The following properties hold _w.e.p._ :

  * (a)

If $\zeta\in(0,\frac{1}{\gamma})$, then for any $k\in\mathbb{N}$ such that
$\delta\leq k\leq n^{\zeta}$ we have

$\displaystyle Y_{k}$ $\displaystyle=$ $\displaystyle(1+\mathcal{O}((\log
n)^{-1}))\ nq_{k}$ (10) $\displaystyle=$ $\displaystyle(1+\mathcal{O}((\log
n)^{-1}))\ n\left(k^{-(\gamma-1)}-(k+1)^{-(\gamma-1)}\right)\delta^{\gamma-1}$
$\displaystyle=$ $\displaystyle(1+\mathcal{O}(k^{-1})+\mathcal{O}((\log
n)^{-1}))\ nk^{-\gamma}(\gamma-1)\delta^{\gamma-1}.$

  * (b)

If $\zeta\in[\frac{1}{\gamma},\frac{1}{\gamma-1})$, then for any
$k\in\mathbb{N}$ such that $\delta\leq k\leq n^{1/\gamma}(\log
n)^{-4/\gamma}\ll n^{\zeta}$ random variable $Y_{k}$ satisfies (10), and for
any $k\in\mathbb{N}$ such that $n^{1/\gamma}(\log n)^{-4/\gamma}\leq k\leq
n^{\zeta}/(1+\eta)$ we have

$\displaystyle Y_{k}^{\eta}$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-1}))\ n\eta kq_{k}$ (11)
$\displaystyle=$ $\displaystyle(1+\mathcal{O}((\log n)^{-1}))\
(\gamma-1)\delta^{\gamma-1}(\log n)^{4},$

where

$\eta=\eta(k)=n^{-1}(\log n)^{4}k^{\gamma-1}=\mathcal{O}((\log n)^{-1})=o(1).$

  * (c)

If $\zeta=\frac{1}{\gamma-1}$, then for any $k\in\mathbb{N}$ such that
$\delta\leq k\leq n^{1/\gamma}(\log n)^{-4/\gamma}\ll n^{\zeta}$ random
variable $Y_{k}$ satisfies (10), and for any $k\in\mathbb{N}$ such that
$n^{1/\gamma}(\log n)^{-4/\gamma}\leq k\leq n^{\zeta}(\log n)^{-5/(\gamma-1)}$
random variable $Y_{k}^{\eta}$ satisfies (11). The number of nodes of degree
at least $n^{\zeta}(\log n)^{-5/(\gamma-1)}$ is equal to $\Theta((\log
n)^{5})$.

Before we move to the proof of this lemma, let us mention the following
straightforward corollary. Recall that for a given set of nodes $A\subseteq
V$, the _volume_ of $A$ is defined as follows:

$\textrm{vol}(A)=\sum_{v\in A}\deg(v).$

In particular, $\textrm{vol}(V)=2|E|$.

######  Corollary 5.3.

The volume of all nodes in $\mathcal{A}$ is _w.e.p._ equal to

$\textrm{vol}(V)=\sum_{k=\delta}^{D}kY_{k}=(1+\mathcal{O}((\log n)^{-1}))\
dn,\hskip 28.45274pt\text{ where }d:=\sum_{k=\delta}^{D}\ kq_{k}.$

Unfortunately, there is no closed formula for a constant $d$ but one can
easily approximate it numerically and obtain some theoretical bounds. For
example, note that

$\displaystyle d$ $\displaystyle=$ $\displaystyle\sum_{k=\delta}^{D}\
k\frac{\int_{k}^{k+1}x^{-\gamma}dx}{\int_{\delta}^{D+1}x^{-\gamma}dx}\leq\sum_{k=\delta}^{D}\
\frac{\int_{k}^{k+1}x^{1-\gamma}dx}{\int_{\delta}^{D+1}x^{-\gamma}dx}=\frac{\int_{\delta}^{D+1}x^{1-\gamma}dx}{\int_{\delta}^{D+1}x^{-\gamma}dx}=\frac{(\delta^{2-\gamma}-(D+1)^{2-\gamma})/(\gamma-2)}{(\delta^{1-\gamma}-(D+1)^{1-\gamma})/(\gamma-1)}$
$\displaystyle=$ $\displaystyle(1+\mathcal{O}(n^{-\zeta(\gamma-2)}))\ \delta\
\frac{\gamma-1}{\gamma-2}.$

On the other hand,

$\displaystyle d$ $\displaystyle=$ $\displaystyle\sum_{k=\delta}^{D}\
k\frac{\int_{k}^{k+1}x^{-\gamma}dx}{\int_{\delta}^{D+1}x^{-\gamma}dx}\geq\sum_{k=\delta}^{D}\
\frac{k}{k+1}\cdot\frac{\int_{k}^{k+1}x^{1-\gamma}dx}{\int_{\delta}^{D+1}x^{-\gamma}dx}\geq\frac{\delta}{\delta+1}\cdot\frac{\int_{\delta}^{D+1}x^{1-\gamma}dx}{\int_{\delta}^{D+1}x^{-\gamma}dx}$
$\displaystyle=$ $\displaystyle(1+\mathcal{O}(n^{-\zeta(\gamma-2)}))\
\frac{\delta^{2}}{\delta+1}\cdot\frac{\gamma-1}{\gamma-2}.$

###### Proof of Lemma 5.2.

For now, suppose that the degree sequence is simply a sequence of $n$
independent random variables, each of them following power-law distribution
$\mathcal{P}(\gamma,\delta,\zeta)$. In the end, the degree of a node of the
largest degree might possibly be decreased by one to make sure the sum of
degrees is even. Clearly, this small adjustment will not affect out asymptotic
bounds.

We will call a node _light_ if its degree is at most $K:=n^{1/\gamma}(\log
n)^{-4/\gamma}$; otherwise, it will be called _heavy_. Note that if
$\zeta<1/\gamma$, then trivially all nodes are light. On the other hand, if
$\zeta\geq 1/\gamma$, then (as will be shown soon) _w.h.p._ the maximum degree
is equal to $(1+o(1))n^{\zeta}$ and so we will have a mixture of light and
heavy nodes. We need to make a distinction because for a given value of $k$,
$\delta\leq k\leq K$, there are plenty of light nodes with their degrees are
equal to $k$, that is, we will show that _w.e.p._ $Y_{k}>0$. Unfortunately,
for a given value of $k$, $K<k\leq n^{\zeta}$, it might happen (in fact, it is
quite often the case) that there will be no heavy node that has its degree
equal to $k$, that is, $Y_{k}=0$. In order to solve this problem, we will need
to group heavy nodes together and consider them in batches, that is, consider
$Y_{k}^{\eta}$ instead of $Y_{k}$.

We start with light nodes. Let us fix $k\in\mathbb{N}$ such that $\delta\leq
k\leq K$. Using (9), we get that

$\mathbb{E}[Y_{k}]=nq_{k}=\Theta(nk^{-\gamma})=\Omega(nK^{-\gamma})=\Omega((\log
n)^{4}).$

After applying Chernoff’s bound (5) with $\varepsilon=(\log n)^{-1}$ we get
that _w.e.p._

$Y_{k}=(1+\mathcal{O}((\log n)^{-1}))\mathbb{E}[Y_{k}]=(1+\mathcal{O}((\log
n)^{-1}))nq_{k}.$

The other two equalities in (10) follow immediately from (5.1) and (9). This
finishes part (a) and the first half of part (b).

We move now to heavy nodes. Assume that $\zeta\geq 1/\gamma$ and let us fix
$k\in\mathbb{N}$ such that $K\leq k\leq n^{\zeta}/(1+\eta)$. If
$\zeta=1/(\gamma-1)$ (part (c)), then we additionally assume that $k\leq
n^{\zeta}(\log n)^{-5/(\gamma-1)}$. (We will independently deal with nodes of
degrees that are very close to the maximum degree.) Recall that

$\eta=\eta(k)=n^{-1}(\log n)^{4}k^{\gamma-1}.$

Recall also that random variable $Y_{k}^{\eta}$ counts a _batch_ of nodes with
degrees at least $k$ but at most $(1+\eta)k$. Note that $\eta(k)$ is an
increasing function of $k$. Moreover, $\eta(K)=1/K$ so only a few values are
considered for $k=K$ (note that $\eta(K)K=1$). On the other extreme,
$\eta(n^{\zeta})=n^{-1+\zeta(\gamma-1)}(\log n)^{4}$ which is
$\mathcal{O}((\log n)^{-1})=o(1)$, provided that $\zeta<1/(\gamma-1)$. If
$\zeta=1/(\gamma-1)$ (part (c)), then additional upper bound for $k$ also
guarantees that at the extreme case $\eta(n^{\zeta}(\log
n)^{-5/(\gamma-1)})=(\log n)^{-1}=o(1)$. In any case, if
$\eta=\mathcal{O}((\log n)^{-1})$, then all nodes in the batch have degrees
equal to $(1+\mathcal{O}(\eta))k=(1+\mathcal{O}((\log n)^{-1}))k$. Using (9)
as before, we get that

$\mathbb{E}[Y_{k}^{\eta}]=n\sum_{i=k}^{(1+\eta)k}q_{i}=\Theta\left(n(\eta
k)k^{-\gamma}\right)=\Theta((\log n)^{4}).$

After applying Chernoff’s bound (5) with $\varepsilon=(\log n)^{-1}$ we get
that _w.e.p._

$Y_{k}^{\eta}=(1+O((\log
n)^{-1}))\mathbb{E}[Y_{k}^{\eta}]=(1+\mathcal{O}((\log n)^{-1}))\ n\eta
kq_{k}.$

The second equality in (11) follows immediately from (9). This finishes the
second half of part (b).

To finish part (c), it remains to concentrate on the case $\zeta=1/(\gamma-1)$
and deal with nodes of degrees that are very close to the maximum degree.
Since the expected number of nodes of degree at least $n^{\zeta}(\log
n)^{-5/(\gamma-1)}$ is of order

$n\left(n^{\zeta}(\log n)^{-5/(\gamma-1)}\right)^{1-\gamma}=(\log n)^{5},$

we may apply Chernoff’s bound (5) with $\varepsilon=(\log n)^{-1}$ for the
last time to get the desired concentration. The proof of the lemma is
finished. ∎

#### Simulation Corner

In order to see whether asymptotic results can be used to predict the
behaviour for relatively small values of $n$, we generated the degree
distributions for two ABCD graphs $\mathcal{A}$ on $n=1{,}000$ and,
respectively, $n=1{,}000{,}000$ nodes. In both cases, we used parameters
$\gamma=2.5$, $\delta=5$, and $\zeta=1/2<2/3=1/(\gamma-1)$ (that is,
$D=\sqrt{n}$). On Figure 1 we plot the complement of the cumulative degree
distribution (that is, the fraction of nodes of degree at least $K$) and
compare it with asymptotic, theoretical predictions, namely, function

$\sum_{k=K}^{D}q_{k}=\frac{\int_{K}^{D+1}x^{-\gamma}dx}{\int_{\delta}^{D+1}x^{-\gamma}dx}=\frac{K^{1-\gamma}-(D+1)^{1-\gamma}}{\delta^{1-\gamma}-(D+1)^{1-\gamma}}.$

We observe almost perfect agreement, especially for a larger graph. As
mentioned earlier, the theoretical distribution uses the continuous model
whereas when generating ABCD we used the discrete distribution. As a
consequence, we see a slight deviation between the curves indicating that the
theoretical continuous model generates slightly larger node degrees.

Figure 1: Complement of cumulative degree distribution for small ($n=1{,}000$;
left plot) and large ($n=1{,}000{,}000$; right plot) graphs using the
following parameters: $\gamma=2.5$, $\delta=5$, and $\zeta=1/2$.

Our next experiment investigates how well Corollary 5.3 predicts the volume of
$\mathcal{A}$ in practice. For each value of $n=1000\cdot 2^{i}$,
$i\in\\{0,1,\ldots,15\\}$, we independently generated 100 graphs with the same
parameters as in the first experiment. On Figure 2 we present the average
value and the standard deviation of $\textrm{vol}(V)$. We use two different
scalings: $dn$, the theoretical asymptotic prediction using continuous power-
law distribution, and $\hat{d}n$ where $\hat{d}=\sum_{k=\delta}^{D}\ kr_{k}$
(see (3) for a definition of $r_{k}$), the discrete counterpart of $d$. Since
discrete distribution is used by default by the ABCD generator, in line what
we observed in Figure 1, the continuous prediction is a little bit off but the
discrete one works well, especially for large graphs.

Figure 2: The average volume of 100 independently generated graphs; shaded
area represents the standard deviation. Both quantities were normalized by the
theoretical prediction for continuous model (red curve) and discrete one (blue
curve). The dashed line at 1 corresponds to a perfect prediction. Parameters
used: $\gamma=2.5$, $\delta=5$, and $\zeta=1/2$ (left plot), and $\gamma=2.5$,
$\delta=25$, and $\zeta=1/2$ (right plot).

###  5.2 Distribution of Community Sizes

Let $\beta\in(1,2)$, $s\in\mathbb{N}$, and $\tau\in(\zeta,1)$. Recall that
community sizes of the ABCD model are generated randomly following the
(truncated) _power-law distribution_ $\mathcal{P}(\beta,s,\tau)$ with exponent
$\beta$, minimum value $s$, and maximum value $S=n^{\tau}$. More precisely, if
$X\in\mathcal{P}(\beta,s,\tau)$, then after following exactly the same
computation as in (5.1) and (9) we get that for any
$k\in\\{s,s+1,\ldots,S\\}$,

$\displaystyle p_{k}$ $\displaystyle=$
$\displaystyle\Pr(X=k)=\frac{\int_{k}^{k+1}x^{-\beta}dx}{\int_{s}^{S+1}x^{-\beta}dx}=\frac{k^{1-\beta}-(k+1)^{1-\beta}}{s^{1-\beta}-(S+1)^{1-\beta}}$
(12) $\displaystyle=$
$\displaystyle(1+\mathcal{O}(n^{-\tau(\beta-1)}))\left(k^{-(\beta-1)}-(k+1)^{-(\beta-1)}\right)s^{\beta-1}$
$\displaystyle=$
$\displaystyle(1+\mathcal{O}(n^{-\tau(\beta-1)})+\mathcal{O}(k^{-1}))\
k^{-\beta}(\beta-1)s^{\beta-1}.$ (13)

Community sizes of ABCD are generated randomly and independently, each of them
following power-law distribution $\mathcal{P}(\beta,s,\tau)$. Our first task
is to investigate how many communities there are in a graph on $n$ nodes, and
how their sizes are distributed. It is slightly easier to fix the number of
communities, generate their sizes independently, and check how large graph
they span. Once we establish this, we will simply inverse the process, fix the
number of nodes of the graph to be $n$ and compute the number of communities
$\ell$ that need to be generated to reach the desired number of nodes.

The assumption that $\tau>\zeta$ is introduced to make sure large degree nodes
have large enough communities to be assigned to. We do not need this
assumption in the first lemma as it is concerned with a sequence of random
variables, not the ABCD model.

######  Lemma 5.4.

Let $\beta\in(1,2)$, $s\in\mathbb{N}$, and $\tau\in(0,1)$. Let

$\ell=\ell(n)=cn^{1-\tau(2-\beta)}$

for some function $c=c(n)\to\hat{c}$, where $\hat{c}\in\mathbb{R}_{+}$. Let
$(X_{1},X_{2},\ldots,X_{\ell})$ be a sequence of independent random variables,
$X_{i}\in\mathcal{P}(\beta,s,\tau)$ for any $i\in[\ell]$. For
$k\in\mathbb{N}$, let $Y_{k}$ be the random variable counting the number of
variables $X_{i}$ that are equal to $k$. For $k\in\mathbb{N}$ and
$\eta=\eta(n)$, let $Y_{k}^{\eta}$ be the random variable counting the number
of variables $X_{i}$ that are at least $k$ but at most $(1+\eta)k$.

The following properties hold _w.e.p._ :

  * (a)

If $\tau\in(0,1/2)$, then for any $k\in\mathbb{N}$ such that $s\leq k\leq
n^{\tau}$ we have

$\displaystyle Y_{k}$ $\displaystyle=$ $\displaystyle(1+\mathcal{O}((\log
n)^{-1}))\ \ell p_{k}$ (14) $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-1}))\
cn^{1-\tau(2-\beta)}\left(k^{-(\beta-1)}-(k+1)^{-(\beta-1)}\right)s^{\beta-1}$
$\displaystyle=$ $\displaystyle(1+\mathcal{O}(k^{-1})+\mathcal{O}((\log
n)^{-1}))\ cn^{1-\tau(2-\beta)}k^{-\beta}(\beta-1)s^{\beta-1}.$

  * (b)

If $\tau\in[1/2,1)$, then for any $k\in\mathbb{N}$ such that $s\leq k\leq
n^{\tau-(2\tau-1)/\beta}(\log n)^{-4/\beta}\ll n^{\tau}$ random variable
$Y_{k}$ satisfies (14), and for any $k\in\mathbb{N}$ such that
$n^{\tau-(2\tau-1)/\beta}(\log n)^{-4/\beta}\leq k\leq n^{\tau}/(1+\delta)$ we
have

$\displaystyle Y_{k}^{\eta}$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-1}))\ \ell\eta kp_{k}$
$\displaystyle=$ $\displaystyle(1+\mathcal{O}((\log n)^{-1}))\
c(\beta-1)s^{\beta-1}(\log n)^{4},$

where

$\eta=\eta(k)=n^{\tau(2-\beta)-1}(\log n)^{4}k^{\beta-1}\leq
n^{-(1-\tau)}(\log n)^{4}=\mathcal{O}((\log n)^{-1})=o(1).$

In any case,

$\sum_{i=1}^{\ell}X_{i}=(1+\mathcal{O}((\log n)^{-1}))\ cns^{\beta-1}\
\frac{\beta-1}{2-\beta}=(1+o(1))n,$ (15)

provided

$\hat{c}=\frac{2-\beta}{(\beta-1)s^{\beta-1}}.$

Before we prove the lemma, let us state the following straightforward
implication for the ABCD model.

######  Corollary 5.5.

Let $\beta\in(1,2)$, $s\in\mathbb{N}$, and $\tau\in(\zeta,1)$. The following
properties hold _w.e.p._ for $\mathcal{A}$.

  * (a)

The number of communities is equal to

$\ell=\ell(n)=(1+\mathcal{O}((\log n)^{-1}))\,\hat{c}\,n^{1-\tau(2-\beta)},$

where

$\hat{c}=\frac{2-\beta}{(\beta-1)s^{\beta-1}}.$

  * (b)

For $k\in\mathbb{N}$, let $Y_{k}$ be the number of communities of size $k$.
For $k\in\mathbb{N}$ and $\eta=\eta(n)$, let $Y_{k}^{\eta}$ be the number of
communities of size at least $k$ but at most $(1+\eta)k$. Random variables
$Y_{k}$ and $Y_{k}^{\eta}$ satisfy properties (a) and (b) in Lemma 5.4.

###### Proof.

Recall that community sizes are generated independently following power-law
distribution $\mathcal{P}(\beta,s,\tau)$ until the sum of their sizes reaches
$n$. By Lemma 5.4 (see (15)), _w.e.p._ after generating

$\ell_{\ell}=\ell_{\ell}(n)=(1-a\,(\log
n)^{-1})\,\hat{c}\,n^{1-\tau(2-\beta)}$

communities, the sum is still below $n$ provided that $a$ is a large enough
constant. On the other hand, after generating

$\ell_{u}=\ell_{u}(n)=(1+a\,(\log n)^{-1})\,\hat{c}\,n^{1-\tau(2-\beta)}$

communities, _w.e.p._ the sum exceeds $n$, again, provided that $a$ is large
enough. It follows that _w.e.p._ $\ell_{\ell}\leq\ell\leq\ell_{u}$. This
finishes part (a) of the corollary.

Recall that once the desired number of nodes is reached, either the last
community is “trimmed” or at most $s-1=O(1)$ communities increase their sizes.
To see that part (b) holds, note that the bounds for $Y_{k}$ and
$Y_{k}^{\eta}$ implied by Lemma 5.4 are asymptotically the same, regardless
whether the lemma is applied for $\ell_{\ell}$ or for $\ell_{u}$. Moreover,
these bounds are of order at least $(\log n)^{4}$ and so affecting $O(1)$
communities at the end of the process will not affect the final bounds. The
proof of the corollary is finished. ∎

Now we are ready to get back to Lemma 5.4. The proof of the lemma is a
straightforward adaptation of the one of Lemma 5.2.

###### Proof of Lemma 5.4.

We will call a random variable $X_{i}$ _light_ if $X_{i}\leq K$, where

$K:=\min\left(n^{\tau-(2\tau-1)/\beta}(\log n)^{-4/\beta},n^{\tau}\right);$

otherwise, $X_{i}$ will be called _heavy_. Note that if $\tau<1/2$, then
$K=n^{\tau}$ so all variables are light. On the other hand, if $\tau\geq 1/2$,
then $K=n^{\tau-(2\tau-1)/\beta}(\log n)^{-4/\beta}\ll n^{\tau}$ and so we
will have a mixture of light and heavy variables.

We start with light variables. Let us fix $k\in\mathbb{N}$ such that $s\leq
k\leq K$. Using (13), we get that

$\mathbb{E}[Y_{k}]=\ell
p_{k}=\Theta(n^{1-\tau(2-\beta)}k^{-\beta})=\Omega(n^{1-\tau(2-\beta)}K^{-\beta})=\Omega((\log
n)^{4}).$

After applying Chernoff’s bound (5) with $\varepsilon=(\log n)^{-1}$ we get
that _w.e.p._

$Y_{k}=(1+\mathcal{O}((\log n)^{-1}))\mathbb{E}[Y_{k}]=(1+\mathcal{O}((\log
n)^{-1}))\ell p_{k}.$

The other two equalities in (14) follow immediately from (12) and (13). This
finishes part (a) and the first half of part (b).

We move now to heavy variables. Assume that $\tau\geq 1/2$ and let us fix
$k\in\mathbb{N}$ such that $K\leq k\leq n^{\tau}/(1+\eta)$. Let us also fix

$\eta=\eta(k)=n^{\tau(2-\beta)-1}(\log n)^{4}k^{\beta-1}.$

Recall that random variable $Y_{k}^{\eta}$ counts a _batch_ of variables
$X_{i}$ that are at least $k$ but at most $(1+\eta)k$. Note that $\eta(k)$ is
an increasing function of $k$. Moreover, $\eta(K)=1/K$ so only a few values
are considered for $k=K$ (note that $\eta(K)K=1$). On the other extreme,
$\eta(n^{\tau})=n^{-(1-\tau)}(\log n)^{4}$ which is still $\mathcal{O}((\log
n)^{-1})=o(1)$. It implies that all variables in the batch are equal to
$(1+\mathcal{O}(\eta))k=(1+\mathcal{O}((\log n)^{-1}))k$. As before, using
(13) we get that

$\mathbb{E}[Y_{k}^{\eta}]=\ell\sum_{i=k}^{(1+\eta)k}p_{k}=\Theta\left(n^{1-\tau(2-\beta)}(\eta
k)k^{-\beta}\right)=\Omega((\log n)^{4}).$

After applying Chernoff’s bound (5) with $\varepsilon=(\log n)^{-1}$ we get
that _w.e.p._

$Y_{k}^{\eta}=(1+\mathcal{O}((\log
n)^{-1}))\mathbb{E}[Y_{k}^{\eta}]=(1+\mathcal{O}((\log n)^{-1}))\ \ell\eta
kp_{k}.$

This finishes the second half of part (b).

It remains to show (15). Since we aim for a statement that holds _w.e.p._ , we
may assume that parts (a) and (b) hold. First, let us note that

$\sum_{i=1}^{\ell}X_{i}=\sum_{k=s}^{n^{\tau}}kY_{k}.$

Light variables can be delt with immediately: for any $k\in\mathbb{N}$ such
that $s\leq k\leq K$ we have

$kY_{k}=(1+\mathcal{O}((\log n)^{-1}))\ k\ell p_{k}.$

For heavy variables we again use the fact that all variables in one batch have
asymptotically the same value. For any $k\in\mathbb{N}$ such that $K\leq k\leq
n^{\tau}/(1+\eta)$ we have

$\displaystyle\sum_{i=k}^{(1+\eta)k}iY_{i}$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}(\eta))k\sum_{i=k}^{(1+\eta)k}Y_{i}=(1+\mathcal{O}((\log
n)^{-1}))\ kY_{k}^{\eta}$ $\displaystyle=$ $\displaystyle(1+\mathcal{O}((\log
n)^{-1}))\ k\ell\eta kp_{k}=(1+\mathcal{O}((\log
n)^{-1}))\sum_{i=k}^{(1+\eta)k}i\ell p_{i}.$

It follows that

$\sum_{i=1}^{\ell}X_{i}=\sum_{k=s}^{n^{\tau}}kY_{k}=(1+\mathcal{O}((\log
n)^{-1}))\sum_{k=s}^{n^{\tau}}k\ell p_{k}.$

Now, note that the contribution from the first $\log n$ terms is negligible:

$\displaystyle\sum_{k=s}^{\log n}k\ell p_{k}$ $\displaystyle=$
$\displaystyle\mathcal{O}\left(n^{1-\tau(2-\beta)}\sum_{k=s}^{\log
n}k^{1-\beta}\right)=\mathcal{O}\left(n^{1-\tau(2-\beta)}\int_{s}^{\log
n}x^{1-\beta}dx\right)$ $\displaystyle=$
$\displaystyle\mathcal{O}\left(n^{1-\tau(2-\beta)}(\log
n)^{2-\beta}\right)=\mathcal{O}\left(n/\log n\right).$

On the other hand,

$\displaystyle\sum_{k=\log n}^{n^{\tau}}k\ell p_{k}$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-1}))\
cn^{1-\tau(2-\beta)}(\beta-1)s^{\beta-1}\sum_{k=\log n}^{n^{\tau}}k^{1-\beta}$
$\displaystyle=$ $\displaystyle(1+\mathcal{O}((\log n)^{-1}))\
cn^{1-\tau(2-\beta)}(\beta-1)s^{\beta-1}\int_{\log
n}^{n^{\tau}}x^{1-\beta}dx+\mathcal{O}(1)$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-1}))\
cn^{1-\tau(2-\beta)}(\beta-1)s^{\beta-1}\frac{n^{\tau(2-\beta)}-(\log
n)^{2-\beta}}{2-\beta}$ $\displaystyle=$ $\displaystyle(1+\mathcal{O}((\log
n)^{-1}))\ cns^{\beta-1}\ \frac{\beta-1}{2-\beta}.$

This finishes the proof of (15), and so the theorem holds. ∎

#### Simulation Corner

We generated community sizes for two ABCD graphs $\mathcal{A}$ on $n=1{,}000$
and, respectively, $n=1{,}000{,}000$ nodes. In both cases, we used parameters
$\beta=1.5$, $s=50$, and $\tau=3/4$ (that is, $S=n^{3/4}$). On Figure 3 we
plot the complement of the cumulative distribution (that is, the fraction of
communities that consist of at least $K$ nodes) and compare it with
asymptotic, theoretical predictions, namely, function

$\sum_{k=K}^{S}p_{k}=\frac{\int_{K}^{S+1}x^{-\beta}dx}{\int_{s}^{S+1}x^{-\beta}dx}=\frac{K^{1-\beta}-(S+1)^{1-\beta}}{s^{1-\beta}-(S+1)^{1-\beta}}.$

Simulation results are averaged over 30 independent runs in view of the small
number of communities compared to $n$. Note that since $s=50$ is much larger
than $\delta=5$, in Figure 1 we do not observe a large difference between
theoretical and simulated curves (the largest discrepancy between the
continuous ($q_{k}$) and the discrete ($r_{k}$) distributions is observed for
small values of $k$).

Figure 3: Complement of cumulative community size distribution for small
($n=1{,}000$; left plot) and large ($n=1{,}000{,}000$; right plot) graphs.
Parameter used: $\beta=1.5$, $s=50$, and $\tau=3/4$.

To see how well Corollary 5.5 predicts the number of communities in practice,
for each value of $n=1000\cdot 2^{i}$, $i\in\\{0,1,\ldots,15\\}$, we
independently generated 100 graphs with the same parameters as in the above
experiment and three other sets of parameters. On Figure 4 we present the
average number of communities and its standard deviation. In our theoretical
results, we do not pay attention to signs of error terms as all of them tend
to zero as $n\to\infty$. However, based on the simulation, it seems that the
error term is negative for $\beta<1.5$ and positive for $\beta>1.5$ but, as
expected, it diminishes to zero asymptotically. Additionally, note that the
standard deviation of the normalized number of communities is significant even
for large graphs, as opposed to standard deviation of the normalized volume
presented in Figure 2.

Figure 4: The average number of communities for 100 independently generated
graphs; shaded area represents the standard deviation. Both quantities were
normalized by the theoretical prediction. The dashed line at 1 corresponds to
a perfect prediction. All plots are with $s=50$. The top two plots are shown
with the same range on the y axis for comparison, i.e. decreasing $\tau$
lowers the variability. In the bottom plots, we see that convergence is slower
for values of $\beta$ away from 1.5.

###  5.3 Assigning Nodes into Communities and Distribution of Weights

Recall that at this point of the process, the degree distribution $(w_{1}\geq
w_{2}\geq\ldots\geq w_{n})$ and the distribution of community sizes
$(c_{1}\geq c_{2}\geq\ldots\geq c_{\ell})$ are already fixed. In order to
assign nodes to communities we will use the following easy and natural
algorithm. We consider nodes, one by one, starting from $w_{1}$ (high degree
node) and finishing with $w_{n}$ (low degree node). Recall that node $i$ of
degree $w_{i}$ has to be assigned to a community of size $c_{j}$ so that
inequality (1) holds. We assign node $w_{i}$ randomly to one of the
communities that have size larger than $\lceil(1-\xi\phi)w_{i}\rceil$ and
still have some “available spots”. We do it with probability proportional to
the number of available spots left.

Note that it follows immediately from Corollary 5.5 that _w.e.p._
$\phi=1-\sum_{k\in[\ell]}(c_{k}/n)^{2}=1-o(1)$, since

$\displaystyle\sum_{k\in[\ell]}(c_{k}/n)^{2}$ $\displaystyle=$
$\displaystyle\sum_{k=s}^{n^{\tau}}Y_{k}(k/n)^{2}=\sum_{k=s}^{n^{\tau}}\mathcal{O}\left(n^{1-\tau(2-\beta)}k^{-\beta}(k/n)^{2}\right)$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(n^{-1-\tau(2-\beta)}\sum_{k=s}^{n^{\tau}}k^{2-\beta}\right)=\mathcal{O}\left(n^{-1-\tau(2-\beta)}n^{\tau(3-\beta)}\right)=\mathcal{O}\left(n^{-(1-\tau)}\right)=o(1).$

In order to see that the above simple algorithm generates one of the
admissible assignments uniformly at random, let $t_{i}$ be the number of
available spots (at the beginning of the process) for node $i$, that is, the
total number of nodes that belong to communities satisfying inequality (1):

$t_{i}=\sum_{j\in I_{i}}c_{j},\hskip 28.45274pt\text{ where
}I_{i}=\Big{\\{}j\in[\ell]:w_{i}\leq\frac{c_{j}-1}{1-\xi\phi}\Big{\\}}=\Big{\\{}j\in[\ell]:c_{j}\geq(1-\xi\phi)w_{i}+1\Big{\\}}.$

Since nodes are considered in non-increasing order of their degrees, exactly
$i-1$ of these $t_{i}$ available spots are taken by other nodes when it is
time for node $i$ to be assigned to some community.

To see that _w.e.p._ $t_{i}\geq i$, consider any node of degree $k$ such that
$\delta\leq k\leq n^{\zeta}(\log n)^{-5/(\gamma-1)}$. It follows from Lemma
5.2 that when this node is considered by the algorithm, _w.e.p._ its index $i$
satisfies the following property:

$i=\Theta\left(\sum_{i=\delta}^{k}nq_{i}\right)=\Theta\left(n\sum_{i=\delta}^{k}i^{-\gamma}\right)=\Theta\left(nk^{-(\gamma-1)}\right).$

On the other hand, by Corollary 5.5, _w.e.p._

$t_{i}=n-\Theta\left(\sum_{i=s}^{(1-\xi\phi)k}\ell
ip_{i}\right)=n-\Theta\left(n^{1-\tau(2-\beta)}\sum_{i=s}^{(1-\xi\phi)k}i^{1-\beta}\right)=n-\Theta\left(n\left(\frac{k}{n^{\tau}}\right)^{2-\beta}\right).$

Both $i$ and $t_{i}$ are decreasing functions of $k$ but clearly $t_{i}\geq
i$. In fact, note that _w.e.p._ $t_{1}=n(1-o(1))$ so almost all nodes are
available right from the very beginning when a node of maximum degree is
considered. Since _w.e.p._ there are linearly many nodes of degree $\delta$,
we process all nodes of degrees at least $\delta+1$ before there is
potentially a problem.

It follows that each admissible assignment is used with probability equal to

$\prod_{i=1}^{n}\frac{1}{t_{i}-(i-1)},$

which is a fixed number that depends on the sequences $(w_{1}\geq
w_{2}\geq\ldots\geq w_{n})$ and $(c_{1}\geq c_{2}\geq\ldots\geq c_{\ell})$ but
not on the choice of admissible assignment. Since the algorithm cannot produce
any non-admissible assignment, this shows a uniformity.

We say that the community is _large_ if its size is at least $(\log n)^{8}$
and _very large_ if it is of size at least $n^{\zeta}(\log n)^{4}$; otherwise,
it will be called _small_. The volumes of small communities are not well
concentrated around their means. For example, a community $C\subseteq V$ of
constant size ($|C|=O(1)$) has to have average degree satisfying

$\delta\leq\frac{\textrm{vol}(C)}{|C|}\leq\left\lfloor\frac{|C|-1}{1-\xi\phi}\right\rfloor,$

but it could be equal to any of the two extreme values with probability
bounded away from zero. Hence, in this situation there is no hope for
determining an asymptotic value for its volume that holds _w.e.p._ On the
other hand, the volumes of very large communities are well concentrated around
their means, as the next lemma shows.

Recall that each node has its degree $w_{i}$ randomly split into community
degree $y_{i}$ and background degree $z_{i}$. For non-leaders, we have
precisely $\mathbb{E}[y_{i}]=(1-\xi)w_{i}$ but the leaders might require
adjustment implying that $\mathbb{E}[y_{i}]=(1-\xi)w_{i}+O(1)$ (which is, of
course, negligible from our asymptotic results point of view). For any
community $C\subseteq V$, let

$\textrm{vol}_{c}(C):=\sum_{i\in C}y_{i}$

be the community volume. We expect $(1-\xi)$ fraction of the total volume of
each community to be assigned to community degrees, that is,
$\mathbb{E}[\textrm{vol}_{c}(C)]=(1-\xi)\textrm{vol}(C)+O(1)$. Similarly to
the total volumes, for very large communities we will prove that
$\textrm{vol}_{c}(C)$ is well concentrated around their expectations.

Now we are ready to state the next lemma.

######  Lemma 5.6.

Let $C\subseteq V$ be any large community in $\mathcal{A}$, that is, community
of size $|C|\geq(\log n)^{8}$. Then,

$\displaystyle\mathbb{E}[\textrm{vol}(C)]$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-(\gamma-2)}))\,d|C|,\text{ and }$
$\displaystyle\mathbb{E}[\textrm{vol}_{c}(C)]$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-(\gamma-2)}))\,(1-\xi)d|C|,\hskip
28.45274pt\text{ where }d:=\sum_{k=\delta}^{D}\ kq_{k}.$

Moreover, the following properties hold _w.e.p._ If $C$ is very large (that
is, $|C|\geq n^{\zeta}(\log n)^{4}$), then

$\displaystyle\textrm{vol}(C)$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-(\gamma-2)}))\,d|C|,\text{ and }$
$\displaystyle\textrm{vol}_{c}(C)$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-(\gamma-2)}))\,(1-\xi)d|C|.$

If $C$ is large (that is, $(\log n)^{8}\leq|C|<n^{\zeta}(\log n)^{4}$), then
$\textrm{vol}(C)=\mathcal{O}(n^{\zeta}(\log n)^{4})$.
If $C$ is small (that is, $|C|<(\log n)^{8}$), then trivially
$\textrm{vol}(C)\leq D|C|<n^{\zeta}(\log n)^{8}$.
Finally, $\textrm{vol}(F)=\mathcal{O}(n(\log n)^{-2})$, where $F$ is the union
of small and large communities.

Let us note that the constant $d$ used in the above lemma is the same as in
Corollary 5.3. Some useful and explicit bounds for $d$ are provided right
after the statement of this corollary.

###### Proof.

Let us fix any community $C\subseteq V$ of size $z=|C|\geq z_{0}:=(\log
n)^{8}$. If, for example, $z>n^{\zeta}$, then community $C$ has enough room
even for a node of the largest degree. However, if $z$ is small then only
nodes of degree at most $\left\lfloor\frac{z-1}{1-\xi\phi}\right\rfloor$ are
allowed to be assigned to $C$. Fortunately, _w.e.p._ the number of nodes of
degree larger than $K_{0}:=\left\lfloor\frac{z-1}{1-\xi\phi}\right\rfloor\geq
k_{0}:=\left\lfloor\frac{z_{0}-1}{1-\xi\phi}\right\rfloor=\Omega((\log
n)^{8})$ is, by Lemma 5.2, equal to

$\displaystyle n^{\prime}$ $\displaystyle=$
$\displaystyle\sum_{k>K_{0}}Y_{k}\leq\sum_{k>k_{0}}Y_{k}=(1+\mathcal{O}((\log
n)^{-1}))\
\sum_{k>k_{0}}nq_{k}=\mathcal{O}\left(\sum_{k>k_{0}}nk^{-\gamma}\right)$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(nk_{0}^{1-\gamma}\right)=\mathcal{O}\left(n\
(\log n)^{-8(\gamma-1)}\right)=\mathcal{O}\left(n\ (\log n)^{-2}\right)=o(n),$

and so is negligible.

In order to track which nodes end up in community $C$, we need to start paying
attention to the algorithm generating admissible assignments from time
$n^{\prime}+1$ when considered nodes have a chance to end up in community $C$
(because their degrees are at most $K_{0}$). Based on the observation above,
right before this happens there are only $n^{\prime}=\mathcal{O}\left(n\ (\log
n)^{-2}\right)$ spots taken from communities of size at least $z+1$. On the
other hand, all the remaining nodes may be assigned to any community of size
more than $n^{\zeta}$, the trivial upper bound for the maximum degree. By
Corollary 5.5, _w.e.p._ the total number of spots available in communities of
size at most $n^{\zeta}$ is equal to

$\displaystyle n^{\prime\prime}$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-1}))\ \sum_{k\leq n^{\zeta}}\ell
kp_{k}=\mathcal{O}\left(\sum_{k\leq
n^{\zeta}}n^{1-\tau(2-\beta)}k^{1-\beta}\right)$ (16) $\displaystyle=$
$\displaystyle\mathcal{O}\left(n^{1-\tau(2-\beta)}n^{\zeta(2-\beta)}\right)=\mathcal{O}\left(n^{1-(\tau-\zeta)(2-\beta)}\right)=\mathcal{O}\left(n\
(\log n)^{-2}\right)=o(n).$

It follows that once $n^{\prime}+t$ nodes are assigned to communities, the
number of nodes assigned to community $C$ can be stochastically upper bounded
by $U_{t}$, the hypergeometric random variable with parameters
$n-n^{\prime}-n^{\prime\prime}=n(1-\mathcal{O}((\log n)^{-2}))$, $z$, $t$ and
lower bounded by $L_{t}$, the hypergeometric random variable with parameters
$n-n^{\prime}=n(1-\mathcal{O}((\log n)^{-2}))$, $z$, $t$.

Suppose first that $t\leq n\,(\log n)^{6}/z=\mathcal{O}(n\,(\log n)^{-2})$.
Note that
$\mathbb{E}[U_{t}]=zt/(n-n^{\prime}-n^{\prime\prime})=\mathcal{O}((\log
n)^{6})$. Chernoff bound (6) applied with $u=(\log n)^{6}$ gives us that
_w.e.p._ $U_{t}=\mathcal{O}((\log n)^{6})$. Hence, during this phase of the
algorithm, a node considered at time $t+1$ is assigned to community $C$ with
probability

$\displaystyle\exp(-\Omega((\log
n)^{2}))+\frac{z-\mathcal{O}(U_{t})}{n(1-\mathcal{O}((\log n)^{-2}))-t}$
$\displaystyle=$ $\displaystyle\frac{z-\mathcal{O}((\log
n)^{6})}{n(1-\mathcal{O}((\log n)^{-2}))-\mathcal{O}(n\,(\log n)^{-2})}$
$\displaystyle=$ $\displaystyle\frac{z}{n}\left(1+\mathcal{O}((\log
n)^{-2})\right).$

Suppose now that $n\,(\log n)^{6}/z\leq t\leq n-n\,(\log n)^{-1}$ so that
$\mathbb{E}[U_{t}]\geq\mathbb{E}[L_{t}]=zt/(n-n^{\prime})\geq(\log n)^{6}$.
Chernoff bound (5) applied with $\varepsilon=(\log n)^{-2}$ gives us that
_w.e.p._

$U_{t}=\mathbb{E}[U_{t}]\left(1+\mathcal{O}((\log
n)^{-2})\right)=\frac{zt}{n}\left(1+\mathcal{O}((\log n)^{-2})\right).$

Similarly, _w.e.p._ $L_{t}=(zt/n)(1+\mathcal{O}((\log n)^{-2}))$. During this
phase of the algorithm, a node considered at time $t+1$ is assigned to
community $C$ with probability

$\displaystyle\exp(-\Omega((\log n)^{2}))+\frac{z-(zt/n)(1+\mathcal{O}((\log
n)^{-2}))}{n(1-\mathcal{O}((\log n)^{-2}))-t}$ $\displaystyle=$
$\displaystyle\frac{z(1-t/n+\mathcal{O}((t/n)(\log
n)^{-2}))}{(n-t)(1-\mathcal{O}((\log n)^{-1}))}$ $\displaystyle=$
$\displaystyle\frac{z(1-t/n)(1+\mathcal{O}((\log
n)^{-1}))}{(n-t)(1-\mathcal{O}((\log n)^{-1}))}$ $\displaystyle=$
$\displaystyle\frac{z}{n}\left(1+\mathcal{O}((\log n)^{-1})\right),$

since $t\leq n-n\,(\log n)^{-1}$. The end of the algorithm is unpredictable;
we claim no bound for the probability of assigning a node to community $C$
when $t>n-n\,(\log n)^{-1}$. However, fortunately, the contribution from these
nodes will turn out to be negligible.

Let us now “rewind” the process and “play” it from the very beginning, this
time paying attention what kind of nodes are assigned to community $C$. Our
goal is to estimate $\textrm{vol}(C)$, the volume of community $C$ of size $z$
and $\textrm{vol}_{c}(C)$, the community volume of $C$. Since the adjustment
needed for the leader of $C$ changes the value of $\textrm{vol}_{c}(C)$ by at
most 1 (and so is negligible), we may assume that each node of degree $w_{i}$
assigned to community $C$ is non-leader, that is, its community degree is
equal to $y_{i}=\lfloor(1-\xi)w_{i}\rceil$.

Let $A$ be the set of nodes of degree larger than
$K_{0}=\left\lfloor\frac{z-1}{1-\xi\phi}\right\rfloor\geq
k_{0}=\left\lfloor\frac{z_{0}-1}{1-\xi\phi}\right\rfloor=\Omega((\log n)^{8})$
that cannot be assigned to community $C$. By Lemma 5.2, _w.e.p._ the volume of
$A$ is equal to

$\displaystyle\textrm{vol}(A)$ $\displaystyle=$
$\displaystyle\sum_{k>K_{0}}kY_{k}\leq\sum_{k>k_{0}}kY_{k}=(1+\mathcal{O}((\log
n)^{-1}))\
\sum_{k>k_{0}}nkq_{k}=\mathcal{O}\left(\sum_{k>k_{0}}nk^{1-\gamma}\right)$
$\displaystyle=$
$\displaystyle\mathcal{O}\left(nk_{0}^{2-\gamma}\right)=\mathcal{O}\left(n\
(\log n)^{-8(\gamma-2)}\right)=o(n),$

and so is negligible comparing to the total volume that is _w.e.p._ linear
(see Corollary 5.3). Let $B$ be the set of the last $n\,(\log n)^{-1}$ nodes
that we do not control, that is, we cannot predict the probability that a
given node joins $C$ but we will be able to say how many of them do it. Since
_w.e.p._ these nodes have degree $\delta$ and so
$\textrm{vol}(B)=\mathcal{O}(n\,(\log n)^{-1})$. More importantly, the
expected number of spots already taken from community $C$ when the nodes from
$B$ are about to be considered is equal to

$\frac{z}{n}\left(1+\mathcal{O}((\log
n)^{-1})\right)\cdot(|V|-|A|-|B|)=z\left(1+\mathcal{O}((\log n)^{-1})\right).$

Hence, the expected number of spots left is $\mathcal{O}(z(\log n)^{-1})$ and
so _w.e.p._ at most $\mathcal{O}(z(\log n)^{-1})$ are indeed left by Chernoff
bound (6) applied with $u=z(\log n)^{-1}\geq(\log n)^{7}$. It follows that

$\displaystyle\mathbb{E}[\textrm{vol}(C)]$ $\displaystyle=$
$\displaystyle\frac{z}{n}\left(1+\mathcal{O}((\log
n)^{-1})\right)\cdot(\textrm{vol}(V)-\textrm{vol}(A)-\textrm{vol}(B))+\mathcal{O}(z(\log
n)^{-1})$ $\displaystyle=$
$\displaystyle\textrm{vol}(V)\cdot\frac{z}{n}\left(1+\mathcal{O}((\log
n)^{-\min(1,8(\gamma-2))})\right)$ $\displaystyle=$ $\displaystyle
dz\left(1+\mathcal{O}((\log n)^{-(\gamma-2)})\right).$

From this we immediately get that

$\mathbb{E}[\textrm{vol}_{c}(C)]=(1-\xi)\mathbb{E}[\textrm{vol}(C)]=(1-\xi)dz\left(1+\mathcal{O}((\log
n)^{-(\gamma-2)})\right).$

The concentration for very large communities follows from Lemma 4.1. Note that
if $C$ is very large, then both $\mathbb{E}[\textrm{vol}(C)]$ and
$\mathbb{E}[\textrm{vol}_{c}(C)]$ are of order $z=\Omega(n^{\zeta}(\log
n)^{4})$. We get the desired bound for the failure probability by applying the
lemma with $\varepsilon=(\log n)^{-1}$ and $c=D=n^{\zeta}$. If $C$ is large,
then $\mathbb{E}[\textrm{vol}(C)]=\mathcal{O}(n^{\zeta}(\log n)^{4})$. The
lemma applied with $u=n^{\zeta}(\log n)^{4}$ and $c=D=n^{\zeta}$ gives us that
_w.e.p._ $\textrm{vol}(C)=\mathcal{O}(n^{\zeta}(\log n)^{4})$. Finally, by
performing the same computation as in (16) we get that _w.e.p._
$|F|=\mathcal{O}\left(n\ (\log n)^{-2}\right)=o(n)$. It follows that
$\mathbb{E}[\textrm{vol}(F)]=\mathcal{O}\left(n\ (\log n)^{-2}\right)$ and so
_w.e.p._ $\textrm{vol}(F)=\mathcal{O}\left(n\ (\log n)^{-2}\right)$, which
finishes the proof of the lemma. ∎

#### Simulation Corner

In order to see whether asymptotic predictions of volumes of large communities
can be used to predict the behaviour for all communities and for relatively
small values of $n$, we generated two ABCD graphs $\mathcal{A}$ on $n=1{,}000$
and, respectively, $n=1{,}000{,}000$ nodes. In both cases, we used parameters
$\gamma=2.5$, $\delta=5$, $\zeta=1/2<2/3=1/(\gamma-1)$ (that is,
$D=\sqrt{n}$), $\beta=1.5$, $s=50$, and $\tau=3/4$ (that is, $S=n^{3/4}$). On
Figure 5 for each generated graph $\mathcal{A}$ we plot $\ell$ points
$(x_{i},y_{i})$, one for each community $C_{i}$, $i\in[\ell]$: $x_{i}=|C_{i}|$
and $y_{i}=\textrm{vol}(C_{i})/(\hat{d}|C_{i}|)$, where
$\hat{d}=\sum_{k=\delta}^{D}\ kr_{k}$ is the discrete counterpart of $d$ (see
(3) for a definition of $r_{k}$). As expected, larger communities in a larger
graph on $n=1{,}000{,}000$ nodes show good concentration but small graphs on
$n=1{,}000$ nodes are too small and deviate from the expectation even for the
largest communities (that are still too small).

Figure 5: Volumes of communities $C_{i}$ scaled by $\hat{d}|C_{i}|$. The
dashed line at 1 corresponds to a perfect prediction. 30 independent small
graphs were generated ($n=1{,}000$; left plot) but only one large
($n=1{,}000{,}000$; right plot).

##  6 Modularity

###  6.1 Modularity of the Ground-truth Partition: $q(\mathbf{C})$

Let us start by investigating the modularity of the ground-truth partition of
$\mathcal{A}$.

######  Theorem 6.1.

Let $\mathbf{C}=\\{C_{1},C_{2},\ldots,C_{\ell}\\}$ be the ground-truth
partition of the set of nodes of $\mathcal{A}$. Then, _w.e.p._

$q^{*}(\mathcal{A})\geq q(\mathbf{C})=(1+\mathcal{O}((\log
n)^{-(\gamma-2)}))\,(1-\xi).$

###### Proof.

Let us first estimate the degree tax. By Corollary 5.3, _w.e.p._
$\textrm{vol}(V)=(1+\mathcal{O}((\log n)^{-1}))\ dn$, where
$d=\sum_{k=\delta}^{D}\ kq_{k}$. By Lemma 5.6, _w.e.p._ for each community
$C_{i}$ we have $\textrm{vol}(C_{i})=\mathcal{O}(n^{\zeta}(\log n)^{8})$. It
follows that _w.e.p._

$\sum_{C_{i}\in\mathbf{C}}\left(\frac{\textrm{vol}(C_{i})}{\textrm{vol}(V)}\right)^{2}=\mathcal{O}(n^{-(1-\zeta)}(\log
n)^{8})\sum_{C_{i}\in\mathbf{C}}\frac{\textrm{vol}(C_{i})}{\textrm{vol}(V)}=\mathcal{O}(n^{-(1-\zeta)}(\log
n)^{8})=\mathcal{O}((\log n)^{-2})=o(1),$

and so it is negligible.

Let us now move to the edge contribution that is more challenging to estimate.
We will use the terminology introduced in Lemma 5.6. In particular, we will
call community $C_{i}$ very large if $|C_{i}|\geq n^{\zeta}(\log n)^{4}$, and
$F$ is the union of communities that are not very large. By Lemma 5.6,
_w.e.p._ $\textrm{vol}(F)=\mathcal{O}(n\,(\log n)^{-2})$ and so the
contribution (to the edge contribution) from communities that are _not_ very
large is _w.e.p._ equal to

$\sum_{C_{i}\in\mathbf{C},|C_{i}|<n^{\zeta}(\log
n)^{4}}\frac{e(C_{i})}{|E|}\leq\sum_{C_{i}\in\mathbf{C},|C_{i}|<n^{\zeta}(\log
n)^{4}}\frac{\textrm{vol}(C_{i})/2}{\textrm{vol}(V)/2}=\frac{\textrm{vol}(F)}{\textrm{vol}(V)}=\mathcal{O}((\log
n)^{-2})=o(1),$

and so it is negligible. It remains to concentrate on very large communities.

Let $C_{i}$ be any very large community. By definition, trivially, all edges
of the community graph $G_{i}=(C_{i},E_{i})$ appear in $C_{i}$. By Lemma 5.6,
_w.e.p._ the number of edges in $G_{i}$ is equal to

$\displaystyle|E_{i}|=\textrm{vol}_{c}(C_{i})/2$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-(\gamma-2)}))\,(1-\xi)d|C|/2$
$\displaystyle=$ $\displaystyle(1+\mathcal{O}((\log
n)^{-(\gamma-2)}))\,(1-\xi)\textrm{vol}(C_{i})/2.$

To estimate the number of edges in the background graph $G_{0}$ that appear
within $C_{i}$ we can use the following useful property of the pairing model.
One does not need to select one pairing uniformly at random from the set of
all pairings but, instead, pairs of points may be chosen sequentially.
Moreover, the first point may be selected using any rule whatsoever as long as
the second point is chosen uniformly at random from the set of the remaining
unchosen points. By Lemma 5.6, _w.e.p._ the number of points in the background
graph that are associated with nodes in $C_{i}$ is equal to

$W=\textrm{vol}(C_{i})-\textrm{vol}_{c}(C_{i})=(1+\mathcal{O}((\log
n)^{-(\gamma-2)}))\,\xi d|C_{i}|.$

In our application, we will always select the first point of the $j$th pair
from the set of unchosen points associated with nodes in $C_{i}$
(arbitrarily). The probability that the second point is also in $C_{i}$ is
equal to

$p_{j}=\frac{W-(j+e_{j})}{\textrm{vol}(V)-(2j-1)}\leq\frac{W}{\textrm{vol}(V)}=:p,$

where $e_{j}$ is the number of pairs of points that already appeared within
$C_{i}$. (Indeed, at this point $2(j-1)+1=2j-1$ points are already chosen,
$j+e_{j}$ of them are associated with nodes in $C_{i}$.) Hence, the number of
edges from the background graph that end up within community $C_{i}$ can be
stochastically upper bounded by the binomial random variable
$X\in\textrm{Bin}(w,p)$ with $\mathbb{E}[X]=Wp=W^{2}/\textrm{vol}(V)$. If
$|C_{i}|\geq\sqrt{n}\,(\log n)$, then $\mathbb{E}[X]=\Omega((\log n)^{2})$ and
we get from Chernoff bound (applied with $\varepsilon=1$) that _w.e.p._

$X=\mathcal{O}(W^{2}/n)=\mathcal{O}(Wn^{-(1-\tau)})=\mathcal{O}(W\,(\log
n)^{-2})=\mathcal{O}(\textrm{vol}(C_{i})\,(\log n)^{-2}),$

since, by definition, $W=\Theta(|C_{i}|)=\mathcal{O}(n^{\tau})$. On the other
hand, if $|C_{i}|<\sqrt{n}\,(\log n)$, then $\mathbb{E}[X]=\mathcal{O}((\log
n)^{2})$ and we get from Chernoff bound (applied with $u=(\log n)^{2}$) that
_w.e.p._ $X=\mathcal{O}((\log n)^{2})$.

Since there are clearly at most $n/(n^{\zeta}(\log n)^{4})=n^{1-\zeta}(\log
n)^{-4}$ very large communities, _w.e.p._ the total number of edges in the
background graph $G_{0}$ that appear within some very large community $C_{i}$
is at most

$\displaystyle\sum_{C_{i}\in\mathbf{C},|C_{i}|\geq n^{\zeta}(\log n)^{4}}$
$\displaystyle\mathcal{O}(\textrm{vol}(C_{i})\,(\log n)^{-2})+n^{1-\zeta}(\log
n)^{-4}\cdot\mathcal{O}((\log n)^{2})$
$\displaystyle=\mathcal{O}(\textrm{vol}(V)\,(\log
n)^{-2})+\mathcal{O}(n^{1-\zeta}(\log n)^{-2})=\mathcal{O}(n\,(\log n)^{-2}).$

The contribution (to the edge contribution) from very large communities is
then _w.e.p._ equal to

$\displaystyle\sum_{C_{i}\in\mathbf{C},|C_{i}|\geq n^{\zeta}(\log n)^{4}}$
$\displaystyle\frac{e(C_{i})}{|E|}=\frac{\mathcal{O}(n(\log n)^{-2})}{|E|}\
+\sum_{C_{i}\in\mathbf{C},|C_{i}|\geq n^{\zeta}(\log
n)^{4}}\frac{|E_{i}|}{|E|}$ $\displaystyle=\mathcal{O}((\log n)^{-2})\
+(1+\mathcal{O}((\log n)^{-(\gamma-2)}))\,\sum_{C_{i}\in\mathbf{C},|C_{i}|\geq
n^{\zeta}(\log n)^{4}}\frac{(1-\xi)\textrm{vol}(C_{i})/2}{\textrm{vol}(V)/2}$
$\displaystyle=\mathcal{O}((\log n)^{-2})\ +(1+\mathcal{O}((\log
n)^{-(\gamma-2)}))\,(1-\xi)\,\frac{\textrm{vol}(V)-\textrm{vol}(F)}{\textrm{vol}(V)}$
$\displaystyle=\mathcal{O}((\log n)^{-2})\ +(1+\mathcal{O}((\log
n)^{-(\gamma-2)}))\,(1-\xi)\,(1+\mathcal{O}((\log n)^{-2}))$
$\displaystyle=(1+\mathcal{O}((\log n)^{-(\gamma-2)}))\,(1-\xi),$

which is the only non-negligible contribution to the modularity function. This
finishes the proof of the theorem. ∎

#### Simulation Corner

In order to see how well Theorem 6.1 predicts the modularity function
$q(\mathbf{C})$ in practice, for each value of $n=1000\cdot 2^{i}$,
$i\in\\{0,1,\ldots,15\\}$, we independently generated 30 graphs with the same
parameters as in the previous experiment: $\gamma=2.5$, $\delta=5$,
$\zeta=1/2<2/3=1/(\gamma-1)$ (that is, $D=\sqrt{n}$), $\beta=1.5$, $s=50$, and
$\tau=3/4$ (that is, $S=n^{3/4}$). On Figure 6 we present the average value
and the standard deviation of $q(\mathbf{C})$, the modularity of the ground-
truth partition, for two values of $\xi$: $\xi=0.2$ (low level of noise) and
$\xi=0.7$ (high level of noise). We also present the edge contribution part of
$q(\mathbf{C})$, again, its average value and the standard deviation. It seems
that the edge contribution for small graphs is slightly larger than the
corresponding asymptotic prediction but it converges quite fast. As expected,
the degree tax for small graphs is non-negligible but it converges to zero
quickly. As a result, both the value of $q(\mathbf{C})$ and the edge
contribution tend to $1-\xi$ as $n$ grows.

Figure 6: The modularity $q(\mathbf{C})$ of the ground-truth partition (red)
and the corresponding edge contribution (blue) for 30 independently generated
graphs; shaded areas represent the standard deviation. The dashed line at
$1-\xi$ corresponds to a perfect prediction. Parameters used: $\gamma=2.5$,
$\delta=5$, $\zeta=1/2$, $\beta=1.5$, $s=50$, and $\tau=3/4$. Two different
levels of noise are investigated.

Additionally, in order to investigate whether there is any difference for
various levels of noise, for each value of $\xi=(0.1)i$, $i\in[9]$, we
independently generated 30 graphs on $n=1{,}000$ nodes and $n=1{,}000{,}000$
nodes. The results are presented in Figure 7. As observed earlier, the edge
contribution for small graphs is slightly larger than $1-\xi$, the asymptotic
prediction. As expected, the difference is more visible for larger values of
$\xi$ as background graph edges in noisy graphs contribute more. On the other
hand, the modularity function is closer to its asymptotic prediction for more
noisy graphs. Large graphs show almost perfect agreement with the asymptotic
prediction.

Figure 7: The modularity $q(\mathbf{C})$ of the ground-truth partition (red)
and the corresponding edge contribution (blue) for 30 independently generated
graphs; shaded areas represent the standard deviation. The dashed line at
$1-\xi$ corresponds to a perfect prediction. Parameters used: $\gamma=2.5$,
$\delta=5$, $\zeta=1/2$, $\beta=1.5$, $s=50$, and $\tau=3/4$. Two different
graph sizes are investigated.

###  6.2 Maximum Modularity: $q^{*}(G)$

As mentioned in Section 3, analyzing the maximum modularity $q^{*}(G)$ for
sparse random graphs is a challenging task and typically only bounds for
$q^{*}(G)$ are known that are far apart from each other. Since the ABCD model
$\mathcal{A}$ is more complex than other sparse random graphs, especially
random $d$-regular graphs, there is no hope for tight bounds for the maximum
modularity function but we will make some interesting observations below.

#### Large Level of Noise

Let us start with investigating graphs with a large level of noise, that is,
with $\xi$ close to one. For such graphs, one should focus on the background
graph $G_{0}$ which involves all but a small fraction of edges. It turns out
that $G_{0}$ is connected _w.h.p._ , provided that its minimum degree is at
least 3, or otherwise _w.h.p._ it has a giant component. By restricting
ourselves to a spanning tree of the giant component of $G_{0}$, we may
partition the set of nodes into small parts such that each part induces a
connected graph. This is not much, but for noisy graphs it yields the
modularity that is larger than the modularity of the ground-truth partition.

######  Theorem 6.2.

Let $\gamma\in(2,3)$, $\delta\in\mathbb{N}$, $\zeta\in(0,\frac{1}{\gamma-1}]$,
and $\xi\in(0,1)$.

  * (a)

If $\xi\delta\geq 3$, then set $\alpha=1$.

  * (b)

If $\xi\delta<3$, then there exists a universal constant $\alpha>0$ which
depends on the parameters of the model but it is always separated from 0 (that
is, $\alpha$ is _not_ a function of $n$).

There exists a partition $\mathbf{C}$ of the set of nodes $V$ of $\mathcal{A}$
such that the following properties hold _w.h.p._

$\displaystyle q^{*}(\mathcal{A})\geq q(\mathbf{C})$ $\displaystyle\geq$
$\displaystyle(1+\mathcal{O}(n^{-(1-\zeta)/2}))\frac{2\alpha
n}{\textrm{vol}(V)}$ $\displaystyle=$ $\displaystyle(1+\mathcal{O}((\log
n)^{-1}))\ \frac{2\alpha}{d},\hskip 28.45274pt\text{ where
}d=\sum_{k=\delta}^{D}\ kq_{k}.$

(Note that $q_{i}$ is defined in (5.1).)

Recall that the modularity function of the ground-truth partition is _w.e.p._
asymptotic to $1-\xi$. The above theorem implies that if $\delta\geq 4$ and
the graph has a large level of noise, namely, $\xi\geq 3/\delta$ and
$\xi>1-2/d$, then _w.h.p._ the modularity function obtained from dissecting
the spanning tree of $G_{0}$ is larger! The same conclusion can be derived
when $\delta\leq 3$ by considering $\xi$ sufficiently close to one.

In order to prove the above theorem, we first investigate the degree
distribution of the background graph $G_{0}$.

######  Lemma 6.3.

Let $\gamma\in(2,3)$, $\delta\in\mathbb{N}$, $\zeta\in(0,\frac{1}{\gamma-1}]$,
and $\xi\in(0,1)$. For $k\in\mathbb{N}\cup\\{0\\}$, let $\hat{Y}_{k}$ be the
random variable counting the number of nodes in the background graph $G_{0}$
of $\mathcal{A}$ that are of degree $k$. For $k\in\mathbb{N}$ and
$\eta=\eta(n)$, let $\hat{Y}_{k}^{\eta}$ be the random variable counting the
number of nodes in the background graph $G_{0}$ of $\mathcal{A}$ that are of
degree at least $k$ but at most $(1+\eta)k$. Finally, for
$k\in\mathbb{N}\cup\\{0\\}$, let

$u_{k}:=\sum_{\begin{subarray}{c}i\in\mathbb{N}\\\ k-1<\xi i<k+1\\\ \delta\leq
i\leq\Delta\end{subarray}}\Big{(}1-|\xi i-k|\Big{)}q_{i},$

where $q_{i}$ is defined in (5.1).

The following properties hold _w.e.p._ :

  * (a)

If $\zeta\in(0,\frac{1}{\gamma})$, then for any $k\in\mathbb{N}$ such that
$\lfloor\xi\delta\rfloor\leq k\leq\xi\lfloor n^{\zeta}\rfloor$ we have

$\hat{Y}_{k}=(1+\mathcal{O}((\log n)^{-1}))\
nu_{k}=\Theta(nq_{k})=\Theta(nk^{-\gamma}).$ (17)

  * (b)

If $\zeta\in[\frac{1}{\gamma},\frac{1}{\gamma-1})$, then for any
$k\in\mathbb{N}$ such that $\lfloor\xi\delta\rfloor\leq k\leq
n^{1/\gamma}(\log n)^{-4/\gamma}\ll n^{\zeta}$ random variable $\hat{Y}_{k}$
satisfies (17), and for any $k\in\mathbb{N}$ such that $n^{1/\gamma}(\log
n)^{-4/\gamma}\leq k\leq\xi\lfloor n^{\zeta}\rfloor/(1+\eta)$ we have

$\hat{Y}_{k}^{\eta}=\Theta(n\eta kq_{k}),$ (18)

where

$\eta=\eta(k)=n^{-1}(\log n)^{4}k^{\gamma-1}=\mathcal{O}((\log n)^{-1})=o(1).$

  * (c)

If $\zeta=\frac{1}{\gamma-1}$, then for any $k\in\mathbb{N}$ such that
$\lfloor\xi\delta\rfloor\leq k\leq n^{1/\gamma}(\log n)^{-4/\gamma}\ll
n^{\zeta}$ random variable $\hat{Y}_{k}$ satisfies (17), and for any
$k\in\mathbb{N}$ such that $n^{1/\gamma}(\log n)^{-4/\gamma}\leq k\leq
n^{\zeta}(\log n)^{-5/(\gamma-1)}\ll n^{\zeta}$ random variable $Y_{k}^{\eta}$
satisfies (18). The number of nodes in $G_{0}$ of degree at least
$n^{\zeta}(\log n)^{-5/(\gamma-1)}$ is equal to $\Theta((\log n)^{5})$.

  * (d)

The minimum and the maximum degrees of $G_{0}$ are respectively
$\delta_{0}\geq\lfloor\xi\delta\rfloor$ and $\Delta_{0}\leq\lceil\xi
n^{\zeta}\rceil\leq n^{\zeta}$.

  * (e)

The volume of $G_{0}$ satisfies

$\textrm{vol}_{\,G_{0}}(V)=\sum_{k=\delta}^{D}k\hat{Y}_{k}=(1+\mathcal{O}((\log
n)^{-1}))\ \xi dn,\hskip 28.45274pt\text{ where }d:=\sum_{k=\delta}^{D}\
kq_{k}.$

###### Proof.

As in the statement of Lemma 5.2, let $Y_{k}$ and $Y_{k}^{\eta}$ be the
counterparts of $\hat{Y}_{k}$ and $\hat{Y}_{k}^{\eta}$ but defined for the
whole graph $\mathcal{A}$ instead of its subgraph, the background graph
$G_{0}$. By Lemma 5.2, _w.e.p._ the degree distribution of $\mathcal{A}$ is
well concentrated around its expectation.

Recall that a node of degree $i$ in $\mathcal{A}$ has degree $\lfloor\xi
i\rceil$ in $G_{0}$, where $\lfloor\xi i\rceil$ is a random variable equal to
$\lfloor\xi i\rfloor$ or $\lceil\xi i\rceil$, and the probabilities are tuned
such that the expectation is equal to $\xi i$—see definition (2). We
immediately get part (d) of the lemma (in fact, it holds deterministically,
not only _w.e.p._). Moreover, it implies that
$\mathbb{E}[\textrm{vol}_{\,G_{0}}(V)]=\xi\,\textrm{vol}_{\,\mathcal{A}}(V)$
and so, by Corollary 5.3 and Chernoff’s bound, we get part (e). More
importantly, in order for a node of degree $i$ in $\mathcal{A}$ to have a
chance to be of degree $k$ in $G_{0}$, we must have $k-1<\xi i<k+1$. If
$k-1<\xi i\leq k$, then its degree in $G_{0}$ is $k$ with probability $\xi
i-(k-1)=1-|\xi i-k|$. On the other hand, if $k<\xi i<k+1$, then the
probability is equal to $(k+1)-\xi i=1-|\xi i-k|$. Hence, we expect $1-|\xi
i-k|$ fraction of nodes of degree $i$ in $\mathcal{A}$ to be of degree $k$ in
$G_{0}$ and so

$\mathbb{E}\left[\hat{Y}_{k}\right]=\sum_{\begin{subarray}{c}i\in\mathbb{N}\\\
k-1<\xi i<k+1\\\ \delta\leq i\leq\Delta\end{subarray}}\Big{(}1-|\xi
i-k|\Big{)}\mathbb{E}\left[Y_{i}\right].$

Note that for any value of $k$, $\mathbb{E}[\hat{Y}_{k}]$ is the linear
combination of $\mathbb{E}\left[Y_{i}\right]$ with values of $i\in\mathbb{N}$
in the interval of length $2/\xi$. So there are at least $\lfloor
2/\xi\rfloor\geq 2$ terms in the above sum but no more than $2/\xi+1$. The
coefficient $1-|\xi i-k|$ of at least one of them is bounded away from zero so
we get that for the range considered in the statement of the lemma, we have
$\mathbb{E}[\hat{Y}_{k}]=\Theta(\mathbb{E}[Y_{k}])$. As the result, all
expectations tend to infinity fast enough, that is, are of order at least
$(\log n)^{4}$. Hence, Lemma 5.2 combined with the Chernoff’s bound, implies
the concentration for $\hat{Y}_{k}$ and $\hat{Y}_{k}^{\eta}$. The proof of the
lemma is finished. ∎

We will also need the following three results from [15], [20], and [37]. The
first two provide sufficient conditions for the graph with a given degree
sequence to be connected and, respectively, to have a giant component, that
is, a component of linear order. (Both papers provide also necessary
conditions but we do not need them so we only concentrate on the sufficient
ones.)

For any graphical degree sequence $\textbf{w}:=(w_{1},w_{2},\ldots,w_{n})$,
let $\mathcal{G}(\textbf{w})$ denote a random graph on the set of nodes $[n]$
selected uniformly at random from the family of simple graphs where node $i$
has degree $w_{i}$ for every $i\in[n]$. Recall that a degree sequence is
graphic if there exists at least one simple graph with such degree sequence.
Our background graph is a multi-graph ($\mathcal{P}(\textbf{w})$ instead of
$\mathcal{G}(\textbf{w})$) but the result below applies to both families of
graphs, and the condition of w being graphical is not needed for
$\mathcal{P}(\textbf{w})$. (In fact, as discussed in Subsection 4.2, in order
to prove results that hold _w.h.p._ for $\mathcal{G}(\textbf{w})$ one
typically proves them for $\mathcal{P}(\textbf{w})$ and then transfers them to
$\mathcal{G}(\textbf{w})$.)

The first lemma will be useful when the background graph $G_{0}$ has minimum
degree at least 3.

######  Lemma 6.4 ([15]).

Let $\textbf{w}:=(w_{1},w_{2},\ldots,w_{n})$ be any graphical sequence such
that $w_{1}\geq w_{2}\geq\ldots\geq w_{n}\geq 1$. Let

$\Delta=w_{1}\text{ \ \ (maximum degree)},\hskip
28.45274ptM=\sum_{i=1}^{n}w_{i}\text{ \ \ (volume)},\hskip
28.45274ptJ=\sum_{i=1}^{\Delta}w_{i},$

and for each $k$ let

$n_{k}=\sum_{i=1}^{n}\textbf{1}_{w_{i}=k}\text{ \ \ (the number of nodes of
degree $k$)}.$

If $n_{1}=o(\sqrt{M})$, $n_{2}=o(M)$, and $J=o(M)$, then _w.h.p._
$\mathcal{G}(\textbf{w})$ is connected.

The next lemma will be used when the background graph has minimum degree at
most 2.

######  Lemma 6.5 ([20]).

Let $\textbf{w}:=(w_{1},w_{2},\ldots,w_{n})$ be any graphical sequence such
that $w_{1}\leq w_{2}\leq\ldots\leq w_{n}$. Let

$\displaystyle J$ $\displaystyle=$
$\displaystyle\min\left(\left\\{j:j\in[n]\text{ and
}\sum_{i=1}^{j}w_{i}(w_{i}-2)>0\right\\}\cup\\{n\\}\right),$ $\displaystyle R$
$\displaystyle=$ $\displaystyle\sum_{i=J}^{n}d_{i},$ $\displaystyle M$
$\displaystyle=$ $\displaystyle\sum_{i\in[n]:d_{i}\neq 2}d_{i}.$

If $R\geq\varepsilon M$ for some $\varepsilon>0$, then there exists
$\alpha=\alpha(\varepsilon)$ such that _w.h.p._ $\mathcal{G}(\textbf{w})$ has
a component of order at least $\alpha n$.

The final observation that we will need, regardless of the minimum degree of
$G_{0}$, is that the spanning tree of the background graph (and so also a
spanning tree of $\mathcal{A}$) can be decomposed into small subtrees. This
can be relatively easily done by analyzing some greedy algorithm. We direct
the reader to [37] for more details.

######  Lemma 6.6 ([37]).

Suppose that $G=(V,E)$ is a connected graph on $n$ nodes. Then there exists a
partition $\mathbf{C}$ of $V$ such that

$q^{*}(G)\geq
q(\mathbf{C})\geq\frac{2n}{\textrm{vol}(V)}-3\sqrt{\frac{\Delta}{\textrm{vol}(V)}}-\frac{\Delta}{\textrm{vol}(V)},$

where $\Delta$ is the maximum degree of $G$ and $\textrm{vol}(V)$ is the
volume of $G$. In fact, the edge contribution is at least
$2n/\textrm{vol}(V)-2\sqrt{\Delta/\textrm{vol}(V)}$ and the degree tax is at
most $\sqrt{\Delta/\textrm{vol}(V)}+\Delta/\textrm{vol}(V)$.

Now, we are ready to combine all of these observations and prove Theorem 6.2.

###### Proof of Theorem 6.2.

Suppose first that $\xi\delta\geq 3$. We will use Lemma 6.4 to show that the
background graph $G_{0}$ is _w.h.p._ connected. By Lemma 6.3(d) we know that
the minimum degree of $G_{0}$ is at least $\lfloor\xi\delta\rfloor\geq 3$. Let
$\textbf{w}:=(w_{1},w_{2},\ldots,w_{n})$ be the degree sequence of $G_{0}$
such that $w_{1}\geq w_{2}\geq\ldots\geq w_{n}\geq 3$. The only property we
need to check before we may apply Lemma 6.4 is to verify that $J=o(M)$. Let
$\omega=\omega(n)$ be any function tending to infinity as $n\to\infty$. By
Lemma 6.3(a-c), _w.e.p._ the number of nodes of degree at least $\omega$ is
$\sum_{k\geq\omega}\Theta(nk^{-\gamma})=\Theta(n\omega^{-(\gamma-1)})=n^{1-o(1)}$,
much more than the maximum degree of $G_{0}$; trivially, $\Delta\leq
n^{\zeta}$. Hence, _w.e.p._

$J=\sum_{i=1}^{\Delta}w_{i}\leq\sum_{i,w_{i}\geq\omega}w_{i}=\sum_{k\geq\omega}\Theta(k\cdot
nk^{-\gamma})=\Theta(n\omega^{-(\gamma-2)})=o(n)=o(M),$

since $M=\textrm{vol}_{\,G_{0}}(V)=\Theta(n)$ by Lemma 6.3(e). Lemma 6.4
implies that _w.h.p._ $G_{0}$ is connected and so, trivially, $\mathcal{A}$ is
connected _w.h.p._ too.

Since $\Delta\leq n^{\zeta}$, we get immediately from Lemma 6.6 that there
exists a partition $\mathbf{C}$ of $V$ such that

$q(\mathbf{C})\geq(1+\mathcal{O}(n^{-(1-\zeta)/2}))\frac{2n}{\textrm{vol}_{\,\mathcal{A}}(V)}.$

The conclusion follows from Corollary 5.3 which implies that _w.e.p._
$\textrm{vol}_{\,\mathcal{A}}(V)=(1+\mathcal{O}((\log n)^{-1}))\ dn$. This
finishes part (a) of the theorem.

Suppose now that $\xi\delta<3$. Lemma 6.3(a-c) tells us that _w.e.p._ there
are linearly many nodes of degree $2$ so, unfortunately, Lemma 6.4 cannot be
applied. We will use Lemma 6.5 instead. This time we need to label nodes of
$G_{0}$ such that $w_{1}\leq w_{2}\leq\ldots\leq w_{n}$. Note that

$\sum_{i=1}^{j}w_{i}(w_{i}-2)=-n_{1}+\sum_{i=n_{1}+n_{2}+1}^{j}w_{i}(w_{i}-2)=-n_{1}+\sum_{i=n_{1}+n_{2}+1}^{j}w_{i}^{2}-2\sum_{i=n_{1}+n_{2}+1}^{j}w_{i},$

where $n_{1}$ and $n_{2}$ denote the number of nodes of degree one and two,
respectively. By Lemma 6.3(a-c), _w.e.p._ $n_{1}=(1+\mathcal{O}((\log
n)^{-1}))\ nu_{k}$. On the other hand, for any constant $K\geq 3$ we have

$\displaystyle\sum_{i\in[n]:3\leq w_{i}\leq K}w_{i}^{2}$ $\displaystyle=$
$\displaystyle\sum_{k=3}^{K}\Theta(k^{2}\cdot
nk^{-\gamma})=\Theta(nK^{3-\gamma})\ \ \text{ and}$
$\displaystyle\sum_{i\in[n]:3\leq w_{i}\leq K}w_{i}$ $\displaystyle=$
$\displaystyle\sum_{k=3}^{K}\Theta(k\cdot nk^{-\gamma})=\Theta(n),$

where the constants hidden in the $\Theta(\cdot)$ notation depend on
parameters of the model but do not depend on $n$ nor $K$. Since the first sum
grows with $K$ and the second one does not, $\sum_{i=1}^{j}w_{i}(w_{i}-2)$
becomes positive when the sum is taken over nodes of degree at most $K$ for
some sufficiently large constant $K$. (Let us stress it again that $K$ is a
universal constant, possibly large, but _not_ a function of $n$.) We get that
$J\leq(1-\lambda)n$ for some $\lambda>0$ and so both $R$ and $M$ are of order
$n$. Since $R\geq\varepsilon M$ for some $\varepsilon>0$, Lemma 6.5 can be
applied and we get that _w.h.p._ $G_{0}$ has a component of order at least
$\alpha n$ for some constant $\alpha$ which only depends on $\varepsilon$.
(One may try to estimate $R$ and $M$ better, which would give some bound for
$\varepsilon$ but Lemma 6.5 does not provide an explicit function
$\alpha=\alpha(\varepsilon)$ anyway so there is no point to do it.)

As before, it is enough to apply Lemma 6.6 but this time to the giant
component of $G_{0}=(V,E)$, graph $G^{\prime}_{0}=(V^{\prime},E^{\prime})$,
instead of $G_{0}$. By Corollary 5.3, _w.e.p._
$\textrm{vol}_{\,G_{0}}(V^{\prime})=\Theta(n)=\Theta(\textrm{vol}_{\,\mathcal{A}}(V))$
(note that since $G_{0}$ is connected,
$\textrm{vol}_{\,G_{0}}(V^{\prime})\geq|V^{\prime}|\geq\alpha n$). By Lemma
6.6, there exists a partition $\mathbf{C}^{\prime}$ of $V^{\prime}$ such that
the corresponding edge contribution for the giant component in $G_{0}$ is at
least $(1+\mathcal{O}(n^{-(1-\zeta)/2}))2\alpha
n/\textrm{vol}_{\,G_{0}}(V^{\prime})$, that is, the number of edges within one
of the parts is at least $(1+\mathcal{O}(n^{-(1-\zeta)/2}))\alpha n$. On the
other hand, the degree tax is $\mathcal{O}(n^{-(1-\zeta)/2})$.

Let $\mathbf{C}$ be a partition of $V$ obtained by extending the partition
$\mathbf{C}^{\prime}$ of $V^{\prime}\subseteq V$ by adding a trivial partition
of $V\setminus V^{\prime}$ consisting of parts of size one (singletons). Since
partition $\mathbf{C}$ captures exactly the same edges within some of its
parts as partition $\mathbf{C}^{\prime}$, the corresponding edge contribution
for $\mathcal{A}$ is $(1+\mathcal{O}(n^{-(1-\zeta)/2}))2\alpha
n/\textrm{vol}_{\,\mathcal{A}}(V)$. On the other hand, since _w.e.p._
$\textrm{vol}_{\,G_{0}}(V^{\prime})=\Theta(\textrm{vol}_{\,\mathcal{A}}(V))$,
the contribution to the degree tax for $\mathcal{A}$ from parts in partition
$\mathbf{C}^{\prime}$ is still $\mathcal{O}(n^{-(1-\zeta)/2})$. The
contribution to the degree tax for $\mathcal{A}$ from singletons is clearly

$\displaystyle\sum_{i\in V\setminus
V^{\prime}}\left(\frac{w_{i}}{\textrm{vol}_{\,\mathcal{A}}(V)}\right)^{2}$
$\displaystyle\leq$
$\displaystyle\frac{\Delta}{\textrm{vol}_{\,\mathcal{A}}(V)^{2}}\sum_{i\in
V\setminus
V^{\prime}}w_{i}\leq\frac{\Delta}{\textrm{vol}_{\,\mathcal{A}}(V)^{2}}\sum_{i\in
V}w_{i}=\frac{\Delta}{\textrm{vol}_{\,\mathcal{A}}(V)}$ $\displaystyle=$
$\displaystyle\mathcal{O}(n^{-(1-\zeta)})=\mathcal{O}(n^{-(1-\zeta)/2}).$

We get that _w.h.p._

$q(\mathbf{C})\geq(1+\mathcal{O}(n^{-(1-\zeta)/2}))\frac{2\alpha
n}{\textrm{vol}(V)},$

which finishes the proof of the theorem. ∎

#### Low Level of Noise

This time we will investigate graphs with a low level of noise, that is, with
$\xi$ close to zero. Let us fix a value of $\delta\in\mathbb{N}$ such that
$\delta\geq 100$. For any $a\in\mathbb{N}$ and
$b\in\mathbb{N}\setminus\\{1,2\\}$ such that $ab<\delta$, let

$c(a,b):=\frac{b-2\sqrt{b-1}}{2b}\,\frac{ab}{ab+b-1}-\frac{b-1}{ab+b-1}-0.011.$
(19)

Let

$\xi_{0}(\delta):=\max_{a\in\mathbb{N},b\in\mathbb{N}\setminus\\{1,2\\},ab<\delta}\min\left(1-\frac{ab}{\delta},\frac{c(a,b)}{4},\frac{1}{20}\right).$
(20)

It is clear that $\xi_{0}(\delta)$ is a non-decreasing function of $\delta$.
Moreover, $\xi_{0}(100)\approx 0.0217$ (the maximum is achieved for $a=8$ and
$b=12$), and $\xi_{0}(\delta)=1/20$ for $\delta\geq 340$.

Our first result says that ABCD graph $\mathcal{A}$ with minimum degree
$\delta\geq 100$ and $\xi\in(0,\xi_{0}(\delta))$ has _w.h.p._ the maximum
modularity $q^{*}(\mathcal{A})$ asymptotically equal to the modularity
function on the ground-truth.

######  Theorem 6.7.

Let $\delta\in\mathbb{N}$ such that $\delta\geq 100$ and
$0<\xi<\xi_{0}(\delta)$, where $\xi_{0}(\delta)$ is defined in (20). Let
$\mathbf{C}=\\{C_{1},C_{2},\ldots,C_{\ell}\\}$ be the ground-truth partition
of the set of nodes of $\mathcal{A}$. Then, _w.h.p._

$q^{*}(\mathcal{A})\sim q(\mathbf{C})\sim 1-\xi.$

The lower bound of $100$ for $\delta$ as well as the constants
$\xi_{0}(\delta)$ are not tuned for the strongest result. Since the proof
technique we use will not allow us to close the gap anyway, we aimed for a
simple argument that works for large enough $\delta$ and relatively simple
constants. Having said that, the above property is not true for $\delta=1$;
that is, if $\mathcal{A}$ has minimum degree $\delta=1$, then one may find a
partition of the nodes of $\mathcal{A}$ that yields larger modularity than the
one associated with the ground-truth.

######  Theorem 6.8.

Fix $\delta=1$ and let $0<\xi<1$. Let
$\mathbf{C}=\\{C_{1},C_{2},\ldots,C_{\ell}\\}$ be the ground-truth partition
of the set of nodes of $\mathcal{A}$. Then, _w.e.p._

$\displaystyle q^{*}(\mathcal{A})$ $\displaystyle\geq$
$\displaystyle(1+\mathcal{O}((\log n)^{-(\gamma-2)}))\,\left((1-\xi)+\frac{\xi
q_{1}}{d}\Big{(}2-\frac{q_{1}}{d}\Big{)}\right)$ $\displaystyle>$
$\displaystyle(1+\mathcal{O}((\log n)^{-(\gamma-2)}))\,(1-\xi)=q(\mathbf{C}),$

where $q_{k}$ is defined in (5.1) and $d=\sum_{k=\delta}^{D}\ kq_{k}$.

The rest of this subsection is devoted to proving the above theorems. Recall
that our ground-truth communities as well the background graph are random
multi-graphs $\mathcal{P}(\textbf{w})$ on $n^{\prime}$ nodes with a given
degree sequence $\textbf{w}:=(w_{1},w_{2},\ldots,w_{n^{\prime}})$ generated by
the _configuration model_ —see Subsection 2.3.5 for more details. In order to
derive some useful expansion properties of $\mathcal{P}(\textbf{w})$, we need
to couple $\mathcal{P}(\textbf{w})$ with $\mathcal{P}_{n^{\prime\prime},b}$,
random $b$-regular multi-graph on $n^{\prime\prime}$ nodes, for some integer
$b\geq 3$. Note that not only $\mathcal{P}(\textbf{w})$ but also
$\mathcal{P}_{n^{\prime\prime},b}$ is generated by the configuration model. In
particular, both of them are defined on the set of points that are eventually
contracted to form nodes. In what follows, we establish a relationship between
points used to generate both of them.

Coupling Between $\mathcal{P}(\textbf{w})$ and
$\mathcal{P}_{n^{\prime\prime},b}$: Let us fix $a\in\mathbb{N}$ and
$b\in\mathbb{N}\setminus\\{1,2\\}$ such that $ab\leq(1-\xi)\delta$, where
$\xi\in(0,1)$ and $\delta\geq 4$ are the parameters of the ABCD model
$\mathcal{A}$. Note that the minimum degree of each community graph $G_{i}$ is
$\lfloor(1-\xi)\delta\rfloor$ so $ab$ is at most the minimum degree of each
$G_{i}$.

Consider any random multi-graphs $\mathcal{P}(\textbf{w})$ on $n^{\prime}$
nodes with a given degree sequence
$\textbf{w}:=(w_{1},w_{2},\ldots,w_{n^{\prime}})$ and the minimum degree at
most $(1-\xi)\delta$. Let $W=\sum_{i=1}^{n^{\prime}}w_{i}$ be the volume of
$\mathcal{P}(\textbf{w})$ which is equal to the number of points in the
corresponding configuration model, as it was defined in Subsection 2.3.5.
Recall that the model guarantees that $W$ is even. Our goal is to couple
$\mathcal{P}(\textbf{w})$ and $\mathcal{P}_{n^{\prime\prime},b}$ such that
they use, if possible, the same set of points. If $W$ is divisible by $b$,
then we have the right number of points to create a random $b$-regular graph
on $n^{\prime\prime}=W/b$ nodes. Suppose then that $W$ is congruent to $j$
(mod $b$) for some $j\in[b-1]$. If $b-j$ is even, then we add $b-j$
_additional_ points; otherwise, the number of additional points is equal to
$2b-j$. Note that if $b$ is even, then $j$ has to be even as $W$ is even. So
if $b-j$ is odd, then $b$ must be odd and so $2b-j$ is even. Hence, regardless
whether $b-j$ is even or not, we add an even number of additional points which
will be important for the argument below to hold. This time, a random
$b$-regular graph will have a few more points than $\mathcal{P}(\textbf{w})$
but, as before, $W$ points will be shared by both models.

Recall that in the configuration model, points are partitioned into buckets
that are eventually contracted to form nodes. In $\mathcal{P}(\textbf{w})$,
there are $n^{\prime}$ buckets, $i$th bucket (corresponding to the $i$th node)
consists of $w_{i}$ points for a total of $W$ points. In
$\mathcal{P}_{n^{\prime\prime},b}$, there are $n^{\prime\prime}$ buckets (that
we will call _auxiliary buckets_), each consisting of $b$ points for a total
of $bn^{\prime\prime}\geq W$ points (a potential discrepancy is taken care of
additional points). Before we expose any edges, we need to assign each of the
regular $W$ points to buckets in $\mathcal{P}(\textbf{w})$ and to auxiliary
buckets in $\mathcal{P}_{n^{\prime\prime},b}$; additional points will only be
assigned to auxiliary buckets in $\mathcal{P}_{n^{\prime\prime},b}$.

First, we arbitrarily place $n^{\prime}$ buckets associated with
$\mathcal{P}(\textbf{w})$ on $W$ regular points. Then, for each
$i\in[n^{\prime}]$, the $i$th bucket in $\mathcal{P}(\textbf{w})$ consisting
of $w_{i}$ points is arbitrarily partitioned into sets of points of size $b$
and, possibly, one set of at most $b-1$ points. By construction, there are at
least $a$ sets of points of size $b$ that become buckets in
$\mathcal{P}_{n^{\prime\prime},b}$ that we will call _internal auxiliary
buckets_. The remaining points (including additional points if $W$ is not
divisible by $b$) are arbitrarily partitioned into $b$-element _external
auxiliary buckets_ in $\mathcal{P}_{n^{\prime\prime},b}$. Note that this is
possible as, by construction, $W$ plus the number of additional points is
divisible by $b$. As mentioned earlier, the original buckets will be used to
generate $\mathcal{P}(\textbf{w})$ and the auxiliary buckets will correspond
to random $b$-regular graph generated by $\mathcal{P}_{n^{\prime\prime},b}$.

It is time to start exposing edges, that is, start randomly matching points!
One of the advantages of using the pairing model is that the pairs may be
chosen sequentially, at each step choosing a point using any rule (possibly
randomized) that depends only on the pairs so far chosen and pairing it with a
point chosen uniformly at random over the remaining (unchosen) points. We
start with exposing additional points (if we have them), one by one. Note
that, during this initial phase, it might happen that two additional points
are paired together. (This happens with probability $\mathcal{O}(1/n)=o(1)$ as
there are $\mathcal{O}(1)$ additional points, so we could announce that the
coupling fails and deal with such rare situations in the proof of the theorem
differently. However, the coupling can be established even if this rare
situation happens.) Suppose that $r$ additional points are matched with not
additional ones: for each $i\in[r]$, additional point $p_{i}$ is matched with
point $q_{i}$. Recall that there are even number of additional points. So,
even if an even number of them are matched with other additional points, the
number of pairs $p_{i}q_{i}$ is even (that is, $r$ is even). Pairs
$p_{i}q_{i}$ ($i\in[r]$) will be present in $\mathcal{P}_{n^{\prime\prime},b}$
but $\mathcal{P}(\textbf{w})$ will consist of pairs $q_{2i-1}q_{2i}$ instead
($i\in[r/2]$). Note that the sequence of points $q_{i}$ ($i\in[r]$) is a
sequence of $r$ points selected uniformly at random from the set of non-
repeating sequences of points from $\mathcal{P}(\textbf{w})$ of that length.
Hence, the two corresponding pairings are valid partial random pairings of
$\mathcal{P}_{n^{\prime\prime},b}$ and, respectively,
$\mathcal{P}(\textbf{w})$. We continue pairing the remaining points, keeping
the obtained pairs in both models. This finishes the coupling.

Remark: Let us summarize the important observations. The coupling between
$\mathcal{P}(\textbf{w})$ and $\mathcal{P}_{n^{\prime\prime},b}$, despite the
fact that the number of points associated with these models might be
different, has the following properties: a) $\mathcal{P}(\textbf{w})$ and
$\mathcal{P}_{n^{\prime\prime},b}$ are perfect configuration models with their
respected fixed degree distributions, and b) almost all pairs of points are
coupled; the only discrepancy occurs with pairs associated with nodes in
$\mathcal{P}_{n^{\prime\prime},b}$ containing additional points and their
neighbours ($\mathcal{O}(1)$ nodes in $\mathcal{P}_{n^{\prime\prime},b}$ and
so also $\mathcal{O}(1)$ nodes in $\mathcal{P}(\textbf{w})$).

Now, we are ready to prove the first theorem, Theorem 6.7.

###### Proof of Theorem 6.7.

The behaviour of some nodes might be challenging to predict. For example,
nodes that belong to a community of constant size may (with positive
probability) be partitioned into two parts with no edges between the parts.
Such small communities might end up in different parts of the optimal
partition yielding the maximum modularity $q^{*}(\mathcal{A})$ of
$\mathcal{A}$. Fortunately, _w.h.p._ the number of problematic nodes will be
small and so their contribution to the modularity function will be negligible.

We will use the terminology introduced in Lemma 5.6. In particular, we will
call community $C_{i}$ very large if $|C_{i}|\geq n^{\zeta}(\log n)^{4}$, and
$F$ is the union of communities that are not very large. Each community that
is not very large will be called _problematic_ and, as a result, all nodes of
$F$ will be called _problematic_. By Lemma 5.6, _w.e.p._
$\textrm{vol}(F)=\mathcal{O}(n\,(\log n)^{-2})=o(n)$. On the other hand, by
Corollary 5.3, _w.e.p._ $\textrm{vol}(V)=(1+\mathcal{O}((\log n)^{-1}))\ dn$,
where $d=\sum_{k=\delta}^{D}\ kq_{k}$. Hence, _w.e.p._
$\textrm{vol}(F)=o(\textrm{vol}(V))$. Since we aim for a statement that hols
_w.h.p._ , we may assume that this property holds.

Let $\delta\geq 100$ be the minimum degree of $\mathcal{A}$. Let
$a\in\mathbb{N},b\in\mathbb{N}\setminus\\{1,2\\}$ be the constants that yield
$\xi_{0}(\delta)>0$ in (20), and $c=c(a,b)>0$ is defined as in (19). We couple
community graphs $G_{i}$ of very large communities $C_{i}$ that are generated
according to the model $\mathcal{P}(\textbf{w})$ with the model
$\mathcal{P}_{n^{\prime\prime},b}$. Note that, since $\xi<\xi_{0}(\delta)\leq
1-ab/\delta$, we have $(1-\xi)\delta\geq ab$ and so the coupling may be
applied. Let $\lambda_{i}$ be the largest absolute value of an eigenvalue
other than $\lambda=b$ of the adjacency matrix of the random $b$-regular graph
$\mathcal{P}_{n^{\prime\prime},b}$ associated with $G_{i}$. (See Section 4.2
for more on that.) If $\lambda_{i}>2\sqrt{b-1}+10^{-5}$, then we call the
associated community $C_{i}$ and all of its nodes _problematic_. By Lemma 4.2,
_w.h.p._ each very large community is not problematic so the expected volume
of nodes that become problematic is $o(n)$. By the first moment method, we
conclude that _w.h.p._ the number of problematic nodes is $o(n)$. Very large
communities $G_{i}$ that are _not_ problematic are coupled with $b$-regular
graphs that are good expanders ($\lambda_{i}\leq 2\sqrt{b-1}+10^{-5}$).
However, as remarked above, there could be some constant number of nodes in
$G_{i}$ that are incident with edges in $\mathcal{P}(\textbf{w})$ that are not
present in $\mathcal{P}_{n^{\prime\prime},b}$. We will also call these nodes
_problematic_. Since the maximum degree is at most $n^{\zeta}$ and each very
large community has at least $n^{\zeta}(\log n)^{4}$ nodes, the volume
associated with new problematic nodes is $\mathcal{O}(n/(\log n)^{4})=o(n)$.

We call a partition $\mathbf{P}$ of the set of nodes of $\mathcal{A}$ _nice_
if the following two properties hold: a) all problematic communities (not very
large or bad expanders) form a separate part in $\mathbf{P}$, and b)
problematic nodes from non-problematic communities belong to a largest part of
the partition of its own community that is induced by $\mathbf{P}$ (if there
are at least two communities that are largest, then all problematic nodes
belong to one of them). Let $\mathbf{P}^{*}$ be a partition that yields
$q^{*}(\mathcal{A})$. One can move the problematic nodes around, if needed, to
transform $\mathbf{P}^{*}$ into a nice partition $\mathbf{P}$. Since the
volume of the problematic nodes is $o(\textrm{vol}(V))$, both the edge
contribution and the degree tax change by $o(1)$, and so we get that
$q(\mathbf{P})=q(\mathbf{P}^{*})+o(1)$. Hence, it is enough to show that the
maximum modularity over the family of nice partitions is $1-\xi+o(1)$.

Let $\mathbf{P}$ be a nice partition that yields the largest modularity over
this family of partitions. We will show that each non-problematic community is
contained in one part of $\mathbf{P}$. For a contradiction, suppose that
partition $\mathbf{P}$ partitions a non-problematic community of volume $W$
into $j\geq 2$ parts $U_{i}$, $i\in[j]$. Let $W_{i}=\textrm{vol}(U_{i})$.
Without loss of generality, we may assume that $W_{1}\geq W_{2}\geq\ldots\geq
W_{j}$ and that all problematic nodes, if present, belong to $U_{1}$. Consider
any part $U_{i}$ ($i\geq 2$). Since $U_{1}$ has a largest volume, $W_{i}\leq
W/2$. Our goal is to estimate $E(U_{i},V\setminus U_{i})$, the number of edges
going from $U_{i}$ to its complement. To that end, we will use the coupling
with $b$-regular graphs. Let $U^{\prime}_{i}$ be a subset of nodes of the
coupled $b$-regular graph $\mathcal{P}_{n^{\prime\prime},b}$ that are
associated with internal auxiliary buckets, and let $W^{\prime}_{i}$ be its
volume. (In order to make it easier for the reader to distinguish sets of
nodes in the original graph $\mathcal{P}(\textbf{w})$ from those in the
coupled graph $\mathcal{P}_{n^{\prime\prime},b}$, we will use $U_{i}$ and,
respectively, $U^{\prime}_{i}$ as well as $W_{i}$ and $W^{\prime}_{i}$.)
Trivially, $W^{\prime}_{i}\leq W_{i}$. Moreover, since at least $a$ internal
auxiliary buckets of $b$ points (nodes in $\mathcal{P}_{n^{\prime\prime},b}$)
are contained in each node in $\mathcal{P}(\textbf{w})$,

$W^{\prime}_{i}\geq\frac{ab}{ab+b-1}W_{i}.$

(The extreme case corresponds to a node in $\mathcal{P}(\textbf{w})$ of degree
$ab+b-1$ which is associated with $ab$ internal buckets.) Since
$\mathcal{P}_{n^{\prime\prime},b}$ is a good expander, it follows from (7)
that the number of edges from $U^{\prime}_{i}$ to its complement satisfies the
following inequality:

$\displaystyle E(U^{\prime}_{i},V\setminus U^{\prime}_{i})$
$\displaystyle\geq$ $\displaystyle(b-\lambda)\frac{|U^{\prime}_{i}||V\setminus
U^{\prime}_{i}|}{n^{\prime\prime}}$ $\displaystyle=$
$\displaystyle(b-\lambda+o(1))\frac{(W^{\prime}_{i}/b)((W-W^{\prime}_{i})/b)}{W/b}$
$\displaystyle\geq$
$\displaystyle\frac{b-\lambda+o(1)}{b}\frac{ab}{ab+b-1}\,W_{i}\,\frac{W-W^{\prime}_{i}}{W}$
$\displaystyle\geq$
$\displaystyle\frac{b-\lambda+o(1)}{2b}\frac{ab}{ab+b-1}\,W_{i}.$

Note that not all of these edges go from $U_{i}$ to its complement (in
$\mathcal{P}(\textbf{w})$) but clearly at most $W_{i}-W^{\prime}_{i}$ of them
can stay within $U_{i}$ as there are $W_{i}-W^{\prime}_{i}$ points in $U_{i}$
that are assigned to external auxiliary buckets. Since $\lambda\leq
2\sqrt{b-1}+10^{-5}$, we get that

$\displaystyle E(U_{i},V\setminus U_{i})$ $\displaystyle\geq$ $\displaystyle
E(U^{\prime}_{i},V\setminus U^{\prime}_{i})-(W_{i}-W^{\prime}_{i})$
$\displaystyle\geq$
$\displaystyle\frac{b-\lambda+o(1)}{2b}\frac{ab}{ab+b-1}\,W_{i}-\frac{b-1}{ab+b-1}\,W_{i}$
$\displaystyle\geq$
$\displaystyle\left(\frac{b-2\sqrt{b-1}-10^{-5}+o(1)}{2b}\frac{ab}{ab+b-1}-\frac{b-1}{ab+b-1}\right)W_{i}$
$\displaystyle\geq$ $\displaystyle\Big{(}c-10^{-5}+0.011\Big{)}W_{i},$

where $c=c(a,b)$ is defined in (19).

Now, we will modify the partition $\mathbf{P}$ slightly, keeping the modified
partition nice, and show that it improves its modularity which will give us
the desired contradiction. We need to independently consider two cases.
Suppose first that $U_{1}$ belongs to a part $P_{1}$ of $\mathbf{P}$ of volume
$\textrm{vol}(P_{1})\leq\frac{c-1.1\xi}{2}\,\textrm{vol}(V)$. We move all
nodes in parts $U_{i}$, $i\geq 2$, to $P_{1}$. That operation puts together
all edges of the non-problematic community we consider within one part but
some edges of the background graph might get lost. To estimate the number of
background edges that might get removed from some part of partition
$\mathbf{P}$, note that the ratio between the background degree and the
community degree of a node of degree $w\geq\delta\geq 100$ is at most

$\frac{\lceil\xi w\rceil}{\lfloor(1-\xi)w\rfloor}\leq\frac{\xi
w+1}{(1-\xi)w-1}\leq\frac{\xi\delta+1}{(1-\xi)\delta-1}\leq\frac{100\xi+1}{94}\leq
1.07\xi+0.0107,$

since $\xi\leq 1/20$. Hence, the edge contribution increases by at least

$\Big{(}c-10^{-5}+0.011\Big{)}\sum_{i=2}^{j}\frac{W_{i}}{\textrm{vol}(V)}-\Big{(}1.07\xi+0.0107\Big{)}\sum_{i=2}^{j}\frac{W_{i}}{\textrm{vol}(V)}\geq\Big{(}c-1.07\xi\Big{)}\sum_{i=2}^{j}\frac{W_{i}}{\textrm{vol}(V)}.$

On the other hand, the degree tax increases by at most

$\displaystyle\frac{(\textrm{vol}(P_{1})+\sum_{i=2}^{j}W_{i})^{2}}{\textrm{vol}(V)^{2}}-\frac{\textrm{vol}(P_{1})^{2}}{\textrm{vol}(V)^{2}}$
$\displaystyle=$
$\displaystyle\frac{2\,\textrm{vol}(P_{1})\sum_{i=2}^{j}W_{i}}{\textrm{vol}(V)^{2}}+\frac{\left(\sum_{i=2}^{j}W_{i}\right)^{2}}{\textrm{vol}(V)^{2}}$
$\displaystyle=$
$\displaystyle\frac{(2+o(1))\,\textrm{vol}(P_{1})\sum_{i=2}^{j}W_{i}}{\textrm{vol}(V)^{2}}$
$\displaystyle\leq$
$\displaystyle\Big{(}c-1.1\xi+o(1)\Big{)}\sum_{i=2}^{j}\frac{W_{i}}{\textrm{vol}(V)}.$

Since

$\Big{(}c-1.07\xi\Big{)}-\Big{(}c-1.1\xi+o(1)\Big{)}=0.03\xi+o(1)>0,$

the modification of $\mathbf{P}$ increases its modularity and we get a
contradiction that $\mathbf{P}$ maximizes the modularity over the family of
nice partitions.

Suppose now that $U_{1}$ belongs to a part $P_{1}$ of $\mathbf{P}$ of volume
$\textrm{vol}(P_{1})>\frac{c-1.1\xi}{2}\,\textrm{vol}(V)$. This time we move
all nodes in parts $U_{i}$, $i\geq 1$, and form an independent part. Since we
also disconnect $U_{1}$ from its part ($P_{1}$), the edge contribution
increases by at least

$\Big{(}c-1.07\xi\Big{)}\sum_{i=2}^{j}\frac{W_{i}}{\textrm{vol}(V)}-\Big{(}1.07\xi+0.0107\Big{)}\frac{W_{1}}{\textrm{vol}(V)}.$

The second term might potentially dominate the change so the edge contribution
might actually decrease. Trivially, it may decrease at most by the absolute
value of the second term above. Fortunately, disconnecting $U_{1}$ from a
large part decreases the degree tax substantially. Indeed, the degree tax
decreases by at least

$\displaystyle\frac{\textrm{vol}(P_{1})^{2}}{\textrm{vol}(V)^{2}}-\frac{(\textrm{vol}(P_{1})-W_{1})^{2}}{\textrm{vol}(V)^{2}}-\frac{(\sum_{i=1}^{j}W_{i})^{2}}{\textrm{vol}(V)^{2}}$
$\displaystyle=$
$\displaystyle\frac{(2+o(1))\,\textrm{vol}(P_{1})W_{1}}{\textrm{vol}(V)^{2}}$
$\displaystyle\geq$
$\displaystyle\Big{(}c-1.1\xi+o(1)\Big{)}\frac{W_{1}}{\textrm{vol}(V)}.$

Note that $c\geq 4\xi_{0}(\delta)\geq 4\xi_{0}(100)>0.08$. Since
$\xi<\xi_{0}(\delta)\leq c/4$, we get that

$\displaystyle\Big{(}c-1.1\xi+o(1)\Big{)}-\Big{(}1.07\xi+0.0107\Big{)}$
$\displaystyle=$ $\displaystyle c-2.17\xi-0.0107+o(1)$ $\displaystyle\geq$
$\displaystyle 0.4575c-0.0107+o(1)$ $\displaystyle=$ $\displaystyle
0.0366-0.0107+o(1)>0,$

and so the modification of $\mathbf{P}$ increases its modularity and we get a
contradiction too.

It follows that the nice partition $\mathbf{P}$ that yields the largest
modularity over this family of partitions has each non-problematic (very large
and good expander) community contained in one part of $\mathbf{P}$. It remains
to show that one cannot improve the modularity function by combining some non-
problematic communities together. We will use $q_{G_{0}}(\mathbf{P})$,
$e_{G_{0}}(A_{i})$, and $\textrm{vol}_{G_{0}}(A_{i})$ for counterparts of
$q(\mathbf{P})$, $e(A_{i})$, and $\textrm{vol}(A_{i})$ that are applied for
the background graph $G_{0}$ instead of the entire graph $\mathcal{A}$. We get
that

$\displaystyle q(\mathbf{P})$ $\displaystyle=$
$\displaystyle\sum_{A_{i}\in\mathbf{P}}\frac{e(A_{i})}{|E|}-\sum_{A_{i}\in\mathbf{P}}\left(\frac{\textrm{vol}(A_{i})}{\textrm{vol}(V)}\right)^{2}$
$\displaystyle=$
$\displaystyle\Big{(}1-\xi+o(1)\Big{)}+\sum_{A_{i}\in\mathbf{P}}\frac{e_{G_{0}}(A_{i})}{|E|}-\sum_{A_{i}\in\mathbf{P}}\left(\frac{\textrm{vol}(A_{i})}{\textrm{vol}(V)}\right)^{2}.$

By Lemma 5.6, _w.e.p._ the volume of each very large community $C$ satisfies
$\textrm{vol}_{G_{0}}(C)=\textrm{vol}(C)-\textrm{vol}_{c}(C)\sim\xi\,\textrm{vol}(C)$.
By Lemma 6.3(e), _w.e.p._ $\textrm{vol}_{G_{0}}(V)\sim\xi\,\textrm{vol}(V)$.
We get that _w.e.p._

$\displaystyle q(\mathbf{P})$ $\displaystyle\leq$
$\displaystyle\Big{(}1-\xi+o(1)\Big{)}+\Big{(}\xi+o(1)\Big{)}\sum_{A_{i}\in\mathbf{P}}\frac{e_{G_{0}}(A_{i})}{|E(G_{0})|}-(1+o(1))\sum_{A_{i}\in\mathbf{P}}\left(\frac{\textrm{vol}_{G_{0}}(A_{i})}{\textrm{vol}_{G_{0}}(V)}\right)^{2}$
$\displaystyle\leq$
$\displaystyle\Big{(}1-\xi+o(1)\Big{)}+\Big{(}1+o(1)\Big{)}\left(\sum_{A_{i}\in\mathbf{P}}\frac{e_{G_{0}}(A_{i})}{|E(G_{0})|}-\sum_{A_{i}\in\mathbf{P}}\left(\frac{\textrm{vol}_{G_{0}}(A_{i})}{\textrm{vol}_{G_{0}}(V)}\right)^{2}\right)$
$\displaystyle\leq$
$\displaystyle\Big{(}1-\xi+o(1)\Big{)}+\Big{(}1+o(1)\Big{)}q_{G_{0}}(\mathbf{P}).$

It remains to show that $q_{G_{0}}(\mathbf{P})=o(1)$. We may contract each
non-problematic community into a single node, since they must belong to one
part. Similarly, we contract all problematic communities into a single node.
Now, we may couple the entire background graph that is generated as the
pairing model $\mathcal{P}(\textbf{w})$ with
$\mathcal{P}_{n^{\prime\prime},d}$ with $a=1$ and $b=d$ for an arbitrarily
large integer $d$ (note that after contraction the minimum degree in
$\mathcal{P}(\textbf{w})$ tends to infinity as $n\to\infty$ so $ab=d$ is
certainly less than the minimum degree of $\mathcal{P}(\textbf{w})$). By Lemma
4.4 and Lemma 4.2 we get that _w.h.p._
$q^{*}(\mathcal{P}_{n^{\prime\prime},d})=\mathcal{O}(1/\sqrt{d})$ and so
_w.h.p._ $q^{*}(\mathcal{P}(\textbf{w}))=\mathcal{O}(1/\sqrt{d})$. Since $d$
can be made arbitrarily large, we conclude that $q_{G_{0}}(\mathbf{P})=o(1)$
and the proof of the theorem is finished. ∎

Now, let us move to the proof of the second theorem. Since the proof is rather
straightforward and the reader is already warmed-up, we only sketch it.

###### Proof of Theorem 6.8.

Suppose that $\delta=1$. By Lemma 5.2, _w.e.p._ there are
$(1+\mathcal{O}((\log n)^{-1}))\ q_{1}n$ nodes of degree 1 in $\mathcal{A}$,
where $q_{k}$ is defined in (5.1). It follows easily from Chernoff’s bound
that _w.e.p._ $(1+\mathcal{O}((\log n)^{-1}))\ \xi q_{1}n$ of them have degree
1 in the background graph (and so degree 0 in their own community graph)—see
also Lemma 6.3. We will call such nodes _lucky_.

Consider the ground-truth partition
$\mathbf{C}=\\{C_{1},C_{2},\ldots,C_{\ell}\\}$ of the set of nodes of
$\mathcal{A}$. It follows from Theorem 6.1 that _w.e.p._
$q(\mathbf{C})=(1+\mathcal{O}((\log n)^{-(\gamma-2)}))\,(1-\xi)$. We will
modify it to improve slightly the modularity function. All lucky nodes will be
moved to the community of their neighbours. Note that two lucky nodes could be
neighbours of each other, that is, they may form an isolated edge in
$\mathcal{A}$. Such lucky nodes will be called _super-lucky_ and we
arbitrarily assign them to a community of one of them. In fact, edges formed
by super-lucky nodes should form independent parts to increase the modularity
function but the improvement would be negligible so there is no point to do
it. By Lemma 6.3(e), the volume of the background graph is well concentrated
around its mean and so the probability that a lucky node is super-lucky is
equal to $(1+\mathcal{O}((\log n)^{-1}))\ (\xi q_{1}n)/(\xi dn)$, where
$d=\sum_{k=\delta}^{D}\ kq_{k}$. Hence, the expected number of super-lucky
nodes is equal to

$(1+\mathcal{O}((\log n)^{-1}))\ \xi q_{1}n\,\frac{\xi q_{1}n}{\xi
dn}=(1+\mathcal{O}((\log n)^{-1}))\,\frac{\xi q_{1}^{2}}{d}\,n,$

and so the expected number of the associated isolated edges is half of it. On
the other hand the expected number of lucky nodes that are not super-lucky is
$(1+\mathcal{O}((\log n)^{-1}))\,\xi q_{1}(1-q_{1}/d)\,n$. The concentration
follows easily from Chernoff’s bound. Since all edges from the community
graphs still remain in some part, _w.e.p._ this modification increases the
edge contribution by

$\displaystyle(1+\mathcal{O}((\log n)^{-1}))\,\Big{(}\frac{\xi
q_{1}^{2}}{2d}+\xi q_{1}\Big{(}1-\frac{q_{1}}{d}\Big{)}\Big{)}\,\frac{n}{|E|}$
$\displaystyle=$ $\displaystyle(1+\mathcal{O}((\log n)^{-1}))\,\Big{(}\xi
q_{1}\Big{(}1-\frac{q_{1}}{2d}\Big{)}\Big{)}\,\frac{n}{dn/2}$ $\displaystyle=$
$\displaystyle(1+\mathcal{O}((\log n)^{-1}))\,\frac{\xi
q_{1}}{d}\Big{(}2-\frac{q_{1}}{d}\Big{)},$

as $|E|=\textrm{vol}(V)/2=(1+\mathcal{O}((\log n)^{-1}))\,dn/2$ by Corollary
5.3.

Since each part may at most double its volume (deterministically), the degree
tax after the modification is of the same order as before the modification,
that is, it is $\mathcal{O}((\log n)^{-2})$. This finishes the proof of the
theorem. ∎

#### Simulation Corner

Theorem 6.2 shows that the maximum modularity is larger than the modularity of
the ground-truth partition, provided that $\mathcal{A}$ is very noisy. On the
other hand, Theorem 6.7 shows the opposite: the maximum modularity is
asymptotic to the modularity of the ground-truth partition, provided
$\mathcal{A}$ has low level of noise. For some technical reason, we assumed in
that theorem that $\delta$, the minimum degree of $\mathcal{A}$, is large
enough but the same property should hold for much smaller values of $\delta$.

In order to investigate this, for each value of $\xi=(0.1)i$, $i\in[9]$, we
independently generated 30 graphs on $n=1{,}000$ nodes and $n=1{,}000{,}000$
nodes and with the same parameters as in the previous experiment:
$\gamma=2.5$, $\delta=5$, $\zeta=1/2<2/3=1/(\gamma-1)$ (that is,
$D=\sqrt{n}$), $\beta=1.5$, $s=50$, and $\tau=3/4$ (that is, $S=n^{3/4}$). In
order to approximate the maximum modularity, we used the ensemble clustering
algorithm for unweighted graphs (ECG) which is based on the Louvain algorithm
[7] and the concept of consensus clustering [36], and is shown to have good
stability.

The experiments coincide with theoretical predictions, despite the fact that
$\delta=5$ in the experimental graphs is much smaller than the lower bound of
100 assumed in the corresponding theorem. For small values of $\xi$, the
modularity found by ECG is very close to $1-\xi$, an asymptotic prediction for
the modularity of the ground-truth. On the other hand, if $\xi$ is large, then
the partition found by the algorithm is of better quality than the ground-
truth partition—see Figure 8.