# Constraints on Meso-Scale Structure in Complex Networks

Rudy Arthur<EMAIL_ADDRESS>University of Exeter, Department of
Computer Science,
Stocker Rd, Exeter EX4 4PY

###### Abstract

A key topic in network science is the detection of intermediate or meso-scale
structures. Community, core-periphery, disassortative and other partitions
allow us to understand the organisation and function of large networks. In
this work we study under what conditions certain common meso-scale structures
are detectable using the idea of block modularity. We find that the
configuration model imposes strong restrictions on core-periphery and related
structures in directed networks. We derive inequalities expressing when such
structures can be detected under the configuration model. Nestedness is
closely related to core-periphery and is similarly restricted to only be
detectable under certain conditions. We show that these conditions are a
generalisation of the resolution limit to structures other than assortative
communities. We show how block modularity is related to the degree corrected
Stochastic Block Model and that optimisation of one can be made equivalent to
the other in general. Finally, we discuss these issues in inferential versus
descriptive approaches to meso-scale structure detection.

Networks, Community Detection, Core Periphery, Stochastic Block Model

††preprint: APS/123-QED

##  I Introduction

An important topic in network science is the identification of intermediate or
meso-scale structure by partitioning the nodes of the network into non-
overlapping sets [1, 2]. The primary structure of interest has historically
been assortative communities [3, 4, 5, 6]. These are tightly connected groups
of nodes which split the network into a number of weakly connected modules.
Another meso-scale structures of interest is core-periphery [7, 8, 9, 10, 11,
12], consisting of a core set and a periphery set, where the core is densely
connected internally and to the periphery, while periphery nodes are
predominantly connected to core nodes. There are also disassortative
structures which have received somewhat less attention [13, 14, 15, 16, 17,
18], but represent the other side of community structure, dense connections
between groups and sparse connections within them.

Recent work [19, 20, 21] has sought to classify meso-scale structures which
partition the nodes of the network into non-overlapping sets. This means
structures like k-cores [22] and rich-clubs [23] are not considered. However,
when we have a hard partition the network’s adjacency matrix has an
approximate block structure. For small numbers of subsets (2 in [20] and 2,3,4
in [19]) it is feasible to enumerate all the possible blocks. [20, 21]
identify meso-scale structure based on the ratio of existing to possible links
within and between communities. [19] bases meso-scale structure detection on
the excess or deficit of links within or between blocks compared to a null
model. We will follow the latter approach in this work, which allows us to
study the assumptions required to determine if a network can have a particular
structure.

Building on [19], in [24] I defined a generalised notion of modularity called
_block modularity_. This extends the original modularity definition [25] in a
way that allows the evaluation of partition quality for a variety of meso-
scale structures other than assortative communities. Block modularity captures
the intuitively reasonable notion that, for us to declare that a meso-scale
structure is present there should be more links within or between the
corresponding blocks than a random network would have. A key point is that the
‘random network’ is one selected from a particular null model. While numerous
choices for a null model are possible: Erdős-Rènyi (ER), Stochastic Block
Model (SBM) [26] or others [27, 28], generally the configuration model [29] is
used.

A random network drawn from the configuration null is one with the same degree
sequence as the observed network. Degree distribution, along with correlations
and anti-correlations among node degrees have long been recognised as key
characteristics that explain many of the properties of complex networks [30,
31, 1]. Significant differences between the observed network and its
configuration model implies that there is structure in the network which
cannot be explained by the node degrees alone. This requirement of structure
beyond that implied by the degree sequence turns out to be quite rigid, and
imposes hard constraints on the types of meso-scale structures which are
possible. In particular [19] found that a partition of a network into one core
and one periphery set is not possible under the configuration null.

This work builds on and extends this result. First, in Section II we introduce
block modularity and extend it to work for directed networks. Section III
enumerates all possible $2\times 2$ block patterns for directed and undirected
networks. We then use block modularity to rederive the constraints found by
[19] in a somewhat simpler way, as well as extending those results to the
directed case. In Section IV we derive further restrictions on Core-Periphery
structure (as well as a directed network structure we refer to as Community-
Hierarchy) when these structures are part of larger networks. Section V
discusses nested networks [32] under the configuration model. In Section VI we
show how these restrictions are related to and generalise the resolution limit
[33]. Section VII considers another popular null model, the degree corrected
Stochastic Block Model (dc-SBM) [26]. We show how this is related to Block
Modularity and how structure detection with the dc-SBM differs from modularity
based approaches.

##  II Block Modularity

Modularity was introduced by Newman [25] to measure the quality of a partition
of a network into communities

$Q_{Newman}=\frac{1}{2E}\sum_{ij}\left(A_{ij}-P_{ij}\right)\delta(c(i),c(j))$
(1)

The sums are over all $N$ nodes of the network, $A$ is the adjacency matrix,
$2E=\sum_{ij}A_{ij}$ is twice the number of edges, $c(i)$ is a function which
returns the community label of the node $i$ and $P_{ij}$ is the expected
number of links between $i$ and $j$ in the null model. With the configuration
model as the null

$P_{ij}=\frac{k_{i}k_{j}}{2E}$

where $k_{i}=\sum_{j}A_{ij}$ is the degree of $i$. An Erdős-Rènyi (ER) null
model, which assumes a constant probability for every edge to exist (including
self edges) has

$P_{ij}=p=\frac{2E}{N^{2}}$

Another common null is the scaled configuration model [34]

$P_{ij}=\gamma\frac{k_{i}k_{j}}{2E}$

where $\gamma$ is an arbitrary parameter. We will primarily deal with the
configuration model and discuss the ER and scaled configuration model in
Appendix A. The stochastic block model (SBM) [35] is also often used to
investigate meso-scale structure, though in general not together with
modularity. We treat the SBM in Section VII.

Modularity can be rewritten in terms of the adjacency matrix of the network
induced by the partition. Define

$S_{ab}=\sum_{i\in a,j\in b}A_{ij}$

as the number of edges going between $a$ and $b$, or twice the number of edges
inside $a$ if $a=b$. Similarly for the null define,

$S_{ab}^{P}=\sum_{i\in a,j\in b}P_{ij}.$

In these terms, Equation 1 becomes

$Q_{Newman}=\frac{1}{2E}\sum_{a}\left(S_{aa}-S^{P}_{aa}\right)$ (2)

where the sum is over all $K$ sets in the partition. Written like this,
$Q_{Newman}$ is the sum over groups of the excess or deficit of edges in the
observed network compared to the number predicted by the null model. For the
configuration null

$Q_{Newman}=\frac{1}{2E}\sum_{a}^{K}\left(S_{aa}-\frac{T_{a}^{2}}{2E}\right)$

with

$T_{a}=\sum_{i\in a}k_{i}$

[24] introduced a natural generalisation of this function (see also [11]),
with

$Q_{ab}=S_{ab}-S^{P}_{ab}$

the _block modularity_ is defined as

$Q(B)=\frac{1}{2E}\sum_{ab}^{K}Q_{ab}B_{ab}$ (3)

with the _block matrix_ $B$ having entries equal to $\pm 1$. For the
configuration model,

$S^{P}_{ab}=\frac{T_{a}T_{b}}{2E}$

The target meso-scale structure is encoded in the block matrix $B$. For
example, if the matrix $B$ has 1s on on the diagonal and -1s elsewhere
$Q(B)=2Q_{Newman}$ and $Q(B)$ evaluates how well a partition groups the nodes
into assortative communities. However we are not limited to assortative
communities. For example, if

$B=\begin{pmatrix}1&1&-1&-1\\\ 1&-1&-1&-1\\\ -1&-1&1&1\\\
-1&-1&1&-1\end{pmatrix}$

then $Q(B)$ evaluates the quality of a partition of the nodes into a pair of
core-peripheries. [24] explores simultaneously optimising both the partition
$c(i)$ and the block pattern $B$, so that the meso-scale structure is
discovered from the data and in Section VII we will discuss an algorithm for
determining $B$. However, for a given target structure we don’t need to learn
$B$ from the data, we can simply choose $B$ to probe the network for the
structure of interest.

###  II.1 Directed networks

Block modularity can be extended straightforwardly to directed networks in
much the same way as modularity is extended in [36]. Let $A$ be the adjacency
matrix of a directed graph. Recall, in the directed case $A_{ij}\neq A_{ji}$.
With

$\displaystyle k^{(in)}_{j}=\sum_{i}A_{ij},\quad
k^{(out)}_{i}=\sum_{j}A_{ij},\quad E=\sum_{ij}A_{ij}$

Define

$Q_{\leftrightarrow}(B)=\frac{1}{E}\sum_{ab}^{K}Q_{ab}B_{ab}$ (4)

with $Q_{ab}$ and $B_{ab}$ as before, noting that in the directed case these
need not be symmetric. Using the directed configuration model as the null

$\displaystyle S^{P}_{ab}=\frac{T_{a}^{(out)}T_{b}^{(in)}}{E},\quad
T_{a}^{(out)}=\sum_{i\in a}k^{(out)}_{i},\quad T_{b}^{(in)}=\sum_{j\in
b}k^{(in)}_{j}$

##  III Allowed Block Patterns

All possible $2\times 2$ block matrices $B$ with entries $\pm 1$ are shown in
Figure 1 for the undirected and Figure 2 for the directed case, where a black
square is $+1$ and a white square $-1$, corresponding to an excess or deficit
of edges respectively. The example networks show the limit where the $+1$
blocks are fully connected and the $-1$ blocks have no edges. [21] groups the
bottom 8 directed networks into two classes, source-basin and core-periphery.
Here we split those groups into

  * •

Source-Basin: one-way flow from a loosely connected group to a densely
connected group.

  * •

Basin-Delta: one-way flow from a densely connected group to a loosely
connected group.

  * •

Core-Periphery: two-way flow between a densely connected group and a loosely
connected group.

  * •

Community-Hierarchy: one-way flow between densely connected groups.

Figure 1: All 2x2 block patterns for undirected networks and an example
network realising that block pattern. Figure 2: All 2x2 block patterns for
directed networks and an example network realising that block pattern.

###  III.1  Detectable $2\times 2$ Patterns

In the undirected case with the configuration model null

$\displaystyle\sum_{b}Q_{ab}$
$\displaystyle=\sum_{b}S_{ab}-\frac{T_{a}}{2E}\sum_{b}T_{b}$ (5)
$\displaystyle=\sum_{i\in a,j}A_{ij}-\frac{T_{a}}{2E}\sum_{i\in a,j}k_{j}$
$\displaystyle=\sum_{i\in a}k_{i}-T_{a}=0$

This implies the row and column sums of the $Q_{ab}$ matrix can’t
simultaneously all be positive or all negative, which is the result found in
[19]. This means that we can’t have a solid black or solid white, row or
column in the matrices of Figure 1, otherwise $Q(B)$ is identically zero. In
other words, it is impossible to have an excess (or deficit) of connections
between one group and all the other groups under the configuration model null.
I will refer to this as the KM rule.

An almost exactly analogous calculation applies in the directed case

$\displaystyle\sum_{b}Q_{ab}$
$\displaystyle=\sum_{b}S_{ab}-\frac{T_{a}^{(out)}}{E}\sum_{b}T_{b}^{(in)}$
$\displaystyle=\sum_{i\in a,j}A_{ij}-\frac{T_{a}^{(out)}}{E}\sum_{i\in
a,j}k^{(in)}_{j}$ $\displaystyle=\sum_{i\in a}k_{i}^{(out)}-T_{a}^{(out)}=0$

and similarly for the column sums. Thus in both the directed and undirected
cases, under the configuration model the only detectable $2\times 2$ block
patterns are 2-Community and Bipartite (called disassortative in [21])
networks

$\begin{pmatrix}1&-1\\\ -1&1\end{pmatrix}\quad\begin{pmatrix}-1&1\\\
1&-1\end{pmatrix}$

In particular a $2\times 2$ Core-Periphery is excluded.

With more than two blocks, other patterns can be observed, provided that the
KM rules are satisfied. [19] provides a list of all allowed $3\times 3$ and
$4\times 4$ patterns for the undirected case. To see that there must be more
than just these row and column sum constraints, consider a pattern like

$\begin{pmatrix}1&1&-1\\\ 1&-1&-1\\\ -1&-1&1\end{pmatrix}$

which represents a CP+1 community structure. This satisfies all the KM rules,
however these rules say nothing about the sizes of the communities. Thus, an
arbitrarily large $2\times 2$ CP structure plus one isolated node would be
allowed. We investigate the resolution of this paradox in the next section.

##  IV Constraint Equations

We will mostly consider the configuration model null, since this is the most
common, and interesting, case. Other cases are considered in Appendix A. For a
group, or pair of groups, to make a positive contribution to the modularity
requires $Q_{ab}B_{ab}>0$. Again, this is just the demand that in order to say
a structure is really present, there should be an excess or deficit of
connections within or between groups compared to a random network. The
structure we are aiming to detect is encoded by $B$. So for example, assuming
groups $c$ and $p$ formed a CP pair (as part of a larger network in order to
satisfy the KM rules) we would require

$Q_{cc}>0,Q_{cp}>0,Q_{pp}<0$

That is, an excess of connections within the core, from core to periphery and
a deficit of connections within the periphery.

Working with the configuration null, we derive general conditions first, then
apply them to specific structures in the relevant sections. We first write the
$Q_{aa}$ and $Q_{ab}$ matrix elements in terms of $S_{aa},S_{ab}$ and
$S_{bb}$. The degree sum can be split as follows,

$\displaystyle T_{a}$ $\displaystyle=\sum_{i\in c,j}A_{ij}=\sum_{i\in a,j\in
a}A_{ij}+\sum_{i\in a,j\in b}A_{ij}+\sum_{i\in a,j\not\in a,b}A_{ij}$ (6)
$\displaystyle=S_{aa}+S_{ab}+S_{a*}$

where $S_{a*}$ is the number of links from group $a$ to all other groups apart
from $a$ and $b$. We also write

$2E=S_{aa}+S_{bb}+2(S_{ab}+S_{a*}+S_{b*})+S_{**}$ (7)

Where $S_{**}$ is twice the number of links in and between all groups apart
from $a$ and $b$. This gives

$\displaystyle
Q_{ab}=S_{ab}-\frac{(S_{aa}+S_{ab}+S_{a*})(S_{bb}+S_{ab}+S_{b*})}{S_{aa}+S_{bb}+2(S_{ab}+S_{a*}+S_{b*})+S_{**}}$

Some simple algebra the shows that the conditions for the matrix elements to
be greater than zero can be written as

$\displaystyle Q_{aa}>0$ $\displaystyle\equiv
S_{aa}S_{**}>(S_{ab}+S_{a*})^{2}-S_{aa}(S_{bb}+2S_{b*})$ (8) $\displaystyle
Q_{ab}>0$ $\displaystyle\equiv S_{ab}S_{**}>(S_{aa}+S_{a*})(S_{bb}+S_{b*})$
(9) $\displaystyle\qquad\quad\qquad-S_{ab}(S_{ab}+S_{a*}+S_{b*})$

Consider the ideal case where $a$ and $b$ may be connected to each other but
share no links with the rest of the network. Any outside connections will
increase the null model term, so only makes it more difficult for the pair
$a,b$ to make a positive contribution to $Q(B)$. In this case
$S_{a*}=S_{b*}=0$ and the above inequalities simplify to

$\displaystyle Q_{aa}>0$ $\displaystyle\equiv
S_{aa}S_{**}>S_{ab}^{2}-S_{aa}S_{bb}$ (10) $\displaystyle Q_{ab}>0$
$\displaystyle\equiv S_{ab}S_{**}>S_{aa}S_{bb}-S_{ab}^{2}$ (11)

###  IV.1 Core-Periphery Constraints

Consider a block matrix which has CP structure between groups labelled $c$ and
$p$, together with some other blocks that allow the KM rules to be satisfied.
The block matrix to detect this looks like

$B=\begin{pmatrix}\vdots&\vdots&\vdots&\vdots&\vdots\\\
\ldots&1&\ldots&1\ldots\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\
\ldots&1&\ldots&-1\ldots\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\
\end{pmatrix}$

The groups $c$ and $p$ make a positive contribution to $Q(B)$ if
$Q_{cc},Q_{cp}\geq 0$ and $Q_{pp}\leq 0$ (also assuming they are not all
zero). In the ideal case there are no internal links in the $p$ group, so
$S_{pp}=0$. Assume also that there are no links between $c,p$ and the rest of
the network. In this case $Q_{pp}<0$ and $Q_{cp}>0$ always. However we only
have $Q_{cc}>0$ if

$S_{cc}S_{**}>S_{cp}^{2}$ (12)

otherwise $Q_{cc}<0$. If $Q_{cc}<0$ then we have a deficit of edges in the
core compared to what would be expected under the null. In this case a block
matrix with $B_{cc}=-1$ would give a larger value of $Q(B)$, i.e. a bipartite
(disassortative) relationship between $c$ and $p$ is less expected under the
configuration null. A core-periphery is possible under the configuration model
when

  * •

The number of edges in the core, $S_{cc}$, is large.

  * •

The number of edges between core and periphery, $S_{cp}$, is small.

  * •

The core-periphery system is part of a much larger network, $S_{**}\gg 0$.

###  IV.2 Directed Network Constraints

The directed case can be analysed similarly and the equivalent of Equations 10
and 11 for directed networks is

$\displaystyle Q_{aa}>0$ $\displaystyle\equiv
S_{aa}S_{**}>S_{ab}S_{ba}-S_{aa}S_{bb}$ (13) $\displaystyle Q_{ab}>0$
$\displaystyle\equiv S_{ab}S_{**}>S_{aa}S_{bb}-S_{ab}S_{ba}$ (14)

where it should be recalled that $S_{ab}\neq S_{ba}$ in general. CP structure
is subject to the same constraints as in the undirected case. For a directed
core-periphery to be detectable under the configuration model, we need

$S_{cc}S_{**}>S_{cp}S_{pc}$ (15)

The community-hierarchy (CH) structure is another interesting case. The
corresponding block matrix is

$B=\begin{pmatrix}\vdots&\vdots&\vdots&\vdots&\vdots\\\
\ldots&1&\ldots&1\ldots\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\
\ldots&-1&\ldots&1\ldots\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\
\end{pmatrix}$

Consider groups $a$ and $b$ which have intra-community links and directed
links from $a$ to $b$ only (so $S_{ba}=0$) and are otherwise disconnected from
the rest of the network.

Using the inequalities above we can show $Q_{aa}>0$, $Q_{bb}>0$ and $Q_{ba}<0$
always. However $Q_{ab}>0$ only if

$S_{ab}S_{**}>S_{aa}S_{bb}$ (16)

otherwise $Q_{ab}<0$ and a simple two community structure (where $B_{ab}=-1$)
is preferred. This means a community hierarchy can be detected if

  * •

The number of edges between communities, $S_{ab}$, is large.

  * •

The number of edges in each community, $S_{aa},S_{bb}$ are small.

  * •

The community-hierarchy is part of a much larger network, $S_{**}\gg 0$.

###  IV.3 Core-Periphery Example

To see what these limits look like in practice, consider an undirected network
with three groups, a core $c$, a periphery $p$ and a disconnected community
$m$. Let there be an equal number, $N$, of nodes in each group. Construct a
network using the Stochastic Block Model such that every possible edge within
and between groups is added with the corresponding probability from the matrix

$\omega=\begin{pmatrix}p_{c}&p_{p}&0\\\ p_{p}&0&0\\\ 0&0&p_{m}\end{pmatrix}.$

These networks will be evaluated against two block patterns

$Q_{CP}\equiv Q\left(\begin{pmatrix}1&1&-1\\\ 1&-1&-1\\\
-1&-1&1\end{pmatrix}\right)$

and

$Q_{Bipartite}\equiv Q\left(\begin{pmatrix}-1&1&-1\\\ 1&-1&-1\\\
-1&-1&1\end{pmatrix}\right)$

where the nodes are labelled in the obvious way. If the CP structure is
detectable then $Q_{CP}>Q_{Bipartite}$.

Figure 3: Color is $Q_{CP}-Q_{Bipartite}$ for fixed $p_{m}$ and variable
$p_{c},p_{p}$. Blue means CP can be detected under the configuration model,
red means a bipartite structure is always preferred. The dashed line shows
where $Q_{CP}=Q_{Bipartite}$.

Figure 3 shows $Q_{CP}-Q_{Bipartite}$ for fixed $p_{m}$ as $p_{c}$ and $p_{p}$
vary. $N=30$ and each pair of values is averaged over 20 random networks.
$p_{m}$ controls the size of the rest of the network and larger values give a
larger region where CP structure can be detected. The dashed line shows where
$Q_{CP}=Q_{Bipartite}$, corresponding to the curve
$p_{c}=\frac{p_{p}^{2}}{p_{m}}$. Pairs such as $(p_{p},p_{c})=(0.4,0.5)$ are
notable as values of $p_{c}$ and $p_{p}$ where CP structure is detectable when
the rest of the network is large ($p_{m}=0.8$) and undetectable when it is
small ($p_{m}=0.2$).

##  V Nestedness

Nestedness is a network property often considered in the analysis of
ecological networks [37] but with many other applications [32]. A nested
network has a hierarchy of degrees such that the neighbors of a node low
degree node are a subset of the neighbours of any higher degree node [38]. A
perfectly nested unipartite network admits an ordering of the nodes that
brings the adjacency matrix into a triangular form. For example, the matrix

$A=\begin{pmatrix}\mathbf{0}&\mathbf{1}&\mathbf{1}&\mathbf{1}&1&1&1&1\\\
\mathbf{1}&\mathbf{0}&\mathbf{1}&\mathbf{1}&1&1&1&0\\\
\mathbf{1}&\mathbf{1}&\mathbf{0}&\mathbf{1}&1&1&0&0\\\
\mathbf{1}&\mathbf{1}&\mathbf{1}&\mathbf{0}&0&0&0&0\\\ 1&1&1&0&0&0&0&0\\\
1&1&1&0&0&0&0&0\\\ 1&1&0&0&0&0&0&0\\\ 1&0&0&0&0&0&0&0\end{pmatrix}$

is perfectly nested. As noted in [39], this concept is very close to the idea
of a core-periphery structure. Indeed in the ecological context, [37] states,
‘To be nested, a network must consist of a core group of generalists all
interacting with each other, and with extreme specialists interacting only
with generalist species’, very similar to the definition of a core-periphery
network.

By partitioning the nodes into two blocks, $c,p$, where nodes in $c$ are
highly connected (the bold upper left block) and rest of the nodes are in $p$,
a nested network has the same block structure as a $2\times 2$ core-periphery
network. In practice we would not require perfectly nested structures, only
that there is an excess or deficit of links compared the the expectation under
the null model. The KM rules imply that, under the configuration model, such
nested matrices are not detectable. Adding other structure to the network to
avoid the KM rule leads to the CP constraint, Equation 12.

Nestedness is often studied in bipartite networks. For example, interactions
between animals and plants, where no animal-animal or plant-plant interactions
are considered. In this case the adjacency matrix has the form

$A=\begin{pmatrix}0&\tilde{A}\\\ \tilde{A}^{T}&0\end{pmatrix}$

Where $\tilde{A}$ is the $N\times M$ bi-adjacency matrix. In this context, a
nested structure is one where $\tilde{A}$ has the distinct nested triangular
form for some ordering of the nodes. We can split the bi-adjacency matrix into
a core and periphery and evaluate the partition using the $4\times 4$ block
structure

$B=\begin{pmatrix}-1&-1&1&1\\\ -1&-1&1&-1\\\ 1&1&-1&-1\\\
1&-1&-1&-1\end{pmatrix}$

$Q(B)$ will be large and positive if the matrix is bipartite and if each part
has a core that interacts with the other core and periphery and a periphery
that only interacts with the other core. As this is a $4\times 4$ block with a
mixture of $\pm 1$ in each row, the KM rules are satisfied. Denote the left
part by $a$ and the right by $b$. $a$ and $b$ are then each split into core
$c$ and periphery $p$ giving 4 groups: $ca,pa,cb,pb$. For this kind of
structure to be detected requires that $Q_{ca,cb},Q_{ca,pb},Q_{cb,pa}>0$ and
the rest are less than $0$.

Assuming the best case of perfect bipartite structure and perfect CP structure
between parts gives $Q_{pa,pb}<0$, $Q_{ca,pb}<0$ and $Q_{cb,pa}<0$. The term
$Q_{ca,cb}$ is the interesting one. Using $*=\\{pa,pb\\}$ gives $S_{**}=0$,
$S_{ca,*}=S_{ca,pb}$ and $S_{cb,*}=S_{cb,pa}$. Substituting into Equation 8
gives

$\displaystyle Q_{ca,cb}>0$ $\displaystyle\equiv
S_{ca,cb}(S_{ca,cb}+S_{ca,pb}+S_{cb,pa})>S_{ca,pb}S_{cb,pa}$ (17)

This condition is somewhat more complicated that the CP and CH conditions, but
broadly requires

  * •

The number of interactions between the cores of $a$ and $b$, $S_{ca,cb}$, is
large.

  * •

The number of interactions between cores and peripheries,
$S_{ca,pb},S_{cb,pa}$ is small.

These results clarify the somewhat elusive nature of nestedness as highlighted
in e.g. [40, 41, 42, 43]. The configuration model is quite constraining. While
an observed network may be sorted so that the adjacency matrix shows nested
structure, a random network with the same degree sequence could also be sorted
to show similar structure. Under a less restrictive null model, like the ER
model, the KM rules do not hold and nestedness is detectable, as found in e.g.
[40]. However, weakening the null risks confusing degree correlations for
other structures [41], in particular dissassortative/bipartite ones. Work like
[44], which situates nested structures inside larger networks is more
promising in terms evading the KM rules and detecting nestedness under the
configuration model.

Figure 4: Left: $Q_{CP}-Q_{Bipartite}$ networks constructed as described in
the text. Blue means CP can be detected under the configuration model, red
means a bipartite structure is always preferred. The dotted line shows where
$Q_{CP}=Q_{Bipartite}$. Right: NODF metric for the same networks. High values
(near 1) imply a strongly nested network. The average of 20 random networks
used for every $p_{cp},p_{cc}$ pair.

Figure 4 shows what happens for networks constructed using the SBM where the
edge probabilities are given by

$\begin{pmatrix}0&0&p_{cc}&p_{cp}\\\ 0&0&p_{cp}&0\\\ p_{cc}&p_{cp}&0&0\\\
p_{cp}&0&0&0\\\ \end{pmatrix}$

placing $N_{c}=10$ nodes in the core and $N_{p}=25$ in the periphery. We
evaluate block modularity against the patterns

$Q_{CP}\equiv Q\left(\begin{pmatrix}-1&-1&1&1\\\ -1&-1&1&-1\\\ 1&1&-1&-1\\\
1&-1&-1&-1\\\ \end{pmatrix}\right)$

and

$Q_{Bipartite}\equiv Q\left(\begin{pmatrix}-1&-1&-1&1\\\ -1&-1&1&-1\\\
-1&1&-1&-1\\\ 1&-1&-1&-1\\\ \end{pmatrix}\right)$

and evaluate nestedness using the popular NODF metric [45]. The key point is
that there are cases where a bipartite structure is preferred to a CP one but
the NODF value is still quite high, for example, the point
$(p_{cp},p_{cc})=(0.7,0.5)$. This would suggest that even though the network
is apparently strongly nested, this is not surprising under the configuration
null.

##  VI Resolution Limit

The well-known resolution limit of modularity [33] can be derived via a
similar argument. Consider two groups $a,b$ which are part of a larger
network. It is better, in terms of increasing $Q(B)$, to merge $a$ and $b$ if
$Q_{ab}>0$. Under the configuration model

$Q_{ab}>0\equiv
S_{ab}>\frac{(S_{aa}+S_{ab}+S_{a*})(S_{bb}+S_{ab}+S_{b*})}{2E}$

where the $*$ index denotes all the nodes in the network other than the nodes
in $a,b$. If there are no links between $a$ and $b$, then $S_{ab}=0$ and,
provided there are some internal links in $a$ or $b$, we can never have
$Q_{ab}>0$ and so the communities should always be kept separate.

The resolution limit in [33] arises by considering a network with equal
numbers of edges in $a$ and $b$, one link between communities $a$ and $b$, and
one link connecting each of $a$ and $b$ to the rest of the network giving
$S_{ab}=S_{a*}=S_{b*}=1$ and $S_{aa}=S_{bb}=2l$. Substituting into the above
gives $Q_{ab}<0$ if

$l<\sqrt{E}-1$

which is the result found in [33] and derived in a similar way to the above in
[46]. As pointed out by [46], in the configuration model, when the network is
large enough, the expectation for a single edge can be much less than 1. The
resolution limit is therefore doing what it is designed to do, identifying
that a single edge between communities is unusual under the null model.
Equation (9) gives the most general form of the resolution limit.
Disconnecting $a,b$ from the rest of the network, which is the best case, two
communities will be kept separate if

$S_{ab}S_{**}<S_{aa}S_{bb}-S_{ab}^{2}$ (18)

The threshold value of $S_{ab}$ depends not only what is happening in the
groups $a$ and $b$, but also on what is happening in the rest of the network
$S_{**}$. Seen in this light, all of the results presented above are a type of
resolution limit, but for core-periphery, community-hierarchy and nested
structures. The resolution limit suggests that, for small communities in large
networks, even single edge between ‘obvious’ communities can be unexpected.
The results of the previous section similarly imply that ‘obvious’ CP and CH
structures can be an expected as a consequence of the degree sequence.

##  VII Relation of Block Modularity to the Stochastic Block Model

The resolution limit is often partially evaded using the scaled configuration
model [34]

$P_{ij}=\gamma\frac{k_{i}k_{j}}{2E}$

as a null. With this null model [47, 48] shows that maximising $Q_{Newman}$ is
equivalent to the method of maximum likelihood applied to a particular class
of degree corrected Stochastic Block Models (dc-SBMs) [26] called the planted
partition model _if $\gamma$ is chosen correctly_. It turns out that block
modularity with the scaled configuration model is similarly related to the dc-
SBM. In fact, with a diffrent choice of null, block modularity can be made to
be identical to the dc-SBM model likelihood in general.

In the dc-SBM, the edge probability is

$P_{ij}=\frac{k_{i}k_{j}}{2E}\omega_{c(i),c(j)}$

where $\omega$ is a $K\times K$ matrix controlling the expected number of
edges in and between each group. In [47] it is shown that maximising the log-
likelihood for the undirected dc-SBM corresponds to maximisation of the
function

$\log
P(G|\omega,c)=\frac{1}{2}\sum_{ij}\left(A_{ij}\log(\omega_{c(i),c(j)})-\frac{k_{i}k_{j}}{2E}\omega_{c(i),c(j)}\right)$
(19)

Where $P(G|\omega,c)$ is the probability of the observed network $G$ given
$\omega$ and the partition $c$. The planted partition model is one where

$\omega_{ab}=(\omega_{in}-\omega_{out})\delta_{ab}+\omega_{out}$

corresponding to a matrix with $\omega_{in}$ on the diagonal and
$\omega_{out}$ elsewhere. Substituting this into Equation 19, [47] shows that
maximising $Q_{Newman}$ is equivalent to maximising the likelihood, Equation
19, provided the scaled configuration model is used with a particular value of
$\gamma$. We can generalise this to block modularity. Define

$\omega_{ab}=(\omega_{in}-\omega_{out})B_{ab}+\omega_{out}$ (20)

using values for $B$ in $\\{1,0\\}$ in this case. The value $\omega_{in}$ is
associated with the excesses and $\omega_{out}$ with the deficits.
Substituting into Equation 19 rearranging and dropping some additive constants
which don’t affect the optimisation gives

$\displaystyle\log
P(G|\omega,c)=\frac{1}{2}\log\frac{\omega_{in}}{\omega_{out}}\sum_{ij}$
$\displaystyle B_{c(i),c(j)}\bigg{(}A_{ij}-$ (21)
$\displaystyle\frac{k_{i}k_{j}}{2E}\frac{\omega_{in}-\omega_{out}}{\log\omega_{in}-\log\omega_{out}}\bigg{)}$

Which is equivalent to block modularity with the scaled configuration model,
up to the scaling factor $\log\frac{\omega_{in}}{\omega_{out}}$, _provided_

$\gamma=\frac{\omega_{in}-\omega_{out}}{\log\omega_{in}-\log\omega_{out}}.$

The standard configuration model has $\omega_{in}=\omega_{out}=1$ which, due
to the overall factor $\log\frac{\omega_{in}}{\omega_{out}}$, causes Equation
21 to vanish. The likelihood, Equation 19, is derived by computing the
probability of the network $G$ given $\omega$ and $g$. With $\omega_{ab}=1$
knowing the partition gives no extra information about the probability of an
edge existing and $\log P(G|\omega,c)$ is constant.

Having one free parameter, $\gamma$, gives the model enough flexibility to be
identified with the planted partition model. An even more flexible null allows
maximising block modularity to be equivalent to likelihood maximisation of the
dc-SBM. The log-likelihood, Equation 19, can be written as a sum over blocks

$\log
P(G|\omega,c)=\frac{1}{2}\sum_{ab}\left(S_{ab}\log(\omega_{ab})-\frac{T_{a}T_{b}}{2E}\omega_{ab}\right)$

Now, define a new null model, which we will call the block scaled
configuration model, via

$P_{ij}=\frac{k_{i}k_{j}}{2E}\gamma_{c(i),c(j)}$

Substituting into block modularity gives

$Q(B)=\frac{1}{2E}\sum_{ab}B_{ab}\left(S_{ab}-\frac{T_{a}T_{b}}{2E}\gamma_{ab}\right)$
(22)

If

$B_{ab}=\log\omega_{ab}$

and

$\gamma_{ab}=\frac{\omega_{ab}}{\log\omega_{ab}}$

then optimising the likelihood and optimising the modularity are equivalent.
Here $\omega_{ab}$ is the edge probability relative to the configuration
model. For $\omega_{ab}<1$, $B_{ab}<0$ and $\gamma_{ab}<0$ meaning $Q_{ab}<0$,
so this term always reduces the modularity/likelihood and optimising the
partition will involve trying to place fewer edges between $a$ and $b$. For
$\omega_{ab}>1$ we have $B_{ab}>0$ and $\gamma_{ab}>0$, so the
modularity/likelihood can be increased by having more edges between $a$ and
$b$ than the null model. This is similar to how we counted excesses and
deficits in the block modularity with the configuration null, except the
excesses and deficits are now weighted.

Despite the possibility of making modularity equivalent to the maximisation of
a dc-SBM likelihood, it is probably better to think of them as conceptually
different approaches. In the ‘inferential’ approach [49], the parameters of
the dc-SBM which could have generated the observed data are determined by
maximising the likelihood. In the ‘descriptive’ approach, modularity
maximisation, the observed network is compared to the expectation under some
null hypothesis and unexpected partitions are highlighted. We compare these
approaches on CP structure in the next section.

###  VII.1 CP structure in the dc-SBM

In the modularity framework there is no requirement that $B_{ab}$ and
$\gamma_{ab}$ be related. If they are assumed to be related via $\omega_{ab}$
according to Equation 22, the values of $\omega_{ab}$ are not known and must
be estimated. We could proceed as in [47] by choosing some starting values of
$B$ and $\gamma$; finding the partition that optimises the
likelihood/modularity; estimate the dc-SBM parameters using

$\omega_{ab}=2E\frac{S_{ab}}{T_{a}T_{b}}$ (23)

update $B$ and $\gamma$ and iterate the process until convergence. Preliminary
experiments suggest this approach is quite sensitive to the starting values of
$\omega$ e.g. if we start with nodes in assortative communities, it is very
hard to transition to having the nodes in disassortative groups, even if this
would be optimal.

An approach that is sufficient for the small networks we will study here is a
based on first fixing $K$, the number of groups. Estimating the correct number
of groups is a difficult problem which we do not address, see e.g. [50].
Starting with random values of $\omega_{ab}=1\pm 0.1\text{ unif}(-1,1)$ and
random labels $c(i)\in\\{0,\ldots,K-1\\}$, Equation 22 is maximised using a
greedy label swapping heuristic. Visiting the nodes in random order, we
compute the change in $Q$ from swapping the label of $i$ to any of the other
allowed labels and choosing the swap which leads to the largest increase in
$Q$. When computing the change caused by a label swap we consider the change
in, $S_{ab}$ and $T_{a}$, as well as $\omega_{ab}$ using Equation 23, and
consequently the change in $B_{ab}$ and $\gamma_{ab}$.

Figure 5: Left: SBM network, partition inferred by maximising the likelihood,
Equation 22. Centre: Proportion of three structures found in 1000 samples from
the configuration model of the left hand network. Right: Label assignment
inferred for a configuration model network with CP structure.

Figure 5 uses the regular SBM to generate a network with parameters

$\omega=\begin{pmatrix}0.6&0.5&0\\\ 0.5&0&0\\\ 0.0&0&0.2\end{pmatrix}$

The left panel shows that the optimisation of Equation 22 recovers the
expected partition into core, periphery and independent community. However
note from Figure 3 that this combination of parameters is one which is
‘forbidden’ under the configuration model, Equation 12. Indeed, for this
specific network and this partition we have $Q_{CP}=0.54$ and
$Q_{Bipartite}=0.62$, where these are computed as in Section IV.

This conflict arises because the two approaches are asking and answering
different questions. The effectiveness of inference using the dc-SBM is
generally discussed in terms of efficiently compressing the network [51, 52].
In our language this approach not only changes the label assignments but also
the null model. The result of optimising both modularity and null is the
partition and parameters that could be (and this case were) used to generate
the network. In contrast, using modularity we suppose that our network is
drawn at random from a fixed null model. Using the configuration model of the
observed network, this means picking a random network with the same degree
sequence. We then ask about the chance of finding the same structures in a
random network as seen in the observed one.

The middle panel of Figure 5 shows what happens when we do this explicitly.
For the network on the left, 1000 random networks were created with the same
degree sequence. The most likely $\omega$ that could have generated these
networks in the dc-SBM is inferred and checked for different $2\times 2$ block
patterns using the following rules:

  * •

First check if: $\omega_{aa}+2\omega_{ab}+\omega_{bb}>2E/2$ i.e. the $2\times
2$ block contains at least half of the network’s edges.

  * •

For every distinct pair of communities the network has the corresponding
structure if one or more of the conditions below is satisfied:

    * –

Community: $\omega_{ab}<f\min(\omega_{aa},\omega_{bb})$

    * –

Bipartite: $f\omega_{ab}>\max(\omega_{aa},\omega_{bb})$

    * –

CP: $\min(\omega_{aa},\omega_{bb})<f\omega_{ab}$ and
$\min(\omega_{aa},\omega_{bb})<f\max(\omega_{aa},\omega_{bb})$

$f\leq 1$ is a parameter where smaller values make the conditions more
stringent. The key point is that CP structure is often found in samples from
the configuration model of this network while bipartite structure is less
common. This is also what modularity and the fact that $Q_{CP}<Q_{Bipartite}$
implies.

##  VIII Conclusions

This analysis shows that the configuration model is quite constraining in
terms of the meso-scale structures that it allows. There are only two possible
$2\times 2$ patterns, and there are strong constraints on the occurrence of CP
and CH pairs as part of larger meso-scale structures. Nested networks are also
quite restricted. Using a weaker null model, like the ER null, relaxes these
constraints but risks confusing structure with effects better attributed to
the network’s degree sequence. An alternative approach, as discussed in
Section VII, is based on supposing that some flexible model, in this case the
dc-SBM, generated the observed network and finding the most likely model
parameters. This inferential approach has been strongly advocated [53, 54, 49]
as superseding the ‘descriptive’ approach of modularity maximisation,
paralleling vigorous debates in statistics over inferential Bayesian
statistics versus classical methods [55, 56].

The failure of modularity to detect the intuitive partition, the resolution
limit [33], has long been discussed and is generally seen as something to be
evaded either by modifying the null [34] or altering the definition of
modularity [57, 58]. As shown in this work, the resolution limit is a specific
example of a general type of constraint which arises when analysing network
structure against a null model. Inequalities like Equations 8 show that the
configuration model is quite stringent and that intuitive structures, like
communities, core-periphery systems and nestedness can sometimes be explained
by the degree sequence alone - any random network with that degree sequence is
likely to have the ‘intuitive’ structure, so finding it is expected and the
highest modularity partition will identify something else as the most
unexpected structure.

The results of Figure 5 are striking. Maximising the dc-SBM likelihood finds
the planted CP structure which modularity rejects. As discussed in Section
VII, these approaches are answering two different questions. The inference is
telling us how our network could have been constructed by picking groups and
randomly connecting them according to some probability matrix. Modularity is
telling us how likely we are to see a given meso-structure in a random network
with this degree sequence. They can and do give different answers and the most
appropriate method of analysis surely depends on the questions of interest to
the researcher.

There are numerous practical problems in community detection using modularity
[49], methods that address them [58, 59] and papers comparing the performance
of different methods in practice [60]. This work does not aim to address this.
Rather the aim is to incorporate structures other than assortative communities
into discussions of modularity and the resolution limit as well as to clarify
the connection and the difference between modularity maximisation and model
inference. It has been pointed out before that formalising the intuitive
notion of ‘community’ or ‘structure’ is difficult [46] and a universal best
definition is not even possible [61]. The constraints found here hopefully
shed light on the elusiveness of certain network structures and help
practitioners better understand and use methods of meso-scale structure
detection.

##  Appendix A Other Null Models

###  A.1 Erdős-Rényi Model

With the ER null model the global sum provides a hard constraint

$\displaystyle\sum_{ab}Q_{ab}$
$\displaystyle=\sum_{ab}S_{ab}-\sum_{ab}pN_{a}N_{b}$ (24)
$\displaystyle=2E-pN^{2}=0$

where $N_{a}$ is the number of nodes in group $a$. This means under the ER
null model we can have an excess (or deficit) between one group and all the
others (including itself), but we can’t have an excess or deficit between
every group with every other one. This rules out the all white or all black
block patterns. The row sums are

$\displaystyle\sum_{b}Q_{ab}$
$\displaystyle=\sum_{b}S_{ab}-N_{a}p\sum_{b}N_{b}=T_{a}-2E\frac{N_{a}}{N}$
(25)

So if there is a group with all excesses, this is an upper limit on the
contribution of that group to the modularity, and similarly for deficits, the
negative of this is a lower bound. The equivalent of Equation 8 is

$Q_{ab}>0\equiv\frac{S_{ab}}{2E}>\frac{N_{a}N_{b}}{N^{2}}$ (26)

i.e. the fraction of edges observed between or within groups $a$ and $b$
should be greater than the fraction of edges which could possibly exist.

###  A.2 Scaled Configuration Model

The row sums for the scaled configuration model are

$\displaystyle\sum_{b}Q_{ab}$ $\displaystyle=T_{a}(1-\gamma)$ (27)

and the total sum is

$\displaystyle\sum_{ab}Q_{ab}$ $\displaystyle=2E(1-\gamma)$ (28)

The value of $\gamma$ sets the upper and lower limits on sums of all black or
all white rows. For evading the resolution limit values of $\gamma>1$ are
usually proposed [62]. However for detecting CP structure, $\gamma<1$ is
preferable. The equivalent of Equations 10 and 11 is

$\displaystyle Q_{ab}>0$ $\displaystyle\equiv
S_{ab}S_{**}>\gamma(S_{aa}S_{bb}-S_{ab}^{2})$ (29)
$\displaystyle\qquad\qquad+(\gamma-1)S_{ab}(S_{aa}+2S_{ab}+S_{bb})$
$\displaystyle Q_{ab}>0$ $\displaystyle\equiv
S_{aa}S_{**}>\gamma(S_{ab}^{2}-S_{aa}S_{bb})$ (30)
$\displaystyle\qquad\qquad+(\gamma-1)S_{aa}(S_{aa}+2S_{ab}+S_{bb})$

The scaled configuration model can be treated by substituting
$\gamma\rightarrow\gamma_{ab}$ in the equations above. For CP structure,
requiring $Q_{cc}>0$ is equivalent to

$\displaystyle Q_{cc}>0$ $\displaystyle\equiv S_{cc}S_{**}>\gamma
S_{cp}^{2}+(\gamma-1)S_{cc}(S_{cc}+2S_{cp})$ (31)

This means $\gamma<1$ makes CP structure easier to detect under this model.
Similar results to the ones found in Sections V and VI for nestedness and the
resolution limit can be derived using the above equations.

## References

  * Barabási [2013] A.-L. Barabási, Network science, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 371, 20120375 (2013).
  * Fortunato and Newman [2022] S. Fortunato and M. E. Newman, 20 years of network community detection, Nature Physics 18, 848 (2022).
  * Radicchi  _et al._ [2004] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, Defining and identifying communities in networks, Proceedings of the national academy of sciences 101, 2658 (2004).
  * Newman [2004] M. E. Newman, Detecting community structure in networks, The European physical journal B 38, 321 (2004).
  * Fortunato [2010] S. Fortunato, Community detection in graphs, Physics reports 486, 75 (2010).
  * Fortunato and Hric [2016] S. Fortunato and D. Hric, Community detection in networks: A user guide, Physics reports 659, 1 (2016).
  * Borgatti and Everett [2000] S. P. Borgatti and M. G. Everett, Models of core/periphery structures, Social networks 21, 375 (2000).
  * Csermely  _et al._ [2013] P. Csermely, A. London, L.-Y. Wu, and B. Uzzi, Structure and dynamics of core/periphery networks, Journal of Complex Networks 1, 93 (2013).
  * Rombach  _et al._ [2014] M. P. Rombach, M. A. Porter, J. H. Fowler, and P. J. Mucha, Core-periphery structure in networks, SIAM Journal on Applied mathematics 74, 167 (2014).
  * Zhang  _et al._ [2015] X. Zhang, T. Martin, and M. E. Newman, Identification of core-periphery structure in networks, Physical Review E 91, 032803 (2015).
  * Kojaku and Masuda [2017] S. Kojaku and N. Masuda, Finding multiple core-periphery pairs in networks, Physical Review E 96, 052313 (2017).
  * Yanchenko and Sengupta [2023] E. Yanchenko and S. Sengupta, Core-periphery structure in networks: A statistical exposition, Statistics Surveys 17, 42 (2023).
  * Holme  _et al._ [2003] P. Holme, F. Liljeros, C. R. Edling, and B. J. Kim, Network bipartivity, Physical Review E 68, 056107 (2003).
  * Estrada and Rodríguez-Velázquez [2005] E. Estrada and J. A. Rodríguez-Velázquez, Spectral measures of bipartivity in complex networks, Physical Review E 72, 046105 (2005).
  * Newman [2006a] M. E. Newman, Finding community structure in networks using the eigenvectors of matrices, Physical review E 74, 036104 (2006a).
  * Barber [2007] M. J. Barber, Modularity and community detection in bipartite networks, Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 76, 066102 (2007).
  * Chen  _et al._ [2014] L. Chen, Q. Yu, and B. Chen, Anti-modularity and anti-community detecting in complex networks, Information Sciences 275, 293 (2014).
  * Arthur [2020] R. Arthur, Modularity and projection of bipartite networks, Physica A: Statistical Mechanics and its Applications 549, 124341 (2020).
  * Kojaku and Masuda [2018] S. Kojaku and N. Masuda, Core-periphery structure requires something else in the network, New Journal of physics 20, 043012 (2018).
  * Li  _et al._ [2021] H. Li, C. Zhao, Y. Liu, and X. Zhang, Anomaly detection by discovering bipartite structure on complex networks, Computer Networks 190, 107899 (2021).
  * Liu  _et al._ [2023] C. X. Liu, T. J. Alexander, and E. G. Altmann, Nonassortative relationships between groups of nodes are typical in complex networks, PNAS nexus 2, pgad364 (2023).
  * Alvarez-Hamelin  _et al._ [2005] J. Alvarez-Hamelin, L. Dall’Asta, A. Barrat, and A. Vespignani, Large scale networks fingerprinting and visualization using the k-core decomposition, Advances in neural information processing systems 18 (2005).
  * Zhou and Mondragón [2004] S. Zhou and R. J. Mondragón, The rich-club phenomenon in the internet topology, IEEE communications letters 8, 180 (2004).
  * Arthur [2023] R. Arthur, Discovering block structure in networks, Physica A: Statistical Mechanics and its Applications 613, 128527 (2023).
  * Newman [2006b] M. E. Newman, Modularity and community structure in networks, Proceedings of the national academy of sciences 103, 8577 (2006b).
  * Karrer and Newman [2011] B. Karrer and M. E. Newman, Stochastic blockmodels and community structure in networks, Physical review E 83, 016107 (2011).
  * Chung and Lu [2002] F. Chung and L. Lu, The average distances in random graphs with given expected degrees, Proceedings of the National Academy of Sciences 99, 15879 (2002).
  * Expert  _et al._ [2011] P. Expert, T. S. Evans, V. D. Blondel, and R. Lambiotte, Uncovering space-independent communities in spatial networks, Proceedings of the National Academy of Sciences 108, 7663 (2011).
  * Newman  _et al._ [2001] M. E. Newman, S. H. Strogatz, and D. J. Watts, Random graphs with arbitrary degree distributions and their applications, Physical review E 64, 026118 (2001).
  * Albert and Barabási [2002] R. Albert and A.-L. Barabási, Statistical mechanics of complex networks, Reviews of modern physics 74, 47 (2002).
  * Park and Newman [2003] J. Park and M. E. Newman, Origin of degree correlations in the internet and other networks, Physical review e 68, 026112 (2003).
  * König  _et al._ [2014] M. D. König, C. J. Tessone, and Y. Zenou, Nestedness in networks: A theoretical model and some applications, Theoretical Economics 9, 695 (2014).
  * Fortunato and Barthelemy [2007] S. Fortunato and M. Barthelemy, Resolution limit in community detection, Proceedings of the national academy of sciences 104, 36 (2007).
  * Reichardt and Bornholdt [2006] J. Reichardt and S. Bornholdt, Statistical mechanics of community detection, Physical review E 74, 016110 (2006).
  * Lee and Wilkinson [2019] C. Lee and D. J. Wilkinson, A review of stochastic block models and extensions for graph clustering, Applied Network Science 4, 1 (2019).
  * Nicosia  _et al._ [2009] V. Nicosia, G. Mangioni, V. Carchiolo, and M. Malgeri, Extending the definition of modularity to directed graphs with overlapping communities, Journal of Statistical Mechanics: Theory and Experiment 2009, P03024 (2009).
  * Nielsen and Bascompte [2007] A. Nielsen and J. Bascompte, Ecological networks, nestedness and sampling effort, Journal of Ecology , 1134 (2007).
  * Mariani  _et al._ [2019] M. S. Mariani, Z.-M. Ren, J. Bascompte, and C. J. Tessone, Nestedness in complex networks: observation, emergence, and implications, Physics Reports 813, 1 (2019).
  * Lee  _et al._ [2016] S. H. Lee _et al._ , Network nestedness as generalized core-periphery structures, Physical Review E 93, 022306 (2016).
  * Joppa  _et al._ [2010] L. N. Joppa, J. M. Montoya, S. Vicente, J. Sanderson, S. L. Pimm, _et al._ , On nestedness in ecological networks, Evolutionary ecology research. 2010; 12: 35-46 (2010).
  * Jonhson  _et al._ [2013] S. Jonhson, V. Domínguez-García, and M. A. Muñoz, Factors determining nestedness in complex networks, PloS one 8, e74025 (2013).
  * Payrató-Borras  _et al._ [2019] C. Payrató-Borras, L. Hernández, and Y. Moreno, Breaking the spell of nestedness: the entropic origin of nestedness in mutualistic systems, Physical Review X 9, 031024 (2019).
  * Bruno  _et al._ [2020] M. Bruno, F. Saracco, D. Garlaschelli, C. J. Tessone, and G. Caldarelli, The ambiguity of nestedness under soft and hard constraints, Scientific reports 10, 19903 (2020).
  * Solé-Ribalta  _et al._ [2018] A. Solé-Ribalta, C. J. Tessone, M. S. Mariani, and J. Borge-Holthoefer, Revealing in-block nestedness: Detection and benchmarking, Physical review E 97, 062302 (2018).
  * Almeida-Neto  _et al._ [2008] M. Almeida-Neto, P. Guimaraes, P. R. Guimaraes Jr, R. D. Loyola, and W. Ulrich, A consistent metric for nestedness analysis in ecological systems: reconciling concept and measurement, Oikos 117, 1227 (2008).
  * Good  _et al._ [2010] B. H. Good, Y.-A. De Montjoye, and A. Clauset, Performance of modularity maximization in practical contexts, Physical review E 81, 046106 (2010).
  * Newman [2016] M. E. Newman, Equivalence between modularity optimization and maximum likelihood methods for community detection, Physical Review E 94, 052315 (2016).
  * Young  _et al._ [2018] J.-G. Young, G. St-Onge, P. Desrosiers, and L. J. Dubé, Universality of the stochastic block model, Physical Review E 98, 032309 (2018).
  * Peixoto [2023] T. P. Peixoto,  _Descriptive vs. inferential community detection in networks: Pitfalls, myths and half-truths_ (Cambridge University Press, 2023).
  * Newman and Reinert [2016] M. E. Newman and G. Reinert, Estimating the number of communities in a network, Physical review letters 117, 078301 (2016).
  * Rosvall  _et al._ [2009] M. Rosvall, D. Axelsson, and C. T. Bergstrom, The map equation, The European Physical Journal Special Topics 178, 13 (2009).
  * Peixoto [2013] T. P. Peixoto, Parsimonious module inference in large networks, Physical review letters 110, 148701 (2013).
  * Peixoto [2014] T. P. Peixoto, Hierarchical block structures and high-resolution model selection in large networks, Physical Review X 4, 011047 (2014).
  * Guimerà [2020] R. Guimerà, One model to rule them all in network science?, Proceedings of the National Academy of Sciences 117, 25195 (2020).
  * Efron [1986] B. Efron, Why isn’t everyone a bayesian?, The American Statistician 40, 1 (1986).
  * Gelman [2008] A. Gelman, Objections to Bayesian statistics, Bayesian Analysis 3, 445 (2008).
  * Chen  _et al._ [2015] M. Chen, T. Nguyen, and B. K. Szymanski, A new metric for quality of network community structure, arXiv preprint arXiv:1507.04308 (2015).
  * Miyauchi and Kawase [2016] A. Miyauchi and Y. Kawase, Z-score-based modularity for community detection in networks, PloS one 11, e0147805 (2016).
  * Yanchenko and Sengupta [2024] E. Yanchenko and S. Sengupta, A generalized hypothesis test for community structure in networks, Network Science 12, 122 (2024).
  * Ghasemian  _et al._ [2019] A. Ghasemian, H. Hosseinmardi, and A. Clauset, Evaluating overfit and underfit in models of network community structure, IEEE Transactions on Knowledge and Data Engineering 32, 1722 (2019).
  * Peel  _et al._ [2017] L. Peel, D. B. Larremore, and A. Clauset, The ground truth about metadata and community detection in networks, Science advances 3, e1602548 (2017).
  * Lancichinetti and Fortunato [2011] A. Lancichinetti and S. Fortunato, Limits of modularity maximization in community detection, Physical review E 84, 066122 (2011).