# Hierarchical configuration model

Remco van der Hofstad  Eindhoven University of Technology, Department of
Mathematics and Computer Science, P.O. Box 513, 5600 MB Eindhoven, The
Netherlands  Johan S.H. van Leeuwaarden  Eindhoven University of Technology,
Department of Mathematics and Computer Science, P.O. Box 513, 5600 MB
Eindhoven, The Netherlands  Clara Stegehuis  Eindhoven University of
Technology, Department of Mathematics and Computer Science, P.O. Box 513, 5600
MB Eindhoven, The Netherlands

###### Abstract

We introduce a class of random graphs with a community structure, which we
call the hierarchical configuration model. On the inter-community level, the
graph is a configuration model, and on the intra-community level, every vertex
in the configuration model is replaced by a community: i.e., a small graph.
These communities may have any shape, as long as they are connected. For these
hierarchical graphs, we find the size of the largest component, the degree
distribution and the clustering coefficient. Furthermore, we determine the
conditions under which a giant percolation cluster exists, and find its size.

##  1 Introduction and model

A characteristic feature of many real-world complex networks is that the
degree distribution obeys a power law. A popular model for such power-law
networks is the _configuration model_ , a random graph with a prescribed
degree distribution [3]. A major shortcoming of this model, however, is that
it is locally tree-like – it contains only a few short cycles and the graph
next to most vertices is a tree – while a prominent feature of complex
networks is that they often have a community structure [7]. The communities
are highly connected and contain many short cycles, while edges between
different communities are more scarce. Therefore, the configuration model is
not a realistic model to study networks with a community structure.

Several other random graph models have been proposed to include community
structures or short cycles. For example, in [1, 4, 23] communities are
introduced in the form of households, i.e., complete graphs of a certain size.
The random graph then remains a configuration model on the macroscopic level,
while on the microscopic level each vertex of the graph can be replaced by a
household. The households introduce a community structure in the graph, which
creates random graphs with not only a prescribed degree distribution but also
a tunable clustering coefficient. Another way to incorporate short cycles in
the configuration model is to introduce triangles [18]. In this case, besides
the vertex degrees, also the number of triangles each vertex belongs to is
prescribed. Then triangles are formed by joining three nodes at random, and
regular edges are formed as in the configuration model. The model was extended
in [15] to include arbitrary subgraphs. Yet another method to include
clustering in random graph models is to use _random intersection graphs_ [5],
which allows one to prescribe the exponent of the power-law degree sequence
and the amount of clustering. In [20], an algorithm is developed for creating
a model that matches the community structure in real-world networks. This
algorithm first randomizes the edges between different communities according
to a configuration model, and then it randomizes the edges inside the
communities. This creates a graph with a similar community structure and
degree distribution as the real-world network. However, this model was only
studied through extensive simulations; the analytical properties of this model
were not studied in [20].

In this paper, we introduce the hierarchical configuration model, a random
graph model that can describe networks with an arbitrary community structure.
This model has a hierarchical structure that consists of two levels. The
macroscopic level consists of the connections between communities, and the
microscopic level describes the connections inside communities. Like in [1]
and [4], we study a random graph which is a configuration model on the
macroscopic level, and then add communities on the microscopic level. In real-
world networks, however, communities do not have to be complete graphs,
especially when the communities are large, as is typically observed through
community detection algorithms [8]. We generalize the setting of [1] and [4]
to a configuration model in which a vertex can be replaced by any small graph.
This generalization makes it possible to apply the hierarchical configuration
model to real-world data sets. When the community structure of a real-world
network is detected by an algorithm, the hierarchical configuration model is
able to produce random graphs that have a similar community structure.
Furthermore, due to the general community structure of the hierarchical
configuration model, several existing random graph models turn out to be
special cases. The model developed in [12] is similar to our model, but in
contrast to the hierarchical configuration model, it only allows for a finite
number of different communities, and all communities have to be of constant
size. The advantage of the hierarchical configuration model is that it is
quite flexible in its local structure, yet it is still analytically tractable
due to its mesoscopic locally tree-like structure. In [22, 21], we have
further studied how this model fits real-world networks, the conclusion being
that our model fits quite well. This is an important step to come to more
realistic random graph models for real-world networks.

This paper is organized as follows. In Section 1.1 we define the hierarchical
configuration model. Section 2 presents several analytical results for the
hierarchical configuration model, including the condition for a giant
component to emerge, the degree distribution and the clustering coefficient.
In Section 3 we study bond percolation on the hierarchical configuration
model. Section 4 describes examples of graph models in the literature that fit
into our general framework. Then we show in Section 5 how some stylized
community structures affect percolation. Finally, we present some conclusions
in Section 6.

##### Notation.

We use $\overset{d}{\longrightarrow}$ for convergence in distribution, and
$\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}$ for convergence in
probability. We say that a sequence of events $(\mathcal{E}_{n})_{n\geq 1}$
happens with high probability (w.h.p.) if
$\lim_{n\to\infty}\mathbb{P}(\mathcal{E}_{n})=1$. Furthermore, we write
$f(n)=o(g(n))$ if $\lim_{n\to\infty}f(n)/g(n)=0$, and $f(n)=O(g(n))$ if
$|f(n)|/g(n)$ is uniformly bounded, where $(g(n))_{n\geq 1}$ is nonnegative.
We say that $X_{n}=O_{\scriptscriptstyle{\mathbb{P}}}(b_{n})$ for a sequence
of random variables $(X_{n})_{n\geq 1}$ if $|X_{n}|/b_{n}$ is a tight sequence
of random variables, and $X_{n}=o_{\scriptscriptstyle{\mathbb{P}}}(b_{n})$ if
$X_{n}/b_{n}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}0$. Table
1, at the end of this paper, contains a list of symbols that are used
frequently throughout the manuscript.

###  1.1 Hierarchical configuration model

We now describe the random graph model that we introduce and study in this
paper. Consider a random graph $G$ with $n$ communities. A community $H$ is
represented by $H=(F,(d_{v}^{\scriptscriptstyle{(b)}})_{v\in V})$, where
$F=(V_{F},E_{F})$ is a simple, connected graph, and
$d_{v}^{\scriptscriptstyle{(b)}}$ is the number of edges from $v\in V_{F}$ to
other communities. Thus $(d_{v}^{\scriptscriptstyle{(b)}})_{v\in V_{F}}$
describes the degrees between the communities. We call
$d_{v}^{\scriptscriptstyle{(b)}}$ the _inter-community degree_ of a vertex. A
vertex inside a community also has an _intra-community degree_
$d_{v}^{\scriptscriptstyle{(c)}}$: the number of edges from that vertex to
other vertices in the same community. The sum of the inside- and the inter-
community degree of the vertex is the degree of the vertex, i.e.,
$d_{v}=d_{v}^{\scriptscriptstyle{(b)}}+d_{v}^{\scriptscriptstyle{(c)}}$. Let
$d_{H}=\sum_{v\in V_{F}}d_{v}^{\scriptscriptstyle{(b)}}$ be the total number
of edges out of community $H$. On the macroscopic level, $G$ is a
configuration model with degrees $d_{H}$. Let this macroscopic configuration
model be denoted by $\phi(G)$.

Let $H_{n}=(F_{n},\boldsymbol{d}_{n})$ denote a uniformly chosen community in
$[n]=\\{1,2,\dots,n\\}$. Furthermore, denote the number of communities of type
$H$ in a graph with $n$ communities by $n^{\scriptscriptstyle{(n)}}_{H}$. Then
$n^{\scriptscriptstyle{(n)}}_{H}/n$ is the fraction of communities that are of
type $H$. Let $D_{n}$ be the number of outgoing edges from a uniformly chosen
community, i.e., $D_{n}=d_{H_{n}}$. Let the size of community $i$ be denoted
by $s_{i}$, and the size of a uniformly chosen community in $[n]$ by
$S_{n}\overset{d}{=}|F_{n}|$. Then the total number of vertices in the graph
is $N=\sum_{i=1}^{n}s_{i}=n\mathbb{E}[S_{n}]$. We assume that the following
conditions hold:

######  Condition 1 (Community regularity).

  1. (i)

$P_{n}(H)=n^{\scriptscriptstyle{(n)}}_{H}/n\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}P(H)$,
where $P(H)$ is a probability distribution,

  2. (ii)

$\lim_{n\to\infty}\mathbb{E}[S_{n}]=\mathbb{E}[S],$

for some random variable $S$ with $\mathbb{E}[S]<\infty$.

######  Condition 2 (Intercommunity connectivity).

  1. (i)

$\lim_{n\to\infty}\mathbb{E}[D_{n}]=\mathbb{E}[D],$

  2. (ii)

$\mathbb{P}(D=2)<1$,

for some random variable $D$ with $\mathbb{E}[D]<\infty$.

Condition 1(i) implies
$(F_{n},\boldsymbol{d}_{n})\overset{d}{\longrightarrow}(F,\boldsymbol{d})$,
$D_{n}\overset{d}{\longrightarrow}D$ and $S_{n}\overset{d}{\longrightarrow}S$,
so that $S$ and $D$ are the asymptotic community size distribution and
community inter-community degree distribution, respectively. Define

$\displaystyle p_{k,s}^{\scriptscriptstyle{(n)}}$
$\displaystyle=\sum_{H=(F,\boldsymbol{d}):|F|=s,d_{H}=k}P_{n}(H),$ (1)
$\displaystyle p_{k,s}$
$\displaystyle=\sum_{H=(F,\boldsymbol{d}):|F|=s,d_{H}=k}P(H),$ (2)

as the probabilities that a uniformly chosen community has size $s$ and inter-
community degree $k$, for finite $n$ and $n\to\infty$, respectively. Then
Condition 1 implies that $p_{k,s}^{\scriptscriptstyle{(n)}}\to p_{k,s}$ for
every $(k,s)$.

We can think of $P_{n}(H)$ as the probability that a uniformly chosen
community has a certain shape. In a data set we can approximate $P_{n}(H)$ and
use the hierarchical configuration model in the following way. Suppose a
community detection algorithm gives the empirical distribution of the
community shapes $P_{n}(H)$. Now we construct a random graph in the way that
was described above. The probability that a certain community is of shape $H$
is $P_{n}(H)$. We condition on the total inter-community degree to be even so
that edges between communities can be formed as in a configuration model. This
results in a graph with roughly the same degree sequence as the original
graph. Additionally, the community structure in the random graph is the same
as in the original graph. This construction preserves more of the microscopic
features of the original graph than a standard configuration model with the
same degree sequence as the original graph. It also shows the necessity of
extending the work of [4, 23] to go beyond the assumption that communities are
complete graphs, because communities in real-world networks can be non-
complete. Using this construction, the hierarchical configuration model can
match the community structure in many complex networks [22, 21].

##  2 Model properties

For a connected component of $G$, we can either count the number of
communities in the component, or the number of vertices in it. We denote the
number of communities in a connected component $\mathscr{C}$ by
$v(\mathscr{C}^{\scriptscriptstyle{\text{H}}})$, and the number of communities
with inter-community degree $k$ by
$v_{k}(\mathscr{C}^{\scriptscriptstyle{\text{H}}})$. The number of vertices in
component $\mathscr{C}$ is denoted by $v(\mathscr{C})$. Let
$\mathscr{C}_{\textup{max}}$ and $\mathscr{C}_{2}$ be the largest and second
largest components of $G$, respectively, so that

$v(\mathscr{C}_{\max})=\max_{u\in[N]}v(\mathscr{C}(u)),$ (3)

where $\mathscr{C}(u)$ denotes the component of vertex $u$. Furthermore,
define $\nu_{D}$ as

$\nu_{D}=\frac{\mathbb{E}[D(D-1)]}{\mathbb{E}[D]},$ (4)

where $D$ is the asymptotic community degree of Condition 2. Let
$p_{k}=\mathbb{P}(D=k)$ and let $g(x)=\sum_{k}p_{k}x^{k}$ be the probability
generating function of $D$, and $g^{\prime}(x)=\sum_{k}kp_{k}x^{k-1}$ its
derivative.

###  2.1 Giant component

In the standard configuration model, a giant component exists w.h.p. if
$\nu_{D}>1$ [14, 17, 16]. In the hierarchical configuration model a similar
statement holds:

######  Theorem 3.

Let $G$ be a hierarchical configuration model satisfying Conditions 1 and 2.
Then,

  1. (i)

If $\nu_{D}>1$,

$\frac{v(\mathscr{C}_{\textup{max}})}{N}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\frac{\sum_{k,s}sp_{k,s}(1-\xi^{k})}{\mathbb{E}[S]}>0,$
(5)

where $\xi$ is the unique solution in $[0,1)$ of
$g^{\prime}(\xi)=\xi\mathbb{E}[D]$. Furthermore,
$v(\mathscr{C}_{2})/N\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}0$.

  2. (ii)

If $\nu_{D}\leq 1$, then
$v(\mathscr{C}_{\textup{max}})/N\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}0$.

###### Proof.

Suppose $\nu_{D}>1$. By [9, Theorem 4.1], if Condition 2 holds,
$D_{n}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}D$ and
$\nu_{D}>1$ in a standard configuration model, then w.h.p. there will be one
component with a positive fraction of the vertices as $n\to\infty$.
Furthermore, the number of vertices in the largest component in a standard
configuration model
$v(\mathscr{C}^{\scriptscriptstyle{\text{CM}}}_{\textup{max}})$ and the number
of vertices of degree $k$ in its largest connected component,
$v_{k}(\mathscr{C}^{\scriptscriptstyle{\text{CM}}}_{\textup{max}})$ satisfy

$\displaystyle
v(\mathscr{C}^{\scriptscriptstyle{\text{CM}}}_{\textup{max}})/n$
$\displaystyle\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}1-g(\xi)>0,$
(6) $\displaystyle
v_{k}(\mathscr{C}^{\scriptscriptstyle{\text{CM}}}_{\textup{max}})/n$
$\displaystyle\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}p_{k}(1-\xi^{k}).$
(7)

If $\nu_{D}\leq 1$, then
$v(\mathscr{C}^{\scriptscriptstyle{\text{CM}}}_{\textup{max}})/n\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}0$.
Therefore, if Conditions 1 and 2 hold and $\nu_{D}>1$ in the hierarchical
configuration model, then there is a component with a positive fraction of the
communities as $n\to\infty$. Hence, we need to prove that the largest
hierarchical component is indeed a large component with size given by (5) if
$\nu_{D}>1$, and that a small hierarchical component is also a small component
of $G$.

We denote the number of communities in the largest hierarchical component with
inter-community degree $k$ and size $s$ by
$v_{k,s}(\mathscr{C}^{\scriptscriptstyle{\text{H}}}_{\text{max}})$. Since $G$
is a configuration model on the community level, (6) and (7) apply on the
community level. Furthermore, given a community in the largest hierarchical
component of inter-community degree $k$, its size is _independent_ of being in
the largest hierarchical component. Moreover,
$\sum_{k}sv_{k,s}(\mathscr{C}^{\scriptscriptstyle{\text{H}}}_{\text{max}})/n\leq\sum_{k}sp_{k,s}^{\scriptscriptstyle{(n)}}$.
Therefore, by Condition 1, the fraction of vertices in the largest
hierarchical component satisfies

$\displaystyle\frac{v(\mathscr{C}_{\textup{max}})}{N}=\frac{\sum_{i\in\mathscr{C}^{\textup{H}}_{\textup{max}}}s_{i}}{\sum_{i}s_{i}}=\frac{\sum_{k,s}n^{-1}sv_{k,s}(\mathscr{C}^{\scriptscriptstyle{\text{H}}}_{\text{max}})}{n^{-1}\sum_{i}s_{i}}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\frac{\sum_{k,s}sp_{k,s}(1-\xi^{k})}{\mathbb{E}[S]}>0.$
(8)

The last inequality follows from Condition 1(ii) and the fact that
$\xi\in[0,1)$ and $s\geq 1$. Now we need to prove that the largest
hierarchical component indeed is the largest component of $G$. We show that a
hierarchical component of size $o_{\mathbb{P}}(n)$ is w.h.p. a component of
size $o_{\mathbb{P}}(N)$. Take a hierarchical component $\mathscr{C}$ which is
not the largest hierarchical component, so that it is of size
$o_{\mathbb{P}}(n)$. Then,

$\displaystyle\frac{v(\mathscr{C})}{N}$
$\displaystyle=\frac{n^{-1}\sum_{k,s}sv_{k,s}(\mathscr{C}^{\scriptscriptstyle{\text{H}}})}{\mathbb{E}[S_{n}]}=\frac{n^{-1}\sum_{s=1}^{K}\sum_{k}sv_{k,s}(\mathscr{C}^{\scriptscriptstyle{\text{H}}})}{\mathbb{E}[S_{n}]}+\frac{n^{-1}\sum_{s>K}\sum_{k}sv_{k,s}(\mathscr{C}^{\scriptscriptstyle{\text{H}}})}{\mathbb{E}[S_{n}]}$
(9) $\displaystyle\leq
K\frac{n^{-1}\sum_{s=1}^{K}\sum_{k}v_{k,s}(\mathscr{C}^{\scriptscriptstyle{\text{H}}})}{\mathbb{E}[S_{n}]}+\frac{\mathbb{E}[S_{n}\mathbbm{1}_{\\{S_{n}>K\\}}]}{\mathbb{E}[S_{n}]}\leq
K\frac{n^{-1}v(\mathscr{C}^{\scriptscriptstyle{\text{H}}})}{\mathbb{E}[S_{n}]}+\frac{\mathbb{E}[S_{n}\mathbbm{1}_{\\{S_{n}>K\\}}]}{\mathbb{E}[S_{n}]}.$

First we take the limit for $n\to\infty$, and then we let $K\to\infty$. By
[14],
$v(\mathscr{C}^{\scriptscriptstyle{\text{H}}})/n\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}0$,
hence the first term tends to zero as $n\to\infty$. Furthermore,
$\mathbb{E}[S_{n}\mathbbm{1}_{\\{S_{n}>K\\}}]\to\mathbb{E}[S\mathbbm{1}_{\\{S>K\\}}]$
as $n\to\infty$ by Condition 1. By Condition 1(ii), this tends to zero as
$K\to\infty$. Thus,
$v(\mathscr{C})/N\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}0$.
Since (9) is uniform in $\mathscr{C}$, this proves that the largest
hierarchical component is indeed the largest component of $G$. This also
proves (ii), since by [9, Theorem 4.1], if $\nu_{D}\leq 1$,
$v(\mathscr{C}^{\scriptscriptstyle{\text{H}}}_{\text{max}})=o_{\mathbb{P}}(n)$,
so that $v(\mathscr{C}_{\textup{max}})=o_{\mathbb{P}}(N)$. ∎

We conclude that if Conditions 1 and 2 hold and $\nu_{D}>1$, then a giant
component exists in the hierarchical configuration model. Equation (5) gives
the fraction of vertices in the largest component. The fraction of vertices in
the giant component may be different from the fraction of communities in the
giant hierarchical component. If the sizes and the inter-community degrees of
the communities are independent, then the fraction of vertices in the largest
component is equal to the fraction of communities in the largest hierarchical
component.

######  Corollary 4.

Suppose that in the hierarchical configuration model $G$ satisfying Conditions
1 and 2, the size of the communities and the inter-community degrees of the
communities are independent. Then, if $\nu_{D}>1$,

$\displaystyle\frac{v(\mathscr{C}_{\textup{max}})}{N}$
$\displaystyle\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}1-g(\xi),$
(10) $\displaystyle\frac{v(\mathscr{C}^{\textup{H}}_{\textup{max}})}{n}$
$\displaystyle\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}1-g(\xi),$
(11)

where $\xi$ is the unique solution in $[0,1)$ of
$g^{\prime}(\xi)=\xi\mathbb{E}[D]$. Hence the fraction of vertices in the
largest component is equal to the fraction of communities in the largest
hierarchical component. If the size and the inter-community degrees are
dependent, then this does not have to be true.

###### Proof.

The equality in (11) is given by [9, Theorem 4.1]. The equality in (10)
follows by substituting $p_{k,s}=p_{k}p_{s}$ in (5), so that

$\frac{v(\mathscr{C}_{\textup{max}})}{N}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\frac{\sum_{s}sp_{s}\sum_{k}p_{k}(1-\xi^{k})}{\mathbb{E}[S]}=\frac{\mathbb{E}[S](1-\sum_{k}p_{k}\xi^{k})}{\mathbb{E}[S]}=1-g(\xi).$
(12)

To show that (10) may not hold when the inter-community degrees and the sizes
are dependent, consider the hierarchical configuration model with

$p_{k,s}=\begin{cases}\frac{1}{3}&\text{if }(k,s)=(3,10),\\\
\frac{2}{3}&\text{if }(k,s)=(1,1).\end{cases}$ (13)

Since $\nu_{D}=\tfrac{6}{5}>1$, a giant component exists w.h.p. Furthermore,
$\xi$ solves

$\tfrac{2}{3}+\xi^{2}=\tfrac{5}{3}\xi,$ (14)

which has $\tfrac{2}{3}$ as its only solution in $[0,1)$. Therefore, the
fraction of communities in the largest component is given by
$1-g(\frac{2}{3})=\frac{37}{81}$. To find the fraction of vertices in the
largest component, we use (5), which gives

$\tfrac{1}{4}(\tfrac{2}{3}(1-\tfrac{1}{2})+10\tfrac{1}{3}(1-(\tfrac{1}{2})^{3}))=\tfrac{13}{16}>\tfrac{37}{81}.$
(15)

Thus, the fraction of vertices in the largest component is larger than the
fraction of communities in the largest component. ∎

If there is a difference between the fraction of communities and the fraction
of vertices in the largest component, then this difference is caused by the
dependence of the sizes and the inter-community degrees of the communities. A
community with a large inter-community degree has a higher probability of
being in the largest hierarchical component than a community with a small
inter-community degree. In the example in the proof of Corollary 4, the
communities with large inter-community degrees are large communities. This
causes the fraction of vertices in the largest component to be larger than the
fraction of communities in the largest hierarchical component.

###  2.2 Degree distribution

In the hierarchical configuration model, the macroscopic configuration model
has a fixed degree sequence. The degree distribution of $G$ depends on the
sizes and shapes of the communities. Let $n_{k}^{\scriptscriptstyle{(H)}}$
denote the number of vertices in community $H$ with the sum of their intra-
community degree and inter-community degree equal to $k$. Then the degree
distribution of the total graph $G$ is described in Proposition 5:

######  Proposition 5.

Let $G$ be a hierarchical configuration model such that Conditions 1 and 2
hold. The asymptotic probability $\hat{p}_{k}$ that a randomly chosen vertex
inside $G$ has degree $k$ satisfies

$\hat{p}_{k}=\frac{\sum_{H}P(H)n_{k}^{\scriptscriptstyle{(H)}}}{\mathbb{E}[S]},$
(16)

as $n\to\infty$.

###### Proof.

Consider a hierarchical configuration model $G$ on $n$ communities. Let
$n^{\scriptscriptstyle{(n)}}_{H}$ be the number of communities in $G$ of type
$H$. The total number of vertices of degree $k$ is the sum of the number of
degree $k$ vertices inside all communities, hence it equals
$\sum_{H}n^{\scriptscriptstyle{(n)}}_{H}n_{k}^{\scriptscriptstyle{(H)}}$.
Furthermore, $P_{n}(H)n^{\scriptscriptstyle{(H)}}_{k}\leq P_{n}(H)s_{H}$, so
that
$\lim_{n\to\infty}\sum_{H}P_{n}(N)n_{k}^{\scriptscriptstyle{(H)}}=\sum_{H}P(H)n_{k}^{\scriptscriptstyle{(H)}}$
by Condition 1. This gives

$\hat{p}_{k}^{\scriptscriptstyle{(n)}}=\frac{n^{-1}\sum_{H}n_{H}n^{\scriptscriptstyle{(H)}}_{k}}{n^{-1}N}=\frac{\sum_{H}P_{n}(H)n^{\scriptscriptstyle{(H)}}_{k}}{\mathbb{E}[S_{n}]}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\hat{p}_{k},$
(17)

as $n\to\infty$. ∎

####  2.2.1 Power-law shift in dense communities

Proposition 5 shows that the inter-community degree distribution and the
degree distribution of the graph may be different. A case of special interest
is when the degree distribution follows a power law. Let $F_{X_{n}}(k)$ be the
empirical distribution function of $n$ observations. Then we say that $X_{n}$
follows a power law with exponent $\tau$ if $0<c_{1}<c_{2}$ and $k_{n}$ exist
such that

$\displaystyle 1-F_{X_{n}}(k)$ $\displaystyle\geq
c_{1}k^{-\tau+1}\quad\quad\forall k\leq k_{n},$ (18) $\displaystyle
1-F_{X_{n}}(k)$ $\displaystyle\leq c_{2}k^{-\tau+1}\quad\quad\forall k,$ (19)

where $k_{n}\to\infty$ as $n\to\infty$. Note that (18) cannot be true for all
$k$ and $X_{n}=D_{n}$, since $c_{1}k^{-\tau+1}<0$, and $1-F_{X_{n}}(k)=0$ for
$k>\max_{i\in[n]}d_{i}^{\scriptscriptstyle{(b)}}$.

In the case of a power-law degree distribution, the degree distribution and
the community size distribution can be related when the communities are dense
enough. We call a community $H$ $(\eta,\varepsilon)$-dense if

$\\#\left\\{v\in
H:d_{v}^{\scriptscriptstyle{(c)}}\geq\eta(s-1)\right\\}\geq\varepsilon s.$
(20)

This condition states that at least a fraction of $\varepsilon$ of the
vertices of community $H$ have edges to at least a fraction of $\eta$ other
vertices in the same community. The special case in which $\varepsilon=\eta=1$
corresponds to complete graph communities. We now show that for dense
communities, the power-law exponents of the community sizes and the degree
distribution are related. For the special case of household communities, this
relation was already observed in [23].

######  Proposition 6.

Let $G$ be a hierarchical configuration model such that Conditions 1 and 2
hold. Suppose that there exists a $K\geq 0$ such that
$d^{\scriptscriptstyle{\textup{(b)}}}\leq Ks$ for all vertices, where $s$ is
the community size. Furthermore, assume that there exist $\varepsilon,\eta>0$
such that every community of $G$ is $(\eta,\varepsilon)$-dense. Then, the
community size distribution $S$ follows a power-law distribution with exponent
$\tau^{\prime}$ with $\tau^{\prime}>2$ if and only if the degree distribution
follows a power law with exponent $\tau=\tau^{\prime}-1$ where $\tau>1$.

###### Proof.

First, assume that $S_{n}$ obeys a power law with exponent $\tau^{\prime}>2$,
so that for some $0<b_{1}<b_{2}$ and $k_{n}$, $b_{1}k^{-\tau^{\prime}+1}\leq
1-F_{S_{n}}(k)$ for all $k\leq k_{n}$ and $1-F_{S_{n}}(k)\leq
b_{2}k^{-\tau^{\prime}+1}$ for all $k$. Then the cumulative distribution
function of the degrees $\hat{D}_{N}$ in a hierarchical configuration model
$G$ on $N$ vertices, $F_{\hat{D}_{N}}(k)$, satisfies

$\displaystyle 1-F_{\hat{D}_{N}}(k)$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}\\{d_{i}\geq
k\\}=\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}\\{d_{i}^{\scriptscriptstyle{\text{(c)}}}+d_{i}^{\scriptscriptstyle{\text{(b)}}}\geq
k\\}\geq\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}\\{d_{i}^{\scriptscriptstyle{\text{(c)}}}\geq
k\\}$ (21)
$\displaystyle\geq\frac{\varepsilon}{N}\sum_{i=1}^{N}\mathbbm{1}\\{\eta(s_{i}-1)\geq
k\\}=\frac{\varepsilon}{n\mathbb{E}[S_{n}]}\sum_{i=1}^{n}s_{i}\mathbbm{1}\\{s_{i}\geq\frac{k}{\eta}+1\\}$
$\displaystyle\geq\frac{\varepsilon}{n\mathbb{E}[S_{n}]}\sum_{i=1}^{n}\frac{k}{\eta}\mathbbm{1}\\{s_{i}\geq\frac{k}{\eta}+1\\}=\frac{k\varepsilon}{\eta}\left(1-F_{S_{n}}(k/\eta+1)\right)$
$\displaystyle\geq\varepsilon c_{1}(\eta)k^{-\tau^{\prime}+2}=\varepsilon
c_{1}(\eta)k^{-\tau+1}\quad\quad\quad\forall k\leq k_{n}\eta,$

where $c_{1}(\eta)$ is a constant depending on $\eta$. Because the communities
are simple, $d^{\scriptscriptstyle{(c)}}_{i}\leq s_{i}-1$ for all vertices.
Hence,

$\displaystyle 1-F_{\hat{D}_{N}}(k)$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}\\{d_{i}^{\scriptscriptstyle{\text{(c)}}}+d_{i}^{\scriptscriptstyle{\text{(b)}}}\geq
k\\}\leq\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}\\{(s_{i}-1)+s_{i}K\geq k\\}$ (22)
$\displaystyle=\frac{1}{n\mathbb{E}[S_{n}]}\sum_{i=1}^{n}s_{i}\mathbbm{1}\\{s_{i}\geq\frac{k+1}{K+1}\\}=\frac{1}{\mathbb{E}[S_{n}]}\mathbb{E}[S_{n}\mathbbm{1}\\{S_{n}\geq\frac{k+1}{K+1}\\}]$
$\displaystyle=\frac{1}{\mathbb{E}[S_{n}]}\left(\frac{k+1}{K+1}\left(1-F_{S_{n}}\left(\frac{k+1}{K+1}\right)\right)+\sum_{j\geq(k+1)/(K+1)}(1-F_{S_{n}}(j))\right)$
$\displaystyle\leq c_{2}(K)k^{-\tau^{\prime}+2}=c_{2}(K)k^{-\tau+1},$

for all $k$, with $c_{2}(K)$ a constant depending on $K$. Here
$\sum_{j\geq(k+1)/(K+1)}(1-F_{S_{n}}(j))\leq c(K)k^{-\tau^{\prime}+2}$ since
$1-F_{S_{n}}(j)\leq b_{2}k^{-\tau^{\prime}+1}$ and $\tau^{\prime}>2$. Taking
the limit of $N\to\infty$, equation (21) and (22) imply that the degree
distribution of $G$ follows a power law with exponent $\tau$, which proves the
first part.

Now assume that the degree distribution $\hat{D}_{N}$ of $G$ obeys a power law
with exponent $\tau$, so that $0<b_{3}<b_{4}$ and $k_{N}$ exist such that (18)
and (19) are satisfied. Then the community sizes are minimized if each
community is a complete graph, and each vertex has inter-community degree
exactly $Ks_{i}$. Then, $d_{v}=(s_{i}-1)+Ks_{i}$ or $s_{i}=(d_{v}+1)/(K+1)$.
Hence, the cumulative distribution of $S_{n}$ in a graph with $n$ communities,
$F_{S_{n}}$, satisfies

$\displaystyle 1-F_{S_{n}}(k)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\\{s_{i}\geq
k\\}\geq\frac{\mathbb{E}[S_{n}]}{N}\sum_{i=1}^{N}\frac{K+1}{d_{i}+1}\mathbbm{1}\left\\{\frac{d_{i}+1}{K+1}\geq
k\right\\}$ (23)
$\displaystyle=\frac{\mathbb{E}[S_{n}]}{N}\sum_{i=1}^{N}\frac{K+1}{d_{i}+1}\mathbbm{1}\\{d_{i}\geq
k(K+1)-1\\}={\mathbb{E}[S_{n}](K+1)}\mathbb{E}\left[\frac{\mathbbm{1}\\{\hat{D}_{N}\geq
k(K+1)-1\\}}{\hat{D}_{N}+1}\right]$
$\displaystyle={\mathbb{E}[S_{n}](K+1)}\mathbb{P}(\hat{D}_{N}>k(K+1)-1)\mathbb{E}[1/(\hat{D}_{N}+1)\mid\hat{D}_{N}\geq
k(K+1)-1]$
$\displaystyle\geq{\mathbb{E}[S_{n}](K+1)}\frac{\mathbb{P}(\hat{D}_{N}>k(K+1)-1)}{\mathbb{E}[\hat{D}_{N}+1\mid\hat{D}_{N}\geq
k(K+1)-1]}$
$\displaystyle={\mathbb{E}[S_{n}](K+1)}\frac{\mathbb{P}(\hat{D}_{N}>k(K+1)-1)^{2}}{\mathbb{E}[(\hat{D}_{N}+1)\mathbbm{1}\\{\hat{D}_{N}+1\geq
k(K+1)\\}]},$

where we use that $\mathbb{E}[1/X]\geq 1/\mathbb{E}[X]$. The term in the
denominator satisfies

$\displaystyle{\mathbb{E}[(\hat{D}_{N}+1)\mathbbm{1}\\{\hat{D}_{N}+1\geq
k(K+1)\\}]}$ $\displaystyle\leq
k(K+1)\mathbb{P}(\hat{D}_{N}+1>k(K+1))+\sum_{j\geq
k(K+1)}\mathbb{P}(\hat{D}_{N}+1\geq j)$ $\displaystyle\leq
C(K)b_{4}(k(K+1))^{-\tau+2},$ (24)

for all $k$, where $C(K)$ is a constant depending on $K$. Combining (23) and
(2.2.1) yields

$\displaystyle 1-F_{S_{n}}(k)$
$\displaystyle\geq{\mathbb{E}[S_{n}](K+1)}\frac{b_{3}(k(K+1))^{-2(\tau+1)}}{b_{4}(k(K+1))^{-\tau+2}C(K)}\geq
c_{3}(K)k^{-\tau}=c_{3}(K)k^{-\tau^{\prime}+1},$ (25)

for all $k\leq k_{N}/(K+1)$, where $c_{3}(K)$ is a constant depending on $K$.
We also have

$\displaystyle 1-F_{S_{n}}(k)$
$\displaystyle=\frac{\mathbb{E}[S_{n}]}{N}\sum_{i=1}^{N}\frac{1}{s_{i}}\mathbbm{1}\\{s_{i}\geq
k\\}\leq\frac{\mathbb{E}[S_{n}]}{N}\sum_{i=1}^{N}\frac{1}{k}\mathbbm{1}\\{s_{i}\geq
k\\}\leq\frac{\mathbb{E}[S_{n}]}{\varepsilon
N}\sum_{i=1}^{N}\frac{1}{k}\mathbbm{1}\\{d_{i}^{\scriptscriptstyle{(c)}}\geq
k\eta\\}$ (26) $\displaystyle\leq\frac{\mathbb{E}[S_{n}]}{\varepsilon
N}\sum_{i=1}^{N}\frac{1}{k}\mathbbm{1}\\{d_{i}^{\scriptscriptstyle{(c)}}+d_{i}^{\scriptscriptstyle{(b)}}\geq
k\eta\\}\leq\frac{1}{\varepsilon}c_{4}(\eta)k^{-\tau}=\frac{1}{\varepsilon}c_{4}(\eta)k^{-\tau^{\prime}+1},$

for all $k$. Taking the limit of $n\to\infty$ proves that $S$ has a power-law
distribution with exponent $\tau^{\prime}=\tau+1$. ∎

Proposition 6 relates the degree distribution to the community size
distribution of the hierarchical configuration model. Under a more restrictive
assumption on the inter-community degrees of individual vertices, this also
establishes a similar relation between the degree distribution of $G$ and the
inter-community degree distribution of the communities in case of a power-law
degree distribution:

######  Corollary 7.

Let $G$ be a hierarchical configuration model satisfying Conditions 1 and 2.
Suppose that there exists a $K\geq 0$ such that
$d_{v}^{\scriptscriptstyle{(b)}}\leq K$ for all vertices $v$. Furthermore,
assume that there exist $\varepsilon,\eta>0$ such that every community of $G$
is $(\eta,\varepsilon)$-dense. Then, the inter-community degree distribution
of $G$ cannot have a power-law distribution with exponent smaller than
$\tau+1$ if the degree distribution of $G$ follows a power-law distribution
with exponent $\tau$, where $\tau>1$.

###### Proof.

By Proposition 6, $S$ follows a power law with exponent $\tau+1$. Since
$d_{v}^{\scriptscriptstyle{(c)}}\leq K$, also $d_{H_{i}}\leq Ks_{i}$ for all
communities $H_{i}$. Therefore, $D\preceq KS$, and hence $D$ cannot have a
power-law distribution with exponent smaller than $\tau+1$. ∎

Corollary 7 shows that the degrees between communities have smaller tails than
the degrees of the graph. This is consistent with our view of communities
being highly connected, while edges between communities are more scarce. For
example, if the degree distribution follows a power law with $\tau\in(2,3)$,
then the inter-community degree distribution has an exponent that is at least
3. Therefore, the inter-community degree distribution has finite variance,
whereas the degree distribution has infinite variance. A property of
configuration models with power-law exponents in (2,3) is that the probability
of obtaining a simple graph vanishes. However, the inter-community connections
in the hierarchical configuration model have exponent larger than 3, so that
the probability of obtaining a simple graph remains uniformly positive. This
suggests that the hierarchical configuration model is able to produce a random
graph which has a positive probability of being simple, while the degree
distribution has an exponent in (2,3).

In a companion paper [22], we study these power-law relations in more detail,
and we show that in the case of communities that are less dense, different
relations between $\tau$ and $\tau^{\prime}$ may hold.

####  2.2.2 The probability of obtaining a simple graph

In the standard configuration model, the probability of obtaining a simple
graph converges to $\mathrm{e}^{-\nu/2-\nu^{2}/4}$ under the condition that
$\mathbb{E}[D^{2}]<\infty$ [10]. In the hierarchical configuration model, the
probability of obtaining a simple graph is largely dependent on the shapes of
the communities. Since we have assumed that the communities are simple, only
the inter-community edges can create self-loops and multiple edges.

Suppose that each vertex in a community has at most one half-edge to other
communities, i.e.,$d_{v}^{\scriptscriptstyle{(b)}}\in\\{0,1\\}$. A double edge
in the macroscopic configuration model corresponds to a community where two
vertices have an edge to the same other community. Since
$d_{v}^{\scriptscriptstyle{(b)}}\in\\{0,1\\}$, a double edge in the
macroscopic configuration model cannot correspond to a double edge in the
hierarchical configuration model. A self-loop in the macroscopic configuration
model corresponds to an edge from one vertex $v$ inside a community to another
vertex $w$ inside the same community. This self-loop in the macroscopic
configuration model corresponds to a double edge in the hierarchical
configuration model if an edge from $v$ to $w$ was already present in the
community. Thus, when $d_{v}^{\scriptscriptstyle{(b)}}\in\\{0,1\\}$ the
probability that the macroscopic configuration model is simple is lower
bounded by the probability that no self-loops exist in the macroscopic
configuration model,

$\liminf_{n\to\infty}\mathbb{P}\left(G_{n}\text{
simple}\right)\geq\textrm{e}^{-\nu_{D}/2}.$ (27)

In the case of complete graph communities, every self-loop of the macroscopic
configuration model corresponds to a double edge in the hierarchical
configuration model. Therefore, equality holds when all communities are
complete graphs.

###  2.3 Clustering coefficient

The clustering coefficient $C$ of a random graph is defined as

$C=\frac{3\times\text{number of triangles}}{\text{number of connected
triples}}.$ (28)

A connected triple is a vertex with edges to two different other vertices.
Note that the order of the vertices to which the middle vertex is connected
does not matter. The clustering coefficient can thus be interpreted as the
proportion of connected triples that are triangles. In the standard
configuration model, the clustering coefficient tends to zero when
$\mathbb{E}[D^{2}]<\infty$ [19]. Thus, in the hierarchical configuration
model, we expect that the clustering is entirely caused by triangles inside
communities.

Another measure of clustering is the local clustering coefficient for vertices
of degree $k$. This coefficient can be interpreted as the fraction of
neighbors of degree $k$ vertices that are directly connected and is defined as

$C_{k}=\frac{\text{number of pairs of connected neighbors of degree $k$
vertices}}{k(k-1)/2\times\text{number of degree }k\text{ vertices}}.$ (29)

As in Section 2.2, let $n_{k}^{\scriptscriptstyle{(H)}}$ denote the number of
vertices in community $H$ with degree equal to $k$. Furthermore, let
$P_{v}^{\scriptscriptstyle{(H)}}$ denote the number of pairs of neighbors of a
vertex $v\in V_{H}$ within community $H$ that are also neighbors of each
other. We denote the clustering coefficient of community $H$ by $C_{H}$. Every
vertex $v$ in community $H$ has
$d_{v}^{\scriptscriptstyle{(c)}}(d_{v}^{\scriptscriptstyle{(c)}}-1)/2$ pairs
of neighbors inside $H$. Hence, the total number of connected triples inside
the community is given by $\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(c)}}(d_{v}^{\scriptscriptstyle{(c)}}-1)/2$.
Then, by (28),

$C_{H}=\frac{2\sum_{v\in V_{H}}P_{v}^{\scriptscriptstyle{(H)}}}{\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(c)}}(d_{v}^{\scriptscriptstyle{(c)}}-1)}.$
(30)

Proposition 8 states that the clustering coefficient of the hierarchical
configuration model can be written as a combination of the clustering
coefficients inside communities. Let $\hat{D}$ denote the asymptotic degree as
in Proposition 5.

######  Proposition 8.

Let $G$ be a hierarchical configuration model satisfying Conditions 1 and 2,
$\lim_{n\to\infty}\mathbb{E}[D_{n}^{2}]=\mathbb{E}[D^{2}]<\infty$ and
$\lim_{N\to\infty}\mathbb{E}[\hat{D}_{N}^{2}]=\mathbb{E}[\hat{D}^{2}]<\infty$.
Then the clustering coefficient $C^{\scriptscriptstyle{(n)}}$ and average
clustering coefficient for vertices of degree $k$,
$C_{k}^{\scriptscriptstyle{(n)}}$, satisfy

$\displaystyle C^{\scriptscriptstyle{(n)}}$
$\displaystyle\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}C:=\frac{2\sum_{H}\sum_{v\in
V_{H}}P(H)C_{H}d_{v}^{\scriptscriptstyle{(c)}}(d_{v}^{\scriptscriptstyle{(c)}}-1)}{\sum_{H}\sum_{v\in
V_{H}}P(H)d_{v}(d_{v}-1)},$ (31) $\displaystyle
C_{k}^{\scriptscriptstyle{(n)}}$
$\displaystyle\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}C_{k}:=\frac{2\sum_{H}\sum_{v\in
V_{H}:d_{v}=k}P(H)P_{v}^{\scriptscriptstyle{(H)}}}{k(k-1)}.$ (32)

###### Proof.

In the hierarchical configuration model, the number of triples is
deterministic. A vertex $v$ with degree $d_{v}$ has $d_{v}(d_{v}-1)/2$ pairs
of neighbors. Thus, the total number of connected triples in $G$ is given by
$\sum_{H}n^{\scriptscriptstyle{(n)}}_{H}\sum_{v\in V_{H}}d_{v}(d_{v}-1)/2$,
where $n^{\scriptscriptstyle{(n)}}_{H}$ is the number of type $H$ communities.

Triangles in $G$ can be formed in several ways. First of all, a triangle can
be formed by three edges inside the same community. In this case the triangle
in $G$ is formed by a triangle in one of its communities $H$. Another
possibility to create a triangle is shown in Figure 1(a). The black edges show
edges inside a community, and the dashed edges are formed by edges in the
macroscopic configuration model. This triangle is formed by two intra-
community edges, and one edge of the macroscopic configuration model. Figure
2(a) shows that this inter-community edge is a self-loop of the macroscopic
configuration model. One self-loop of the macroscopic configuration model can
create multiple triangles; at most $s_{i}-2$. Figure 1(b) shows the case where
only one edge of the triangle is an intra-community edge. Figure 2(b) shows
that the two inter-community edges must form a double edge in the macroscopic
configuration model. The last possibility is that all three edges of the
triangle are inter-community edges as in Figure 1(c). This corresponds to a
triangle in the macroscopic configuration model (Figure 2(c)).

(a) self-loop

(b) double edge

(c) triangle

Figure 1: Possibilities to form triangles in the hierarchical configuration
model that are not entirely inside communities. Edges between communities
(dashed) that add clustering correspond to either a self-loop, a double edge
or a triangle in the macroscopic configuration model.

(a) self-loop

(b) double edge

(c) triangle

Figure 2: Figure 1 on macroscopic level. The inter-community edges that add
clustering correspond to either a self-loop, a double edge or a triangle of
the macroscopic configuration model.

Hence, either the triangle was present in $H$ already, or it corresponds to a
double edge, self-loop or triangle in $\phi(G)$. Here we recall that $\phi(G)$
denotes the macroscopic configuration model. Let the number of self-loops,
double edges and triangles in $\phi(G)$ be denoted by
$W^{\scriptscriptstyle{(n)}},M^{\scriptscriptstyle{(n)}}$ and
$T^{\scriptscriptstyle{(n)}}$ respectively. Denote the number of triangles
entirely in communities of $G$ by $T^{\scriptscriptstyle{(n)}}_{\text{com}}$.
The number of triangles in $G$ is bounded from below by
$T_{\text{com}}^{\scriptscriptstyle{(n)}}$. Using (30), we obtain that

$3T_{\text{com}}^{\scriptscriptstyle{(n)}}=\sum_{H}\sum_{v\in
V_{H}}n^{\scriptscriptstyle{(n)}}_{H}P_{v}^{\scriptscriptstyle{(H)}}=\sum_{H}\sum_{v\in
V_{H}}n_{H}C_{H}d_{v}^{\scriptscriptstyle{(c)}}(d_{v}^{\scriptscriptstyle{(c)}}-1).$
(33)

Since $P_{v}^{\scriptscriptstyle{(H)}}\leq d_{v}^{2}$, and
$\lim_{N\to\infty}\mathbb{E}[\hat{D}_{N}]=\mathbb{E}[\hat{D}]$,

$\displaystyle C^{\scriptscriptstyle{(n)}}$
$\displaystyle=\frac{3\times\text{number of triangles in }G}{\text{number of
connected triples in
}G}\geq\frac{3T^{\scriptscriptstyle{(n)}}_{\text{com}}/n}{\sum_{H}n^{\scriptscriptstyle{(n)}}_{H}\sum_{v\in
V_{H}}d_{v}(d_{v}-1)/(2n)}$ (34)
$\displaystyle\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\frac{2\sum_{H}\sum_{v\in
V_{H}}P(H)C_{H}d_{v}^{\scriptscriptstyle{(c)}}(d_{v}^{\scriptscriptstyle{(c)}}-1)}{\sum_{H}\sum_{v\in
V_{H}}P(H)d_{v}(d_{v}-1)}.$

The sums in (34) are finite due to the assumptions $\mathbb{E}[D^{2}]<\infty$
and $\mathbb{E}[\hat{D}^{2}]<\infty$.

For the upper bound, we use that every self-loop on the community level adds
at most $s_{i}-2$ triangles, and every triangle and double edge on the
community level adds at most one triangle. This yields the inequality

$\text{number of triangles }G\leq
T^{\scriptscriptstyle{(n)}}_{\text{com}}+M^{\scriptscriptstyle{(n)}}+S^{\scriptscriptstyle{(n)}}+\sum_{i=1}^{W^{\scriptscriptstyle{(n)}}}(s_{\mathcal{I}_{i}}-2).$
(35)

Here the sum is over all communities where a self-loop is present, written as
$(\mathcal{I}_{i})_{i=1}^{W^{\scriptscriptstyle{(n)}}}$. If a community has
multiple self-loops, then the community is counted multiple times in the sum.
By [2, Theorem 5]

$\left(M^{\scriptscriptstyle{(n)}}+T^{\scriptscriptstyle{(n)}}\right)/n\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}0.$
(36)

in a configuration model with $\mathbb{E}[D^{2}]<\infty$.

The last term in (35) satisfies

$\displaystyle\frac{\sum_{i=1}^{W^{\scriptscriptstyle{(n)}}}(s_{\mathcal{I}_{i}}-2)}{n}$
$\displaystyle=\frac{W^{\scriptscriptstyle{(n)}}\mathbb{E}[S_{n}-2\mid\text{self-
loop}]}{n}\leq\frac{W^{\scriptscriptstyle{(n)}}\max_{i\in[n]}s_{i}}{n}=\frac{W^{\scriptscriptstyle{(n)}}o(n)}{n}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}0.$
(37)

The last equality follows because $\mathbb{E}[S_{n}]\to\mathbb{E}[S]<\infty$,
which implies that

$\lim_{k\to\infty}\lim_{n\to\infty}\frac{1}{n}\sum_{j\in[n]}s_{j}\mathbbm{1}\\{s_{j}>k\\}=0,$
(38)

so that $\max_{i}s_{i}=o(n)$. The convergence follows since the number of
self-loops in a configuration model converges to a Poisson distribution with
mean $\nu_{D}$ [10, Proposition 7.11], combined with
$\mathbb{E}[D^{2}]<\infty$.

Combining (36) and (37) yields

$\displaystyle C^{\scriptscriptstyle{(n)}}$
$\displaystyle\leq\frac{3T^{\scriptscriptstyle{(n)}}_{\text{com}}+3(M^{\scriptscriptstyle{(n)}}+T^{\scriptscriptstyle{(n)}})+3\sum_{i=1}^{W^{\scriptscriptstyle{(n)}}}(s_{\mathcal{I}_{i}}-2)}{\sum_{H}n^{\scriptscriptstyle{(n)}}_{H}\sum_{v\in
V_{H}}d_{v}(d_{v}-1)/2}$
$\displaystyle\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\frac{2\sum_{H}P(H)\sum_{v\in
V_{H}}C_{H}d_{v}^{\scriptscriptstyle{(c)}}(d_{v}^{\scriptscriptstyle{(c)}}-1)}{\sum_{H}P(H)\sum_{v\in
V_{H}}d_{v}(d_{v}-1)}.$ (39)

Together with (34) this proves (31).

To prove (32), a similar argument can be used. The number of connected
neighbors of vertices of degree $k$ is bounded from below by
$\sum_{H}n_{H}^{\scriptscriptstyle{(n)}}\sum_{v\in
V_{H}:d_{v}=k}P_{v}^{\scriptscriptstyle{(H)}}$, and from above by

$\sum_{H}n_{H}^{\scriptscriptstyle{(n)}}\sum_{v\in
V_{H}:d_{v}=k}P_{v}^{\scriptscriptstyle{(H)}}+M^{\scriptscriptstyle{(n)}}+S^{\scriptscriptstyle{(n)}}+\sum_{i=1}^{W^{\scriptscriptstyle{(n)}}}(s_{\mathcal{I}_{i}}-2).$
(40)

Then, dividing by $k(k-1)n\hat{p}_{k}^{\scriptscriptstyle{(n)}}$, where
$\hat{p}_{k}^{\scriptscriptstyle{(n)}}$ is the probability of having a vertex
of degree $k$, and taking the limit yields (32). Note that the assumption that
$\mathbb{E}[\hat{D}^{2}]<\infty$ is not necessary for this clustering
coefficient, since $P_{v}/k(k-1)\leq 1$ for all vertices of degree $k$. ∎

##  3 Percolation

We now consider bond percolation on $G$, where each edge of $G$ is removed
independently with probability $1-\pi$. We are interested in the critical
percolation value and the size of the largest percolating cluster. Percolation
on the configuration model was studied in [6, 13]. Here we extend these
results to the hierarchical configuration model.

Percolating $G$ is the same as first percolating only the edges within
communities, and then percolating the edges between communities. For
percolation inside a community, only the edges inside a community are removed
with probability $1-\pi$. The half-edges attached to a community are not
percolated. Let $H_{\pi}$ denote the subgraph of $H$, where each edge of $H$
has been deleted with probability $1-\pi$. When percolating a community, it
may split into different connected components. Let $g(H,v,l,\pi)$ denote the
probability that the component of $H_{\pi}$ containing $v$ has inter-community
degree $l$. If $H_{\pi}$ is still connected, then the component containing $v$
still has $d_{H}$ outgoing edges for all $v\in V_{H}$. If $H_{\pi}$ is
disconnected, then this does not hold. If one of the components of $H_{\pi}$
has an outgoing edge, each vertex in another component of $H_{\pi}$ cannot
reach that edge. Therefore, a vertex in this other component is connected to
less than $d_{H}$ outgoing edges.

To compute the size of the largest percolating cluster, we need the following
definitions:

$\displaystyle p_{k}^{\prime}$ $\displaystyle:=\frac{\sum_{H}\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}P(H)g(H,v,k,\pi)/k}{\sum_{H}\sum_{v\in
V_{H}}\sum_{l}d_{v}^{\scriptscriptstyle{(b)}}P(H)g(H,v,l,\pi)/l},$ (41)
$\displaystyle h(z)$
$\displaystyle:=\sum_{k=1}^{\infty}kp^{\prime}_{k}z^{k-1},$ (42)
$\displaystyle\lambda$ $\displaystyle:=\sum_{k=0}^{\infty}kp_{k}^{\prime}.$
(43)

The probabilities $(p^{\prime}_{k})_{k\geq 0}$ can be interpreted as the
asymptotic probability distribution of the inter-community degrees of the
connected parts of communities after percolation inside communities. Then
$h(z)$ and $\lambda$ are the derivative of the probability generating function
and the mean of the inter-community degrees of the components of communities
after percolation respectively.

Define $D_{\pi}^{*}$ as the number of inter-community edges after entering a
percolated community from a randomly chosen edge. The probability of entering
at vertex $v$ in community $H$, equals
$P(H){d_{v}^{\scriptscriptstyle{(b)}}}/{\mathbb{E}[D]}$. After entering $H$ at
vertex $v$, there are in expectation $\sum_{k=1}^{D_{H}-1}kg(H,v,k+1,\pi)$
edges to other communities (since one edge was used to enter $H$). Hence,

$\mathbb{E}[D_{\pi}^{*}]=\frac{1}{\mathbb{E}[D]}\sum_{H}P(H)\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}\sum_{k=1}^{D_{H}-1}kg(H,v,k+1,\pi).$
(44)

After percolating the inter-community edges, a fraction of $\pi$ of these
edges remain. Thus, after percolating all edges, when entering a community,
the expected number of outgoing edges excluding the traversed edge is
$\pi\mathbb{E}[D_{\pi}^{*}]$. We expect the critical value of $\pi$ to satisfy
$\pi\mathbb{E}[D_{\pi}^{*}]=1$, i.e., the expected number of edges to other
communities is one, after entering a community from a randomly chosen edge.
The next theorem states that this is indeed the critical percolation value:

######  Theorem 9.

Assume $G$ is a hierarchical configuration model satisfying Conditions 1 and
2. The critical value of the percolation parameter $\pi_{c}$ of $G$ satisfies

$\pi_{c}=\frac{1}{\mathbb{E}[D^{*}_{\pi_{c}}]}.$ (45)

Furthermore:

  1. (i)

For $\pi>\pi_{c}$, the size of the largest component of the percolated graph
satisfies

$\frac{v(\mathscr{C}_{\textup{max}})}{N}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\frac{1}{\mathbb{E}[S]}\sum_{k=1}^{\infty}\sum_{H}\sum_{v\in
V_{H}}P(H)g(H,v,k,\pi)\left(1-(1-\sqrt{\pi}+\sqrt{\pi}\xi)^{k}\right)>0,$ (46)

where $\xi$ is the unique solution in $(0,1)$ of

$\sqrt{\pi}h(1-\sqrt{\pi}+\sqrt{\pi}\xi)+(1-\sqrt{\pi})\lambda=\lambda\xi.$
(47)

  2. (ii)

For $\pi\leq\pi_{c}$,
$v(\mathscr{C}_{\textup{max}})/N\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}0$.

Note that for the standard configuration model, (45) simplifies to
$\pi_{c}=\mathbb{E}[D]/\mathbb{E}[D(D-1)]$, since in that case, for a vertex
of degree $d$, $g(v,v,k,\pi)=\mathbbm{1}_{\\{k=d\\}}$. Furthermore,
$\pi_{c}=0$ when for any $\pi>0$, the expected number of edges to other
communities is infinite when entering a community via a uniformly chosen edge.

###### Proof.

The proof of Theorem 9 has a similar structure as the proof of [4, Theorem 1].
The proof consists of three key steps:

  1. (a)

First, each edge within each community is removed with probability $1-\pi$.
This may split the community into several connected components. We find the
distribution of the inter-community degrees of the connected components of the
percolated communities, which is given by $p^{\prime}_{k}$, as in (41). We
identify vertices that are in the same connected component of a community.
Lemma 10 shows that this results in a graph $\phi(G_{\pi})$ that is
distributed as a configuration model with asymptotic degree probabilities
$p_{k}^{\prime}$ (recall (41)).

  2. (b)

We then remove each edge between communities with probability $1-\pi$. Results
of [13] can now be applied to the configuration model with distribution
$p_{k}^{\prime}$ to find the critical percolation value and the size of the
giant hierarchical component.

  3. (c)

Next, we translate the number of communities in the largest percolated
hierarchical component to the number of vertices. Then we show that this is
indeed the largest component of the percolated graph.

##### Auxiliary graph.

We introduce the auxiliary graph $\phi(\bar{G})$, defined for every subgraph
$\bar{G}\subset G$, and obtained by identifying the vertices that belonged to
the same community in $G$, and are connected in $\bar{G}$ [4]. Hence, in
$\phi(\bar{G})$ every vertex represents a connected part of a community.
Figure 3 illustrates $\phi(\bar{G})$. For a hierarchical configuration model
$G$, the graph $\phi(G)$ is a configuration model where communities of $G$ are
collapsed into single vertices.

Figure 3: Left, a subgraph $\bar{H}$ of a community $H$, dashed lines are not
in $\bar{H}$, but are present in $H$, solid lines are present in $\bar{H}$.
The graph $\phi(\bar{H})$ is shown on the right.

######  Lemma 10.

Let $G$ be a hierarchical configuration model satisfying Conditions 1 and 2.
Let $G_{\pi}$ denote the subgraph of $G$ where each edge inside each community
is removed with probability $1-\pi$. Then the graph $\phi(G_{\pi})$ is
distributed as a configuration model with degree probabilities
$p^{\prime}_{k}$ given in (41).

###### Proof.

We independently delete each edge within each community with probability
$1-\pi$. We want to find the degree distribution of $\phi(G_{\pi})$. Let
$M^{\scriptscriptstyle{(n)}}(H,v,k,\pi)$ denote the number of connected
components of the percolated versions of community $H$ containing vertex $v$
and having inter-community degree $k$. Each community of shape $H$ has an
equal probability that the component containing $v$ has inter-community degree
$k$ given by $g(H,v,k,\pi)$. Furthermore, the probability that a randomly
chosen community has shape $H$ is independent of the probability that the
inter-community degree is $k$ after percolation in a community of shape $H$.
Therefore, given the number of type $H$ communities
$n^{\scriptscriptstyle{(n)}}_{H}$,
$M^{\scriptscriptstyle{(n)}}(H,v,k,\pi)\sim\text{Bin}(n^{\scriptscriptstyle{(n)}}_{H},g(H,v,k,\pi))$.
Thus, by the weak law of large numbers,

$\frac{M^{\scriptscriptstyle{(n)}}(H,v,k,\pi)}{n}=\frac{M^{\scriptscriptstyle{(n)}}(H,v,k,\pi)}{n^{\scriptscriptstyle{(n)}}_{H}}\frac{n^{\scriptscriptstyle{(n)}}_{H}}{n}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}P(H)g(H,v,k,\pi).$
(48)

Let $N^{\scriptscriptstyle{(n)}}(H,k,\pi)$ denote the total number of
connected components of the percolated versions of $H$ having inter-community
degree $k$. This number can be obtained by counting the number of half-edges
of all connected components of percolated graphs with inter-community degree
$k$, and then dividing by $k$. Each vertex $v$ in such a percolated community
contributes $d_{v}^{\scriptscriptstyle{(b)}}$ to the inter-community degree of
the percolated community. Thus,

$N^{\scriptscriptstyle{(n)}}(H,k,\pi)=\sum_{v\in{V_{H}}}d_{v}^{\scriptscriptstyle{(b)}}M^{\scriptscriptstyle{(n)}}(H,v,k,\pi)/k.$
(49)

Let $\tilde{n}$ denote the number of vertices in $\phi(G_{\pi})$, so that
$\tilde{n}=\sum_{H}\sum_{k}N^{\scriptscriptstyle{(n)}}(H,k,\pi)$. Similarly,
the number vertices of degree $k$ in $\phi(G_{\pi})$ is denoted by
$\tilde{n}_{k}=\sum_{H}N^{\scriptscriptstyle{(n)}}(H,k,\pi)$. Furthermore,
$\sum_{k}N^{\scriptscriptstyle{(n)}}(H,k,\pi)/n\leq P_{n}(H)s_{H}$, and
therefore by Condition 1, (48) and (49),

$\tilde{n}/n\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\sum_{H}\sum_{k=1}^{D_{H}}\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}P(H)g(H,v,k,\pi)/k.$ (50)

Therefore also

$\frac{N^{\scriptscriptstyle{(n)}}(H,k,\pi)}{\tilde{n}}=\frac{N^{\scriptscriptstyle{(n)}}(H,k,\pi)/n}{\tilde{n}/n}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\frac{\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}P(H)g(H,v,k,\pi)/k}{\sum_{H}\sum_{v\in
V_{H}}\sum_{l}d_{v}^{\scriptscriptstyle{(b)}}P(H)g(H,v,l,\pi)/l}.$ (51)

Hence, the proportion of vertices in $\phi(G_{\pi})$ with degree $k$ tends to

$\frac{\tilde{n}_{k}}{\tilde{n}}=\sum_{H}\frac{N^{\scriptscriptstyle{(n)}}(H,k,\pi)}{\tilde{n}}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}p_{k}^{\prime}.$
(52)

Since the edges between communities in $G$ were paired at random, this means
that the graph $\phi(G_{\pi})$ is distributed as a configuration model with
degree probabilities $p_{k}^{\prime}$. ∎

Using Lemma 10, we now prove Theorem 9:

Step (a). Lemma 10 proves that $\phi(G_{\pi})$ is distributed as a
configuration model with degree probabilities $p^{\prime}_{k}$.

Step (b). $\phi(G_{\pi})$ and $\phi(G)$ have $\sum_{k}k\tilde{n}_{k}$ and
$\sum_{k}kn_{k}$ half-edges, respectively. Since only edges inside communities
have been deleted, $\sum_{k}kn_{k}$ equals $\sum_{k}k\tilde{n}_{k}$. By
Condition 2(i), $\sum_{k}kn_{k}/n\to\mathbb{E}[D]$. Furthermore, by (50)
$\tilde{n}/n$ converges, hence $\sum_{k}k\tilde{n}_{k}/\tilde{n}$ converges.
Therefore we can apply Theorem 3.9 from [13], which states that after
percolation, a configuration model with degree probabilities $p_{k}^{\prime}$
has a giant component if

$\pi\sum_{k}k(k-1)p_{k}^{\prime}>\sum_{k}kp_{k}^{\prime}.$ (53)

From Theorem 3 we know that a giant hierarchical component is also a giant
component in $G$, and a hierarchical component of size $o_{\mathbb{P}}(n)$ is
a component of size $o_{\mathbb{P}}(N)$. Hence, the giant component emerges
precisely when the giant hierarchical component emerges. Substituting (52)
gives for the critical percolation value $\pi_{c}$ that,

$\displaystyle\pi_{c}$
$\displaystyle=\frac{\sum_{k}kp_{k}^{\prime}}{\sum_{k}k(k-1)p_{k}^{\prime}}=\frac{\sum_{H}\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}\sum_{k=1}^{D_{H}}P(H)g(H,v,k,\pi_{c})k/k}{\sum_{H}\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}\sum_{k=1}^{D_{H}}P(H)g(H,v,k,\pi_{c})k(k-1)/k}$
(54) $\displaystyle=\frac{\sum_{H}\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}P(H)}{\sum_{H}\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}\sum_{k=1}^{D_{H}}P(H)g(H,v,k,\pi_{c})(k-1)}$
$\displaystyle=\frac{\mathbb{E}[D]}{\sum_{H}\sum_{v\in
V_{H}}\sum_{k=1}^{D_{H}-1}d_{v}^{\scriptscriptstyle{(b)}}P(H)g(H,v,k+1,\pi_{c})k}$
$\displaystyle=\frac{1}{\mathbb{E}[D_{\pi_{c}}^{*}]}.$

Step (c). Now assume that $\pi>\pi_{c}$. The number of degree $r$ vertices in
the largest component of $\phi(G_{\pi})$ satisfies
$v_{r}(\mathscr{C}^{\scriptscriptstyle{\text{H}}}_{\text{max}})/\tilde{n}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\sum_{l\geq
r}b_{lr}(\sqrt{\pi})p_{l}^{\prime}(1-\xi^{r})$ [13], with
$b_{lr}(\sqrt{\pi})={l\choose r}\sqrt{\pi}^{r}(1-\sqrt{\pi})^{l-r}$ is the
probability that a binomial with parameters $l$ and $\sqrt{\pi}$ takes value
$r$, and $\xi$ is as in (47). To translate the number of percolated
communities in the largest component into the number of vertices in the
largest component, we want to know the expected number of vertices in the
largest component that are in a percolated community with inter-community
degree $k$. The size of a percolated community is independent of being in the
largest hierarchical component, but does depend on the inter-community degree
of the percolated community. The total number of vertices in connected
percolated components with inter-community degree $k$ is given by
$\sum_{H}\sum_{v\in V_{H}}M^{\scriptscriptstyle{(n)}}(H,v,k,\pi)$, and the
total number of percolated communities of inter-community degree $k$ is given
by $\sum_{H}N^{\scriptscriptstyle{(n)}}(H,k,\pi)$. Furthermore, $\sum_{v\in
V_{H}}M^{\scriptscriptstyle{(n)}}(H,v,k,\pi)/n\leq P_{n}(H)s_{H}$. Hence, by
Condition 2, the expected size of a percolated community, given that it has
inter-community degree $k$, satisfies

$\displaystyle\mathbb{E}[S_{\pi}\mid\text{inter-community degree }k]$
$\displaystyle=\frac{\sum_{H}\sum_{v\in
V_{H}}M^{\scriptscriptstyle{(n)}}(H,v,k,\pi)}{\sum_{H}N^{\scriptscriptstyle{(n)}}(H,k,\pi)}$
(55) $\displaystyle=\frac{\sum_{H}\sum_{v\in
V_{H}}M^{\scriptscriptstyle{(n)}}(H,v,k,\pi)/n}{\sum_{H}N^{\scriptscriptstyle{(n)}}(H,k,\pi)/n}$
$\displaystyle\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\frac{\sum_{H}\sum_{v\in
V_{H}}P(H)g(H,v,k,\pi)}{\sum_{H}\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}P(H)g(H,v,k,\pi)/k}.$

Since
$v_{r}(\mathscr{C}_{\textup{max}})/N\leq\hat{p}_{r}^{\scriptscriptstyle{(n)}}$,
which sums to one, we can compute the asymptotic number of vertices in the
largest component of $\phi(G_{\pi})$ as

$\displaystyle\frac{v(\mathscr{C}_{\textup{max}})}{N}$
$\displaystyle=\sum_{r=0}^{\infty}\frac{v_{r}(\mathscr{C}_{\textup{max}})/\tilde{n}}{N/n\cdot
n/\tilde{n}}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}\sum_{r=0}^{\infty}\frac{\sum_{l\geq
r}b_{lr}(\sqrt{\pi})p_{l}^{\prime}(1-\xi^{r})\mathbb{E}[S_{\pi}\mid\text{inter-
community degree }l]}{\mathbb{E}[S]/\sum_{H}\sum_{v\in
V_{H}}\sum_{k}d_{v}^{\scriptscriptstyle{(b)}}P(H)g(H,v,k,\pi)/k}$
$\displaystyle=\frac{\sum_{r=0}^{\infty}\sum_{l\geq
r}b_{lr}(\sqrt{\pi})(1-\xi^{r})p_{l}^{\prime}}{\mathbb{E}[S]/\sum_{H}\sum_{v\in
V_{H}}\sum_{k}d_{v}^{\scriptscriptstyle{(b)}}P(H)g(H,v,k,\pi)/k}\frac{\sum_{H}\sum_{v\in
V_{H}}P(H)g(H,v,l,\pi)}{\sum_{H}\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}P(H)g(H,v,l,\pi)/l}$
$\displaystyle=\frac{\sum_{l=0}^{\infty}\sum_{r=0}^{l}b_{lr}(\sqrt{\pi})(1-\xi^{r})\frac{p^{\prime}_{l}}{p^{\prime}_{l}}\sum_{H}\sum_{v\in
V_{H}}P(H)g(H,v,l,\pi)}{\mathbb{E}[S]}$
$\displaystyle=\frac{\sum_{l=0}^{\infty}(1-(1-\sqrt{\pi}+\sqrt{\pi}\xi)^{l})\sum_{H}\sum_{v\in
V_{H}}P(H)g(H,v,l,\pi)}{\mathbb{E}[S]}.$ (56)

Any other component of $\phi(G_{\pi})$ has size $o_{\mathbb{P}}(\tilde{n})$ by
[13, Theorem 3.9]. As shown in the proof of Theorem 3, any component of size
$o_{\mathbb{P}}(\tilde{n})$ in $\phi(G_{\pi})$ is a component of size
$o_{\mathbb{P}}(N)$ in the total graph. Hence, w.h.p.
$\mathscr{C}_{\textup{max}}$ is the largest component of the percolated graph
$G_{\pi}$.

When $\pi<\pi_{c}$, the largest component of $\phi(G_{\pi})$ satisfies
$v(\mathscr{C}^{\scriptscriptstyle{\text{H}}}_{\text{max}})/\tilde{n}\overset{\scriptscriptstyle{\mathbb{P}}}{\longrightarrow}0$
[13]. Again, by the analysis of Theorem 3, this component is of size
$o_{\mathbb{P}}(N)$ in the original graph. ∎

Equation (47) also has an intuitive explanation. Let $Q$ be the distribution
of the community inter-community degrees after percolation when following a
randomly chosen half-edge. Then we can interpret $\xi$ as the extinction
probability of a branching process with offspring distribution $Q$.
Percolating the inter-community edges with probability $1-\pi$ is the same as
deleting each half-edge with probability $1-\sqrt{\pi}$. Then, with
probability $1-\sqrt{\pi}$ the randomly chosen half-edge is paired to a
deleted half-edge, in which case the branching process goes extinct. With
probability $\sqrt{\pi}$, the half-edge leads to a half-edge which still
exists after percolation, and leads to a community. The probability generating
function of the number of half-edges pointing out of this community before
percolating the half-edges is $\frac{1}{\lambda}h(\xi)$. Since the number of
half-edges after percolation is binomial given the number of half-edges that
were present before percolation, the probability generating function of the
number of half-edges pointing out of a community entered by a randomly chosen
half-edge is $\frac{1}{\lambda}h(1-\sqrt{\pi}+\sqrt{\pi}\xi)$. Combining this
yields (47).

##### The case $\mathbb{E}[D^{2}]=\infty$.

In the standard configuration model $\pi_{c}=0$ precisely when
$\mathbb{E}[D^{2}]=\infty$. In the hierarchical configuration model, this may
not be true, since it is possible to construct communities with large inter-
community degrees, while all individual vertices have a low degree. An example
of such a community structure is the hierarchical configuration model, where
each community is a line graph $H_{L}$ of $L$ vertices with probability
$\bar{p}_{L}$, where each vertex has inter-community degree one. Figure 4(a)
illustrates $H_{L}$ for $L=5$. We assume that $\bar{p}_{L}$ obeys the power
law $\bar{p}_{L}=cL^{-\alpha}$, with $\alpha\in(2,3)$. Then
$\mathbb{E}[D]<\infty$, but $\mathbb{E}[D^{2}]=\infty$. Hence, communities may
have large inter-community degrees. However, $G$ is a 3-regular graph, so no
individual vertex has high degree. From this fact, we can already conclude
that $\pi_{c}\neq 0$. Suppose $\pi_{c}<\frac{1}{2}$. Then, after percolation
every vertex has less than two expected neighbors. Hence, there is no giant
component w.h.p. We can also use Theorem 9 to show that $\pi_{c}\neq 0$. We
compute the denominator of (45), and show that it is finite. We have

$\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}g(H_{L},v,k,\pi_{c})=\begin{cases}2k\pi_{c}^{k-1}(1-\pi_{c})+k\pi_{c}^{k-1}(1-\pi_{c})^{2}(L-k-1)&\text{if
}k<L,\\\ k\pi_{c}^{k-1}&\text{if }k=L.\end{cases}$ (57)

This gives

$\sum_{k=1}^{L-1}k\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}g(H_{L},v,k+1,\pi_{c})=\frac{2\pi_{c}(\pi_{c}^{L}+L(1-\pi_{c}))-1}{(1-\pi_{c})^{2}}.$
(58)

Using that $\bar{p}_{l}=cl^{-\alpha}$ gives for (44)

$\displaystyle\mathbb{E}[D_{\pi_{c}}^{*}]$
$\displaystyle=\frac{1}{\mathbb{E}[D]}\sum_{H}P(H)\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}\sum_{k=1}^{D_{H}-1}kg(H,v,k+1,\pi_{c})$
$\displaystyle=\frac{1}{\mathbb{E}[D]}\sum_{L=1}^{\infty}cL^{-\alpha}\frac{2\pi_{c}(\pi_{c}^{L}+L(1-\pi_{c}))-1}{(1-\pi_{c})^{2}}$
$\displaystyle=\frac{1}{\mathbb{E}[D]}\frac{2\pi_{c}}{(1-\pi_{c})^{2}}\left(-1+(1-\pi_{c})\mathbb{E}[D]+\sum_{L=1}^{\infty}c\pi_{c}^{L}L^{-\alpha}\right).$
(59)

From (59) we see that $\pi_{c}=0$ is not a solution of (45). Hence,
$\pi_{c}\neq 0$, even though $\mathbb{E}[D^{2}]=\infty$.

(a)

(b)

(c)

Figure 4: Communities with $L=5$.

##### Infinite second moment of degree.

When the second moment of the degree distribution as defined in Proposition 5
is infinite, $\pi_{c}$ also does not have to be zero. It is possible to ‘hide’
all vertices of high degree inside communities that have small inter-community
degrees. The small inter-community degrees make it difficult to leave the
community in percolation. One example of such a community structure is the
case in which each community is a star-shaped graph with $L$ endpoints with
probability $p_{L}$. One vertex in the graph has inter-community degree one,
and all the other vertices have inter-community degree zero. Figure 4(b)
illustrates the star-shaped graph for $L=5$. Since each community has only one
outgoing edge, there cannot be a giant component in $G$. We can also see this
from Theorem 3, since $\mathbb{E}[D]=\mathbb{E}[D^{2}]=1$. By Proposition 5,
the degree distribution equals

$\hat{p}_{k}=\begin{cases}\left(\sum_{L=1}^{\infty}(L-1)p_{L}+p_{1}\right)/\mathbb{E}[S]&\text{if
}k=1,\\\ \left(1+p_{2}\right)\mathbb{E}[S]&\text{if }k=2,\\\
p_{k}/\mathbb{E}[S]&\text{if }k>2.\end{cases}$ (60)

When $p_{l}$ is a probability distribution with infinite second moment, the
second moment of $\hat{p}_{l}$ is also infinite. Hence, the degree
distribution of the hierarchical configuration model $G$ has infinite second
moment, while there is no giant component, so that certainly $\pi_{c}\neq 0$.

##### A sufficient condition for $\pi_{c}=0$.

By (45),

$\displaystyle\pi_{c}$
$\displaystyle=\frac{\mathbb{E}[D]}{\sum_{G}P(H)\sum_{v\in
V_{H}}d_{v}^{\scriptscriptstyle{(b)}}\sum_{k=1}^{D_{H}-1}kg(H,v,k+1,\pi_{c})}$
(61) $\displaystyle\leq\frac{\mathbb{E}[D]}{\sum_{G}P(H)\sum_{v\in
V_{H}}{(d_{v}^{\scriptscriptstyle{(b)}}})^{2}}$

Hence, $\sum_{H}\sum_{v\in
V_{H}}P(H){(d_{v}^{\scriptscriptstyle{(b)}}})^{2}=\infty$ is a sufficient
condition for $\pi_{c}=0$. This condition can be interpreted as an infinite
second moment of the inter-community degrees of individual vertices. However,
it is not a necessary condition. It is possible to construct a community where
all individual vertices have a small inter-community degree, but are connected
to a vertex with high degree. Consider for example the star community of
Figure 4(c), with one vertex in the middle, linked to $L$ other vertices. The
$L$ other vertices have inter-community degree one, and the middle vertex has
inter-community degree zero, hence all vertices have a small inter-community
degree. However, the middle vertex can have a high degree. Let each community
be a star-shaped community with $L$ outgoing edges with probability
$\bar{p}_{L}$. We can calculate that
$\pi_{c}=\sum_{L}\bar{p}_{L}L(L-1)\pi_{c}^{2}$. Hence, if we choose
$\bar{p}_{L}$ with finite first moment and infinite second moment,
$\pi_{c}=0$. However, $\sum_{H}\sum_{v\in
V_{H}}{(d_{v}^{\scriptscriptstyle{(b)}})}^{2}=\sum_{L}L\bar{p}_{L}=\mathbb{E}[D]<\infty$.

##  4 Existing graph models with a community structure

In this section, we show how three existing random graph models with community
structure fit within the hierarchical configuration model.

###  4.1 Trapman’s household model

Trapman [23] replaces vertices in a configuration model by households in the
form of complete graphs, such that the degree distribution of the resulting
graph is $p_{k}$. To achieve this, each community is a single vertex of degree
$k$ with probability $(1-\gamma)p_{k}$, or a complete graph of size $k$ with
probability $\gamma\bar{p}_{k}$. Here $\bar{p}_{k}$, the probability that a
certain clique has degree $k$, is given by

$\bar{p}_{k}=k^{-1}p_{k}\mathbb{E}[W^{-1}]^{-1},$ (62)

where $W$ is a random variable satisfying $\mathbb{P}(W=k)=p_{k}$. Each vertex
of the complete graph has one edge to another community. Figure 5 illustrates
a household of size 5. This model is a special case of the hierarchical
configuration model with

$H_{i}=\begin{cases}(K_{k},(1,\dots,1))&\text{w.p. }\gamma\bar{p}_{k},\\\
(v,(k))&\text{w.p. }(1-\gamma)p_{k},\end{cases}$ (63)

where $K_{k}$ is a complete graph on $k$ vertices.

We now check when (63) satisfies Conditions 1 and 2. The assumption
$\mathbb{P}(D=2)<1$ is satisfied if and only if $p_{2}<1$. The expected inter-
community degree of a community is given by

$\mathbb{E}[D]=(1-\gamma)\sum_{k}kp_{k}+\gamma\sum_{k}k\bar{p}_{k}=(1-\gamma)\mathbb{E}[W]+\frac{\gamma}{\mathbb{E}[W^{-1}]}.$
(64)

Hence, $\mathbb{E}[D]<\infty$ if $\mathbb{E}[W]<\infty$ and
$\mathbb{E}[W^{-1}]\neq 0$. By Jensen’s inequality,
$\mathbb{E}[W^{-1}]\geq\mathbb{E}[W]^{-1}>0$, hence $\mathbb{E}[D]<\infty$ if
and only if $\mathbb{E}[W]<\infty$. For every community in this model, its
size is smaller than or equal to its inter-community degree, so that also
$\mathbb{E}[S]<\infty$ if $\mathbb{E}[D]<\infty$. Thus, Conditions 1 and 2
hold if $\mathbb{E}[W]<\infty$ and $p_{2}<1$. Under these conditions we can
apply the results for the hierarchical configuration model as derived in
Sections 2 and 3.

Suppose that $p_{k}$ follows a power law with exponent $\alpha$. Then
$\bar{p}_{k}$ follows a power law with exponent $\alpha-1$, and the
distribution of the inter-community degrees $D$ is a mixture of a power law
with exponent $\alpha$ and a power law with exponent $\alpha-1$ by (62). Thus,
the power-law shift of Corollary 7 does not occur, since in this household
model, the single vertex communities do not satisfy
$d_{v}^{\scriptscriptstyle{(b)}}\leq K$. For Trapman’s household model, the
power-law shift only occurs if $\gamma=1$, in which case all communities are
households.

Figure 5: A household of size 5

###  4.2 Lelarge and Coupechoux’ household model

Another model that takes complete graphs as communities is the model of
Coupechoux and Lelarge [4]. This model is very similar to Trapman’s model.
Again, each community is either a complete graph or a single vertex. In
contrast to [23], the probability that a certain community is a clique is
dependent on the degree of the clique. Each vertex of degree $k$ in the
macroscopic configuration model is replaced by a complete graph with
probability $\gamma_{k}$. This graph can be modeled as a hierarchical
configuration model with

$H_{i}=\begin{cases}(K_{k},(1,\dots,1))&\text{w.p. }\gamma_{k}\bar{p}_{k}\\\
(v,(k))&\text{w.p. }(1-\gamma_{k})\bar{p}_{k},\end{cases}$ (65)

where $(\bar{p}_{k})_{k\geq 1}$ is a probability distribution. Since the
inter-community degrees of all communities have distribution
$\mathbb{P}(D=k)=\bar{p}_{k}$, Condition 2 holds if the probability
distribution $\bar{p}_{k}$ has finite mean and $\bar{p}_{2}<1$. The size of a
community is always smaller than or equal to its inter-community degree, so
that also $\mathbb{E}[S]<\infty$ if $\bar{p}_{k}$ has finite mean. Thus,
Conditions 1 and 2 hold if $\bar{p}_{k}$ has finite mean and $\bar{p}_{2}<1$.

If these conditions on $\bar{p}_{k}$ hold, then the degree distribution
${p}_{k}$ of the resulting graph can be obtained from Proposition 5 as

${p}_{k}=\frac{(k\gamma_{k}+(1-\gamma_{k}))\bar{p}_{k}}{\sum_{i\geq
0}(i\gamma_{i}+(1-\gamma_{i}))\bar{p}_{i}}.$ (66)

Suppose that $\gamma_{k}\geq\gamma>0$. Then, in contrast to Trapman’s
household model in Section 4.1, the degree distribution of the edges between
communities, $\bar{p}_{k}$, follows a power law with exponent $\alpha+1$ if
the degree distribution ${p}_{k}$ follows a power law with exponent $\alpha$.

As an example of such a household model, consider a graph with ${p}_{3}=a$ and
${p}_{6}=1-a$ and a tunable clustering coefficient. We take $\gamma_{6}=0$,
but increase $\gamma_{3}$, while the degree distribution remains the same.
Thus, the graph consists of only single vertices of degree 6, single vertices
of degree 3 and triangle communities. Since we increase $\gamma_{3}$, the
number of triangles increases, so that also the clustering coefficient
increases. Figures 6(a) and 6(b) show the size of the giant component under
percolation for different values of the clustering coefficient using $a=0.75$
and $a=0.95$ respectively. In the case where $a=0.75$, clustering decreases
the value of $\pi_{c}$, whereas if $a=0.95$, clustering increases the value of
$\pi_{c}$. This illustrates that the influence of clustering on bond
percolation of a random graph is non-trivial. In two similar random graph
models, introducing clustering has a different effect.

(a) $a=0.75$

(b) $a=0.95$

Figure 6: The size of the giant component after bond percolation with
probability $\pi$ in a household model with $p_{3}=a$ and $p_{6}=1-a$ for
various clustering coefficients $C$. If $a=0.75$, adding clustering decreases
the critical percolation value, whereas if $a=0.95$, adding clustering
increases the critical percolation value.

###  4.3 Configuration model with triangles

A third random graph model with clustering is the model by Newman [18]. In
this model, each vertex $v$ has an edge-degree
$d_{v}^{\scriptscriptstyle{(1)}}$ and a triangle degree
$d_{v}^{\scriptscriptstyle{(2)}}$, denoting the number of triangles that the
vertex is part of. Then a random graph is formed by pairing edges at random
and pairing triangles at random. Even though this model does not explicitly
replace vertices in a configuration model by communities, it is also a special
case of the hierarchical configuration model if some conditions on the degrees
are satisfied. The communities in this model are the connected components
consisting only of triangles. Figure 8 shows two possible realizations of such
communities.

From results derived in [18], we can find the probability generating function
$h_{r}(z)$ of the number of vertices in triangles that can be reached from a
uniformly chosen triangle, and the probability generating function
$h_{S^{*}}(z)$ of the size of the triangle component of a randomly chosen
vertex, that together satisfy

$\displaystyle h_{r}(z)=zg_{q}(h_{r}^{2}(z)),\quad
h_{S^{*}}(z)=zg_{p}(h_{r}^{2}(z)),$ (67)

where $g_{q}$ is the probability generating function of the size-biased
distribution of the triangle degrees, and $g_{p}$ the probability generating
function of the triangle degree distribution. In the hierarchical
configuration model, $h_{S^{*}}(z)$ can be interpreted as the probability
generating function of the size-biased community sizes. Thus, the mean size-
biased community size is given by

$\mathbb{E}[S^{*}]=1+\frac{2\mathbb{E}[D^{\scriptscriptstyle{(2)}}]}{3-2\mathbb{E}[D^{\scriptscriptstyle{(2)}*}]},$
(68)

where $D^{\scriptscriptstyle{(2)}*}$ is the size-biased distribution of the
triangle degrees. Since $\mathbb{E}[S^{*}]\geq\mathbb{E}[S]$, Condition 1(ii)
is satisfied if $\mathbb{E}[D^{\scriptscriptstyle{(2)}*}]<\frac{3}{2}$.

The mean inter-community degree of a community is given by

$\mathbb{E}[D]=\lim_{n\to\infty}\frac{\sum_{i=1}^{n}\sum_{v\in
G_{i}}d^{\scriptscriptstyle{(1)}}_{v}}{n}=\lim_{n\to\infty}\frac{\sum_{i=1}^{N}d_{i}^{\scriptscriptstyle{(1)}}/N}{n/N}=\mathbb{E}[S]\mathbb{E}[D^{\scriptscriptstyle{(1)}}].$
(69)

Hence, Conditions 1 and 2 are satisfied if
$\mathbb{E}[D^{\scriptscriptstyle{(2)}*}]<\frac{3}{2}$ and
$\mathbb{E}[D^{\scriptscriptstyle{(1)}}]<\infty$. When these conditions are
satisfied, the condition for emergence of a giant component is

$\frac{\mathbb{E}[{D^{\scriptscriptstyle{(1)}}}^{2}]\mathbb{E}[S]-\mathbb{E}[D^{\scriptscriptstyle{(1)}}]\mathbb{E}[S]}{\mathbb{E}[D^{\scriptscriptstyle{(1)}}]\mathbb{E}[S]}=\frac{\mathbb{E}[{D^{\scriptscriptstyle{(1)}}}^{2}]-\mathbb{E}[D^{\scriptscriptstyle{(1)}}]}{\mathbb{E}[D^{\scriptscriptstyle{(1)}}]}>1.$
(70)

Therefore, as long as $\mathbb{E}[D^{\scriptscriptstyle{(2)}*}]<\frac{3}{2}$,
the emergence of the giant component only depends on the edge degree
distribution.

To apply the results of the hierarchical configuration model, we need the
probability $P(H)$ that a randomly chosen community is of type $H$. This
probability is not easy to obtain, but it can be approximated using a
branching process. The branching process starts at a vertex, and explores the
component of triangles. The first generation of the branching process has
$Z_{0}=1$. The first offspring, $Z_{1}$ is distributed as
$2D^{\scriptscriptstyle{(2)}}$. All other offspring, $Z_{i}$ for $i>1$ is
distributed as $\sum_{j=1}^{Z_{i-1}}2(D_{j}^{\scriptscriptstyle{(2)}*}-1)$.
Here $D_{j}^{\scriptscriptstyle{(2)}*}$ are independent copies, distributed as
$D^{\scriptscriptstyle{(2)}*}$. In this branching process approximation,
cycles of triangles are ignored. The size-biased probability of having a
specific community $H$ can be obtained by summing the probabilities of the
possible realizations of the branching process when exploring graph $H$. This
probability is size-biased, since when starting at an arbitrary vertex, the
probability of starting in a larger community is higher. This probability then
needs to be transformed to the probability of obtaining graph $H$.

To compute the size of the giant component after percolation from (46),
$g(H,v,k,\pi)$ is needed for every community shape $H$. This is difficult to
obtain, since it largely depends on the shape of the community, and there are
infinitely many possible community shapes. Figure 8 shows an example of why
the shape of a community matters. When percolating the left community, the
probability that the red vertex is connected to $k$ other vertices is smaller
than for the graph on the right. For this reason, we approximate (46)
numerically using the branching process described above. In [18], Newman gives
expressions for the size of the largest percolating cluster. Figure 8 compares
the size of the giant component computed in that way with a numerical
approximation of (46). We see that indeed the equations from [18] give the
same results for the largest percolating cluster as (46).

Figure 7: Two possible communities with 4 triangles. In the left community, 6
other nodes can be reached from the gray node within 2 steps, in the right
community 8 nodes.

Figure 8: The size of the giant percolating cluster calculated by (46)
(hierarchical configuration model) and from results in [18] (Newman) agree.

##  5 Stylized networks

In this section, we study two stylized examples of community structures. The
first example gives a community type that decreases the critical percolation
value compared to a configuration model with the same degree distribution. The
second example increases the critical percolation value when compared to a
configuration model.

###  5.1 A community structure that decreases $\pi_{c}$

As an example of a community structure that decreases $\pi_{c}$, we consider a
hierarchical configuration model where with probability $\phi$ a community is
given by $H_{1}$: a path of $L$ vertices, with a half-edge at each end of the
path as illustrated in Figure 9. With probability $1-\phi$ the community is
$H_{2}$: a vertex with three half-edges. The degree distribution of this
hierarchical configuration model can be found using Proposition 5 and is given
by

$p_{k}=\begin{cases}\frac{L\phi}{L\phi+1-\phi}&\text{if }k=2,\\\
\frac{1-\phi}{L\phi+1-\phi}&\text{if }k=3,\\\ 0&\text{otherwise}.\end{cases}$
(71)

In this example $\mathbb{E}[D]=2\phi+3(1-\phi)$. Furthermore,
$g(H_{1},v,2,\pi)=\pi^{L-1}$ for all $v\in H_{1}$. In $H_{2}$ there is no
percolation inside the community, hence $g(H_{2},v,3,\pi)=1$. Equation (45)
now gives:

$\pi_{c}=\frac{3-\phi}{2\phi\pi_{c}^{L-1}+6(1-\phi)},$ (72)

hence $2\phi\pi^{L}_{c}+6(1-\phi)\pi_{c}-3+\phi=0$.

Now we let the degree distribution as defined in (71) remain the same, while
changing the length of the path communities $L$. If in the total graph, we
want to have a fraction of $a$ vertices of degree 3, then
$a=p_{3}=\frac{1-\phi}{1-\phi+L\phi}$. Hence, $\phi=\frac{1-a}{1-a+La}$. In
this way, we obtain hierarchical configuration models with the same degree
distribution, but with different values of $L$. Figure 11 shows the size of
the largest component as calculated by (46) for $a=1/3$. As $L$ increases,
$\pi_{c}$ decreases. Hence, adding this community structure ‘helps’ the
diffusion process. This can be explained by the fact that increasing $L$
decreases the number of line communities. Therefore, more vertex communities
will be connected to one another, which decreases the value of $\pi_{c}$.
Another interesting observation is that the size of the giant component is
non-convex in $\pi$. These non-convex shapes can be explained intuitively. As
the lines get longer, there are fewer and fewer of them, since the degree
distribution remains the same. Hence, if $L$ is large, there will only be a
few long lines. These lines have $\pi_{c}\approx 1$. Since there are only a
few lines, almost all vertices of degree 3 will be paired to one another. The
critical value for percolation on a configuration model with only vertices of
degree 3 is $0.5$. Hence, for this hierarchical configuration model with $L$
large we will see the vertices of degree 3 appearing in the giant component as
$\pi=0.5$, and the vertices in the lines as $\pi=1$.

Figure 9: A line community with $L=5$

###  5.2 A community structure that increases $\pi_{c}$

As an example of a community structure that inhibits the diffusion process,
consider a configuration model with intermediate vertices as introduced in
[11]: a configuration model where every edge is replaced by two edges with a
vertex in between them. This is equal to a hierarchical configuration model
with star-shaped communities as in Figure 4(c): one vertex that is connected
to $L$ other vertices. Each of the $L$ other vertices has inter-community
degree one. The vertex in the middle is not connected to other communities. We
consider a hierarchical configuration model where all communities are stars of
the same size. Therefore all star-shaped communities have the same number of
outgoing edges, and $\mathbb{E}[D]=L$.

The degree distribution of this hierarchical configuration model is given by

$p_{k}=\begin{cases}\frac{L}{L+1}&\text{if }k=2,\\\ \frac{1}{L+1}&\text{if
}k=L,\\\ 0&\text{otherwise}.\end{cases}$ (73)

Under percolation, the connected component of a vertex $v$ at the end point of
a star can link to other half-edges only if the edge to the middle vertex is
present. Then the number of half-edges to which $v$ is connected is binomially
distributed, so that
$g(H,v,k,\pi)=\pi{{L-1}\choose{k-1}}\pi^{k-1}(1-\pi)^{L-k}$ for $k\geq 2$.
Then (44) gives

$\displaystyle\mathbb{E}[D_{\pi}^{*}]$
$\displaystyle=\frac{1}{\mathbb{E}[D]}\sum_{H}\sum_{k}\sum_{v\in
V_{H}}P(H)d_{v}^{\scriptscriptstyle{\text{(}b)}}kg(H,v,k+1,\pi)$ (74)
$\displaystyle=\pi\sum_{k\geq 1}k\pi^{k}(1-\pi)^{L-k-1}{L-1\choose
k}=(L-1)\pi^{2}.$

Then equation (45) yields $\pi_{c}=(L-1)^{-1/3}$.

Now we consider a configuration model with the same degree distribution (73).
For this configuration model, $\pi_{c}=\frac{3L}{4L+L^{2}-3L}=\frac{3}{L+1}$.
Figure 11 shows the size of the giant component of the hierarchical
configuration model compared with a configuration model with the same degree
distribution for different values of $L$. This hierarchical configuration has
a higher critical percolation value than its corresponding configuration
model. Intuitively, this can be explained from the fact that all vertices with
a high degree are ‘hidden’ behind vertices of degree 2, whereas in the
configuration model, vertices of degree $L$ may be connected to one another.

Combined with the previous example, we see that adding communities may lead to
a higher critical percolation value or a lower one. Furthermore, the size of
the giant component may be smaller or larger after adding communities.

Figure 10: Size of giant component against $\pi$ for line communities with
different values of $L$.

Figure 11: Size of giant component against $\pi$ for star communities with
different values of $L$.

##  6 Conclusions and discussion

In this paper, we have introduced the hierarchical configuration model, where
the macroscopic graph is a configuration model, and on the microscopic level
vertices are replaced by communities. We have analytically studied several
properties of this random graph model, which led to several interesting
insights. For example, the condition for a giant component to emerge in the
hierarchical configuration model is completely determined by properties of the
macroscopic configuration model. However, the size of the giant component also
depends on the community sizes. In contrast, the asymptotic clustering
coefficient is entirely defined by the clustering inside the communities. For
bond percolation on the hierarchical configuration model, the critical
percolation value depends on both the inter-community degree distribution, and
the shape of the communities. Furthermore, we have shown that if communities
are dense with a power-law degree distribution, then the edges between
communities follow a power law with an exponent that is one higher than the
exponent of the degree distribution. We have further investigated power-law
relations in several real-world networks, and compare these to the power-law
relations in our hierarchical configuration model in a companion paper [22].
These real-world networks do not display this power-law shift, which implies
that most communities in real-world networks do not satisfy the intuitive
picture of dense communities. In fact, we find a power-law relation between
the denseness of the communities and their sizes, so that the large
communities are less dense than the smaller communities.

Finally, we have shown that several existing models incorporating a community
structure can be interpreted as a special case of the hierarchical
configuration model, which underlines its generality. Worthwhile extensions of
the hierarchical configuration model for future research include directed or
weighted counterparts and a version that allows for overlapping communities.

The analysis of percolation on the hierarchical configuration model has shown
that the size of the largest percolating cluster and the critical percolation
value do not necessarily increase or decrease when adding clustering. It would
be interesting to investigate how other characteristics of the graph like
degree-degree correlations influence the critical percolation value. Another
interesting feature of the hierarchical configuration model is its
applicability to real-world data sets. In this setting, the hierarchical
configuration model creates a graph with the same degree distribution and the
same community structure as real-world networks. In [21] we investigated by
simulations how community structures affect the spread of several epidemic
processes on real-world networks, including bond percolation and an SIR model,
and showed that communities in real-world networks can either inhibit or
enforce an epidemic. It would be interesting to study these epidemic processes
also analytically.

$H$ |  a community type
---|---
$P(H)$ |  asymptotic probability that a community is of type $H$
$p_{k,s}$ |  asymptotic probability that a community has size $s$ and inter-community degree $k$
$S$ |  asymptotic community size distribution
$D$ |  asymptotic community inter-community degree distribution
$d_{v}^{\scriptscriptstyle{(b)}}$ |  inter-community degree: the number of edges from vertex $v$ to other communities
$d_{v}^{\scriptscriptstyle{(c)}}$ |  intra-community degree: the number of edges from vertex $v$ to community members
$d_{v}$ |  degree of vertex $v$, $d_{v}=d_{v}^{\scriptscriptstyle{(b)}}+d_{v}^{\scriptscriptstyle{(c)}}$
$n$ |  number of communities
$N$ |  number of vertices
$\pi_{c}$ |  critical percolation probability
$g(H,v,k,\pi)$ |  probability that vertex $v$ is connected to $k$ edges going out of community $H$ after percolating the edges inside the community with parameter $\pi$
Table 1: Frequently used symbols

##### Acknowledgement.

This work is supported by NWO TOP grant 613.001.451. The work of RvdH is
further supported by the NWO VICI grant 639.033.806. The work of JvL is
further supported by an NWO TOP-GO grant and by an ERC Starting Grant.

## References

  * [1] F. Ball, D. Sirl, and P. Trapman.  Threshold behaviour and final outcome of an epidemic on a random network with household structure.  Adv. in Appl. Probab., 41(3):765–796, 09 2009.
  * [2] F. Ball, D. Sirl, and P. Trapman.  Analysis of a stochastic SIR epidemic on a random network incorporating household structure.  Mathematical Biosciences, 224(2):53 – 73, 2010.
  * [3] B. Bollobás.  Random Graphs, volume 74 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, 2nd edition, 2001.
  * [4] E. Coupechoux and M. Lelarge.  How clustering affects epidemics in random networks.  Adv. in Appl. Probab., 46(4):985–1008, 12 2014.
  * [5] M. Deijfen and W. Kets.  Random intersection graphs with tunable degree distribution and clustering.  Probability in the Engineering and Informational Sciences, 23:661–674, 10 2009.
  * [6] N. Fountoulakis.  Percolation on sparse random graphs with given degree sequence.  Internet Mathematics, 4(4):329–356, 2007.
  * [7] M. Girvan and M. E. J. Newman.  Community structure in social and biological networks.  Proceedings of the National Academy of Sciences, 99(12):7821–7826, 2002.
  * [8] R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, and A. Arenas.  Self-similar community structure in a network of human interactions.  Phys. Rev. E, 68:065103, Dec 2003.
  * [9] R. van der Hofstad.  Random Graphs and Complex Networks Vol. II.  Available on http://www.win.tue.nl/$\sim$rhofstad/NotesRGCNII.pdf, 2014.
  * [10] R. van der Hofstad.  Random Graphs and Complex Networks Vol. I.  To appear with Cambridge University Press, 2016.
  * [11] R. van der Hofstad and N. Litvak.  Degree-degree dependencies in random graphs with heavy-tailed degrees.  Internet Mathematics, 10(3-4):287–334, September 2014.
  * [12] T. House.  Exact epidemic dynamics for generally clustered, complex networks.  arXiv:1006.3483, 2010.
  * [13] S. Janson.  On percolation in random graphs with given vertex degrees.  Electron. Journal of Probability, 14:86–118, 2009.
  * [14] S. Janson and M. J. Luczak.  A new approach to the giant component problem.  Random Structures & Algorithms, 34(2):197–216, 2009.
  * [15] B. Karrer and M. E. J. Newman.  Random graphs containing arbitrary distributions of subgraphs.  Phys. Rev. E, 82:066118, Dec 2010.
  * [16] M. Molloy and B. Reed.  A critical point for random graphs with a given degree sequence.  Random Structures & Algorithms, 6(2-3):161–180, 1995.
  * [17] M. Molloy and B. Reed.  The size of the giant component of a random graph with a given degree sequence.  Combinatorics, Probability and Computing, 7(03):295–305, 1998.
  * [18] M. E. J. Newman.  Random graphs with clustering.  Phys. Rev. Lett., 103(5):058701, July 2009.
  * [19] M. E. J. Newman and J. Park.  Why social networks are different from other types of networks.  Phys. Rev. E, 68:036122, Sep 2003.
  * [20] P. Sah, L. O. Singh, A. Clauset, and S. Bansal.  Exploring community structure in biological networks with random graphs.  BMC Bioinformatics, 15(1):220, 2014.
  * [21] C. Stegehuis, R. van der Hofstad, and J. S. H. van Leeuwaarden.  Epidemic spreading on complex networks with community structures.  Scientific Reports, 6:29748, 2016.
  * [22] C. Stegehuis, R. van der Hofstad, and J. S. H. van Leeuwaarden.  Power-law relations in random networks with communities.  Phys. Rev. E, 94:012302, Jul 2016.
  * [23] P. Trapman.  On analytical approaches to epidemics on networks.  Theoretical Population Biology, 71(2):160 – 173, 2007.