# Modularity and Graph Expansion

Baptiste Louf Email<EMAIL_ADDRESS>Part of this work was
done while supported by the Knut and Alice Wallenberg Foundation. CNRS and
Institut de Mathématiques de Bordeaux, France  Colin McDiarmid Email:
<EMAIL_ADDRESS>Department of Statistics, University of Oxford, United Kingdom
Fiona Skerman Email<EMAIL_ADDRESS>Partially supported by the
Wallenberg AI, Autonomous Systems and Software Program WASP and the project
AI4Research at Uppsala University. Part of this work was done while visiting
the Simons Institute for the Theory of Computing, supported by a Simons-
Berkeley Research Fellowship. Department of Mathematics, Uppsala University,
Sweden

###### Abstract

We relate two important notions in graph theory: expanders which are highly
connected graphs, and modularity a parameter of a graph that is primarily used
in community detection. More precisely, we show that a graph having modularity
bounded below 1 is equivalent to it having a large subgraph which is an
expander.

We further show that a connected component $H$ will be split in an optimal
partition of the host graph $G$ if and only if the relative size of $H$ in $G$
is greater than an expansion constant of $H$. This is a further exploration of
the resolution limit known for modularity, and indeed recovers the bound that
a connected component $H$ in the host graph $G$ will not be split if
$e(H)<\sqrt{2e(G)}$.

##  1 Introduction and results

In this paper, we relate the property of a graph having expander induced
subgraphs with the notion of its modularity. (We recall the definitions of the
modularity of a graph and of expander graphs in Section 1.1 below.) Modularity
was introduced by Newman and Girvan [33], and it quantifies how well a graph
can be divided into separate communities. More precisely, to each graph $G$,
we associate a quantity $0\leq q^{*}(G)<1$, and the higher $q^{*}(G)$ is the
more ‘community structure’ $G$ has. Many community detection algorithms are
based on a modularity maximisation principle [4, 11, 36], with a wide range of
applications, from protein detection to connections between web sites. See
[14, 34] for surveys on modularity.

On the other hand, expander graphs are important objects in graph theory and
theoretical computer science. An expander graph has a wide variety of
properties: for instance, the random walk mixes very fast [1, 16], and the
eigenvalues of its Laplacian are well-separated [2, 9]. In computer science,
they are used for clustering with the expander decomposition technique, see
for instance [19]. We refer to [17] for a survey of expander graphs and their
applications.

The modularity value $q^{*}(G)$ of a graph $G$ is robust to small
perturbations in the edge-set: changing an $\varepsilon$ proportion of the
edges in the graph changes the modularity value by at most $2\varepsilon$
[29]. In contrast, the property of being an expander, and the expansion
constant, is influenced by even very small regions in the graph: for example
adding a disjoint edge causes the expansion constant to drop to zero. However,
the property of having large expander subgraphs is robust to changes in the
edge-set, see also the discussion in [8, 22]. Here, by ‘large’ we mean
containing at least a constant fraction of the edges of the graph. It turns
out this notion of containing large induced expander subgraphs will be the
right expander property of graphs to consider when relating modularity and
expansion. The question of the presence of large expanders in graphs has been
considered in previous works [6, 21, 22, 26].

Here is a quick guide to the results, which will be presented after the
definitions. Theorem 1.1 shows that modularity bounded below 1 implies having
a large expander subgraph and vice versa; with detailed upper and lower bounds
given in Propositions 1.2 and 1.3. Our other main result, Theorem 1.4 shows
that whether a connected component $H$ in host graph $G$ is split (or kept as
one part) in an optimal partition of $G$ is characterised by the ratio
$e(H)/e(G)$ and an edge expansion constant $\hat{h}_{H}$ of $H$ \- see Section
1.1. This extends the ‘resolution limit’ known to exist for modularity.

The results are stated in Section 1.2 and proven in Section 2. In Section 3 we
give families of examples showing the tightness of Theorem 1.1 and part of
Proposition 1.2, the other part remains open, see Section 5.

###  1.1 Definitions

#### Graph definitions

Given a graph $G$, for disjoint sets $A$ and $B$ of vertices, let $e_{G}(A)$
be the number of edges within $A$, let $e_{G}(A,B)$ be the number of edges
between $A$ and $B$, and let the _volume_ ${\rm vol}_{G}(A)$ be the sum over
the vertices $v$ in $A$ of the degree $d_{v}$. We will sometimes drop the
subscript if it is clear from context. We restrict our attention to graphs $G$
with at least one edge (that is, _non-empty_ graphs), usually without comment.

Our graphs may have multiple or weighted edges and loops. For such a graph
$G$, $e_{G}(A)$ and $e_{G}(A,B)$ are the sums of the weights of the
corresponding edges. Similarly the weighted degree $d_{v}$ of a vertex $v$ is
the sum of the weights of the incident edges, with loops counting twice to the
sum. The volume ${\rm vol}_{G}(S)$ of a set $S$ of vertices is the sum of the
weighted degrees of the vertices in $S$.

#### Expansion definitions

Let us now introduce the property of graph expansion and two ways of measuring
it: relative to the volume of the smaller set or to a product of volumes.
Given a graph $G$ the _conductance_ or _Cheeger constant_ $h_{G}$ is defined
as follows. Write $\bar{A}$ to denote $V(G)\backslash A$ and let

$h_{G}(A)=\frac{e_{G}(A,\bar{A})}{\min\\{{\rm vol}_{G}(A),{\rm
vol}_{G}(\bar{A})\\}}\;\;\mbox{for }\emptyset\neq
A\;\subsetneq\;V(G),\;\;\;\mbox{and}\;\;\;h_{G}=\min_{A}h_{G}(A)\ .$ (1.1)

We say that $G$ is a _$\delta$ -expander_ for any $0<\delta\leq h_{G}$.
Observe that $0\leq h_{G}\leq 1$, $h_{G}=0$ iff $G$ is disconnected, and
$h_{G}=1$ iff $G$ is $K_{3}$ or $K_{1,t}$ for some $t\geq 1$, see Remark 2.1.

Now define the following variant $\hat{h}_{G}$ of graph expansion, by
replacing the minimum with a product and normalising. Let

$\hat{h}_{G}(A)=\frac{e_{G}(A,\bar{A})}{{\rm vol}_{G}(A){\rm
vol}_{G}(\bar{A})}{\rm vol}(G)\;\;\;\mbox{for }\emptyset\neq
A\;\subsetneq\;V,\;\;\;\;\mbox{and}\;\;\;\;\hat{h}_{G}=\min_{A}\hat{h}_{G}(A).$
(1.2)

We say $G$ is a _$\hat{\delta}$ -expander-by-products_ for any
$0<\hat{\delta}\leq\hat{h}_{G}$. Observe that $0\leq\hat{h}_{G}\leq 2$,
$\hat{h}_{G}=0$ iff $G$ is disconnected, and $\hat{h}_{G}=2$ iff $G$ is
$K_{2}$, see Remark 2.1. Further we always have

$\tfrac{1}{2}\,\hat{h}_{G}\leq h_{G}\leq\hat{h}_{G}$ (1.3)

(and $h_{G}<\hat{h}_{G}$ if $G$ is connected).

This notion $\hat{h}_{G}$ of expansion-by-products was used for example in the
paper by Kannan, Lovász and Simonovits [18] as they found it a more natural
definition to relate expansion and Markov chains. We will find that under the
notion of expansion-by-products we have a tight upper bound for modularity in
Proposition 1.2. Also the value $\hat{h}_{H}$ of a connected component $H$ in
host graph $G$, together with the relative size $e(H)/e(G)$, characterise
whether or not the vertex set of the component is split in a modularity
optimal partition of $G$, see Theorem 1.4.

#### Modularity definitions

For a graph $G$, we assign a modularity score $q_{\mathcal{A}}(G)$ to each
vertex partition (or ‘clustering’) $\mathcal{A}$. The modularity $q^{*}(G)$ of
$G$, sometimes called the ‘maximum modularity’ of $G$, is defined to be the
maximum of these scores over all vertex partitions.

Modularity was introduced in Newman & Girvan [33]. Let $G$ be a graph with
vertex set $V$ and with $m\geq 1$ edges. For a partition $\mathcal{A}$ of $V$,
the modularity score of $\mathcal{A}$ on $G$ is

$q_{\mathcal{A}}(G)=\frac{1}{m}\sum_{A\in\mathcal{A}}e(A)-\frac{1}{4m^{2}}\sum_{A\in\mathcal{A}}{\rm
vol}(A)^{2};$

and the (maximum) modularity of $G$ is
$q^{*}(G)=\max_{\mathcal{A}}q_{\mathcal{A}}(G)$, where the maximum is over all
partitions $\mathcal{A}$ of $V$. We will write modularity as the difference of
two terms, the _edge contribution_ or _coverage_
$q^{E}_{\mathcal{A}}(G)=\tfrac{1}{m}\sum_{A\in\mathcal{A}}e(A)$, and the
_degree tax_
$q^{D}_{\mathcal{A}}(G)=\tfrac{1}{4m^{2}}\sum_{A\in\mathcal{A}}{\rm
vol}(A)^{2}$. For a graph $G$ with no edges, by convention we set
$q_{\mathcal{A}}(G)=0$ for every vertex partition $\mathcal{A}$ and thus
$q^{*}(G)=0$.

###  1.2 Statement of Results

#### Modularity of $G$ and expansion of subgraphs $H$

Recall that $0\leq q^{*}(G)<1$, and the closer $q^{*}(G)$ is to $1$ the more
community structure $G$ is considered to have. Our main result, Theorem 1.1,
is that having low modularity implies having a large expander induced
subgraph, and vice versa.

We shall use the following function $f$, see Figure 1.2. For $0<\alpha\leq 1$
let $f(\alpha)$ be the maximum value of $\sum_{i}x_{i}^{2}$ where $0\leq
x_{i}\leq\alpha$ for each $i$ and $\sum_{i}x_{i}=1$; so

$f(\alpha)=\alpha^{2}\lfloor 1/\alpha\rfloor+(1-\alpha\lfloor
1/\alpha\rfloor)^{2}\;\;\mbox{ for }0<\alpha\leq 1\,.$ (1.4)

Notice that $f$ is continuous and increasing, $f(\alpha)=\alpha$ when
$\alpha=1/k$ for some integer $k$, and always $\alpha-\alpha^{2}/4\leq
f(\alpha)\leq\alpha$, so for small $\alpha$ we have $f(\alpha)\sim\alpha$.

(a) $G_{H}$ with $q^{*}(G_{H})\\!\geq\\!1\\!-\\!\alpha^{2}\\!-\\!O(m^{-1}).$

(b) $G_{\alpha}$ with
$q^{*}(G_{\alpha})\\!=\\!1-\\!f(\alpha)\\!+\\!O(m^{-\frac{1}{2}}).$

Figure 1.1: Example constructions for Theorem 1.1, see Section 3.1 for
details.

######  Theorem 1.1.

Let $0<\alpha<1$ and let $\varepsilon>0$.

  1. (a)

    1. (i)

If the graph $G$ contains a subgraph $H$ with $e(H)\geq\alpha e(G)$ which is
an $\alpha$-expander (that is $h_{H}\geq\alpha$) then $q^{*}(G)\leq
1-\alpha^{2}$.

    2. (ii)

Conversely, for all sufficiently large $m\in{\mathbb{N}}$, for _each_ graph
$H$ with $e(H)\leq\alpha m$ there exists an $m$-edge graph $G_{H}$ containing
$H$ as an induced subgraph such that $q^{*}(G_{H})\geq
1-\alpha^{2}-\varepsilon$.

  2. (b)

    1. (i)

There exists $\delta>0$ such that every graph $G$ with
$q^{*}(G)<1-f(\alpha)-\varepsilon$ contains an induced subgraph $H$ with
$e(H)\geq\alpha e(G)$ which is a $\delta$-expander (that is
$h_{H}\geq\delta)$.

    2. (ii)

Conversely, for all sufficiently large $m\in{\mathbb{N}}$ there is an $m$-edge
graph $G_{\alpha}$ with $q^{*}(G_{\alpha})<1-f(\alpha)+\varepsilon$ such that
each subgraph of $G_{\alpha}$ with at least $\alpha\,m$ edges is disconnected.

Constructions for the two ‘converse’ statements (a)(ii) and (b)(ii) in the
theorem are illustrated in Figure 1.1, with full details and proofs of the
bounds deferred to Section 3.1. Notice that the construction for (a)(ii) is
particularly simple - given $H$ we may form $G_{H}$ by adding $e(G)-e(H)$
disjoint edges to $H$. Notice also that in (a)(ii) we may for example take $H$
to be an $\alpha$-expander. (by products).

The first statements (a)(i) and (b)(i) in Theorem 1.1 follow immediately from
the next two propositions, which give bounds on the dependence between the
modularity value of $G$ and the relative size and expansion constant of
subgraphs of $G$. Recall from Section 1.1 that $h_{H}$ denotes the usual
notion of conductance, while $\hat{h}_{H}$ is a measure of edge expansion
normalised by the product of the volumes of the two parts.

######  Proposition 1.2.

  1. (i)

Let $0<\alpha\leq 1$, let $G$ be a graph and let $H$ be a subgraph with
relative size $e(H)/e(G)\geq\alpha$. Then

$q^{*}(G)\leq 1-\alpha\min\\{\hat{h}_{H},\alpha\\}.$

  2. (ii)

Conversely, for all $\varepsilon>0$, $0\leq a\leq 1$, $0\leq\hat{\delta}\leq
1$, there exists a graph $G$ with induced subgraph $H$ of relative size
$\alpha=e(H)/e(G)$ such that
$\,|\alpha-a|,|\hat{h}_{H}-\hat{\delta}|<\varepsilon$ and

$q^{*}(G)\geq 1-\alpha\min\\{\hat{h}_{H},\alpha\\}-\varepsilon.$

In Proposition 1.2, the converse statement (ii) shows that the inequality in
(i) is tight. Since $h_{H}\leq\hat{h}_{H}$ by (1.3), from (i) we have

$q^{*}(G)\leq 1-\alpha\min\\{\hat{h}_{H},\alpha\\}\leq
1-\alpha\min\\{h_{H},\alpha\\};$

and in the special case $\alpha=1$ we obtain $q^{*}(G)\leq
1-\min\\{\hat{h}_{G},1\\}\leq 1-h_{G}$ see Section 5 for a discussion.

Figure 1.2: The function $f$, see (1.4).

######  Proposition 1.3.

Let $0<\alpha,\delta\leq 1$, let $G$ be a graph, and suppose that each induced
subgraph $H$ with relative size $e(H)/e(G)\geq\alpha$ has $h_{H}<\delta$. Then

$q^{*}(G)>1-f\left(\min\\{1,\alpha+\tfrac{3}{2}\delta\\}\right)-\tfrac{3}{2}\,\delta\lceil\log_{2}(1/\alpha)\rceil.$

To prove the first statements (a)(i) and (b)(i) in Theorem 1.1 from these two
propositions, one just needs to assume $h_{H}\geq\alpha$ (since then also
$\hat{h}_{H}\geq\alpha$) in Proposition 1.2(i); and $\delta$ small enough in
Proposition 1.3, and use the fact that $f$ is continuous.

#### When should we split a component?

In an optimal partition of any graph $G$ without isolated vertices, for each
part $A$ the induced subgraph $G[A]$ is connected [7]. (If not, say
$e(A^{\prime},A\backslash A^{\prime})=0$ for some $\emptyset\neq
A^{\prime}\subset A$, then replacing part $A$ by parts $A^{\prime}$ and
$A\backslash A^{\prime}$ strictly increases the modularity score: the edge
contribution stays the same while the degree tax is strictly decreased.) This
implies that each connected component $H$ is partitioned separately from the
rest of the host graph.

We find that whether an optimal partition of $G$ splits $H$ into multiple
parts or keeps the vertices of $H$ together in one part is characterised by
$\alpha$ and $\hat{h}_{H}$. Let ${\rm OPT}(G)$ be the set of partitions
$\mathcal{A}$ for $G$ such that $q_{\mathcal{A}}(G)=q^{*}(G)$.

######  Theorem 1.4.

Let $H$ be a connected component in a graph $G$ and let $\alpha$ be the
relative size $e(H)/e(G)$.

  * •

If $\alpha<\hat{h}_{H}$ then $\forall\mathcal{A}\in{\rm OPT}(G)$, $H$ is not
split.

  * •

If $\alpha>\hat{h}_{H}$ then $\forall\mathcal{A}\in{\rm OPT}(G)$, $H$ is
split.

  * •

If $\alpha=\hat{h}_{H}$ then $\exists\,\mathcal{A},\mathcal{A}^{\prime}\in{\rm
OPT}(G)$ such that $H$ is not split in $\mathcal{A}$ and $H$ is split in
$\mathcal{A}^{\prime}$.

Note that $\hat{h}_{H}$ is a minimum of a function over cuts or bipartitions
of $V(H)$, rather than over all partitions of $V(H)$ including those
containing more than two parts. Hence it is interesting that $\alpha$ and
$\hat{h}_{H}$ are enough to determine when a connected component is split in
an optimal partition of the host graph.

Recall the original resolution limit bound, in [15], that any modularity
optimal partition will not split a connected component $H$ in graph $G$ if
$e(H)<\sqrt{2e(G)}$. This is implied by Theorem 1.4. To see this, note first
that $e(U,V(H)\backslash U)\geq 1$ for all $\emptyset\neq U\subsetneq V(H)$
(since $H$ is connected). Also $\max_{U}{\rm vol}(U)({\rm vol}(H)-{\rm
vol}(U))\leq{\rm vol}(H)^{2}/4={\rm vol}(H)e(H)/2$. Hence $\hat{h}_{H}\geq
2/e(H)$. By the theorem, $H$ will not be split if $e(H)/e(G)<2/e(H)$ (since
then $e(H)/e(G)<\hat{h}_{H}$). Rearranging, we see that $H$ will not be split
if $e(H)<\sqrt{2e(G)}$, which recovers the resolution limit bound.

Theorem 1.4 also shows that connected components with modularity zero will not
be split in any optimal partition of $G$.

######  Corollary 1.5.

Let the graph $G$ have no isolated vertices, and let $H$ be a connected
component of $G$ with $e(H)<e(G)$. Let $\mathcal{A}$ be an optimal partition
for $G$, that is, $q_{\mathcal{A}}(G)=q^{*}(G)$. If $q^{*}(H)=0$ then $V(H)$
is a part in $\mathcal{A}$.

To see why Corollary 1.5 follows from Theorem 1.4 (and Proposition 1.7), note
by Proposition 1.7 that $q^{*}(H)=0$ implies $\hat{h}_{H}\geq 1$. Now since
$e(H)<e(G)$ we have that $\alpha=e(H)/e(G)<\hat{h}_{H}$ and thus by Theorem
1.4 the component $H$ is not split in any optimal partition of $G$.

This corollary tells us, for example, that each clique in Figure 1.1 forms its
own part in any optimal partition.

#### Modularity near one

The next result says roughly that $q^{*}(G)\approx 1$ if and only if each
‘large’ subgraph $H$ of $G$ has $h_{H}\approx 0$.

######  Corollary 1.6.

  1. (a)

For all $\alpha,\delta>0$ there exists $\varepsilon>0$ such that if the graph
$G$ has a subgraph $H$ with at least $\alpha\,e(G)$ edges which is an
$\delta$-expander then $q^{*}(G)<1-\varepsilon$ (indeed we may take
$\varepsilon=\alpha\min\\{\alpha,\delta\\}$).

  2. (b)

For all $\varepsilon>0$ there exists $\alpha>0$ such that if the graph $G$ has
no subgraph $H$ with at least $\alpha\,e(G)$ edges which is an
$\alpha$-expander then $q^{*}(G)>1-\varepsilon$.

This last result shows that, given a sequence $G_{m}$ of $m$-edge graphs, as
$m\to\infty$ we have $q^{*}(G_{m})\to 1$ if and only if $\max_{H\subseteq
G_{m}}\min\\{e(H)/m,h_{H}\\}\to 0$. (This statement remains true if instead of
maximising over all subgraphs $H$ of $G$ we maximise over all topological
minors $H$ of $G$, see [26].) Thus we have a characterisation of ‘maximally
modular’ graphs $G_{m}$ as defined in [32].

#### Modularity zero

Now consider the other extreme, when $q^{*}(G)=0$. It is known that this holds
for complete graphs [7] and complete multipartite graphs [5, 27] and for all
graphs constructed by taking a complete graph on $n$ vertices and deleting at
most $n/2$ edges [30]. We can characterise when $q^{*}(G)=0$ in terms of a
form of graph expansion. This can be expressed in a way now involving not the
minimum of $e(A)$ and $e(\bar{A})$ but their geometric mean, or involving a
product of ${\rm vol}(A)$ and ${\rm vol}(\bar{A})$. Here $\bar{A}$ denotes
$V(G)\setminus A$.

######  Proposition 1.7.

For a graph $G$, the following three conditions are equivalent:

  1. (a)

$\;q^{*}(G)=0$

  2. (b)

$\;e(A,\bar{A})\geq 2\sqrt{e(A)e(\bar{A})}\;$ for all $A\subseteq V(G)$

  3. (c)

$\;e(A,\bar{A})\geq{\rm vol}(A){\rm vol}(\bar{A})/{\rm vol}(G)\;$ for all
$A\subseteq V(G)$ , i.e. $\hat{h}_{G}\geq 1$.

By Proposition 1.7, if the graph $G$ satisfies $q^{*}(G)=0$, then

$e(A,\bar{A})\geq{\rm vol}(A){\rm vol}(\bar{A})/{\rm vol}(G)\geq\min\\{{\rm
vol}(A),{\rm vol}(\bar{A})\\}\cdot\tfrac{1}{2}\;\;\mbox{ for all }A\subseteq
V(G)\,,$

and so we have the following corollary concerning the conductance $h_{G}$.

######  Corollary 1.8.

If the graph $G$ satisfies $q^{*}(G)=0$, then $h_{G}\geq 1/2$.

The reverse statement to the corollary does not hold. See Lemma 3.7 and Figure
3.2 for an example ‘windmill’ graph with conductance $1/2$ and positive
modularity. Proposition 1.7 also yields a short proof that complete
multipartite graphs have modularity zero, see [30].

###  1.3 Relation to existing results and our contribution

##### Natural conditions to guarantee a large expander subgraph

What properties of the graph imply that it will have an expander subgraph on a
linear proportion of the edges? This question is asked in [8] which shows that
having a positive proportion of vertices such that a random walk starting from
them is well-mixing is sufficient, indeed, it implies the graph contains an
almost spanning subgraph which is an expander. We show that modularity bounded
away from 1 is another such condition which guarantess a linear sized expander
subgraph.

##### Relation to spectral properties of subgraphs.

Our results relate the expansion properties of subgraphs $H$ of $G$ to the
modularity of $G$, but how about spectral properties of $H$, what do these
imply about the modularity of $G$?

Define the normalised Laplacian of graph $H$ to be
$\mathcal{L}_{H}=I-D^{-1/2}AD^{-1/2}$ where $A$ is the adjacency matrix of
$H$, $d_{i}$ is the degree of vertex $i$, and $D^{-1/2}$ is the diagonal
matrix with $i$-th diagonal entry $d_{i}^{-1/2}$. The spectral gap of $H$ is
$\bar{\lambda}_{H}=\max_{i\neq 0}|1-\lambda_{i}|$ where
$0=\lambda_{0}\leq\lambda_{1}\leq\cdots$ are the eigenvalues of
$\mathcal{L}_{H}$. Always $0\leq\bar{\lambda}_{H}\leq 1$. An expander-mixing
lemma, see Corollary 5.5 of [10], says that for any graph $H$ we have
$\hat{h}_{H}\geq 1-\bar{\lambda}_{H}$, and thus the following result is an
immediate corollary of Proposition 1.2.

######  Corollary 1.9.

Let the graph $G$ have a subgraph $H$ with spectral gap $\bar{\lambda}_{H}$,
and with $e(H)\geq\alpha\,e(G)$ where $\alpha>0$. Then

$q^{*}(G)\leq 1-\alpha\min\\{\alpha,1-\bar{\lambda}_{H}\\}.$

Note that in the case $\alpha=1$, that is when the graph $G$ itself has
spectral gap $\bar{\lambda}$ this recovers the results
$q^{*}(G)\leq\bar{\lambda}$ in [13, 37] (regular graphs) and [29] (general
graphs). Spectral results were used to prove upper bounds on the modularity in
[28, 29, 35] and lower bounds in [24] \- see Proposition 4.1.

##### Graphs with asymptotically maximal modularity

De Montgolfier, Soto and Viennot [32] defined the notion of maximally modular
classes of graphs as those for which $q^{*}(G)\rightarrow 1$ as
$e(G)\rightarrow\infty$, and showed hypercubes and tori are maximally modular,
as well as $n$-vertex trees with maximum degree $\Delta=o(n^{1/5})$. This was
extended to the class of trees with $\Delta=o(n)$ [28], to the class of graphs
with treewidth such that the product of treewidth and max degree is $o(e(G))$
[28], and to the class of minor-free graphs with maximum degree
$\Delta=o(e(G))$ [24]. Our paper extends this to graphs $G$ where any expander
subgraph $H$ satisfies $e(H)=o(e(G))$, see Corollary 1.6.

##### Graphs with bounds on modularity values

Given that the most popular clustering algorithms for large networks are
modularity-based [23] it is important to build up our theoretical knowledge on
modularity. Finding the modularity for graph classes helps us understand the
behaviour of the modularity function. For a list of results see the table in
[29], noting that since then it has been established in [25] that whp random
cubic graphs have modularity value in the interval $[0.667,0.79998]$, and in
[24] that graphs which have bounded genus and maximum degree $o(n)$ have
modularity asymptotically 1. Also, the modularity of the stochastic block
model is considered in [3, 11, 20] and of random geometric graphs in [12]. Our
paper contributes to this line of work by proving upper and lower bounds on
modularity in terms of the relative size and expansion of subgraphs.

##### Key contributions of this paper

We relate modularity and graph expansion by formulating and proving upper and
lower bounds for the modularity of graphs given the sizes and expansion
coefficients of their subgraphs. In the constructions, Section 3, we establish
their modularity values and the expansion-by-products of their subgraphs. This
yields the tightness of the upper bounds on $q^{*}$ in Proposition 1.2 for all
values of $\alpha$ and $\hat{h}_{H}$. Previously the special cases
$q^{*}(G)\leq 1-h_{G}$ and $q^{*}(G)\leq\bar{\lambda}_{G}$, as mentioned
earlier, were known. Recall that robustness results of [29] show that, if $G$
has a subgraph $H$ then $q^{*}(G)\leq q^{*}(H)+2e(G\backslash H)/e(G)$ which
yields the upper bound $q^{*}(G)\leq\bar{\lambda}_{H}+2(1-\alpha)$ where
$\alpha=e(H)/e(G)$ (this was used to prove that whp
$q^{*}(G_{n,d/n})=\Theta(d^{-1/2})$). Lower bounds on $q^{*}$ in terms of
expansion of subgraphs were used in [24] and we improve these - see
Proposition 4.1.

The other key contribution is to deepen the understanding of the well-known
resolution limit for modularity established by Fortunato and Barthélemy [15].
Loosely this says that modularity cannot pick up the community structure of
any connected component of an $m$-edge graph if the component has fewer than
$\sqrt{2m}$ edges. Theorem 1.4 determines the scale at which the community
structure of a connected component becomes detectable by modularity, as a
function of an expansion coefficient of the component.

##  2 Proofs

In this section we prove Propositions 1.2, 1.3 and 1.7. Note that this yields
all the results presented in Section 1, except for the ‘conversely’ statements
(a)(ii) and (b)(ii) in Theorem 1.1 and Proposition 1.2(ii) which are all based
on proving properties of constructions, see Section 3.

For completeness, we also include a remark on the upper bounds on $h_{G}$ and
$\hat{h}_{G}$ claimed in the introduction, as we could not find a reference.

######  Remark 2.1.

It is easy to see that $h_{G}\leq 1$. Let us show that $h_{G}=1$ iff $G$ is
$K_{3}$ or $K_{1,t}$ for $t\geq 1$. First note that $h_{G}=h_{G}(A)$ for some
$A$ with $G[A]$ connected and ${\rm vol}_{G}(A)\leq{\rm vol}_{G}(\bar{A})$. We
may now see that $h_{G}=1$ iff $G$ does not contain two disjoint edges. If $G$
contains two disjoint edges $uv$ and $xy$ say, and ${\rm
vol}(\\{u,v\\})\leq{\rm vol}(\\{x,y\\})$ then $h_{G}(\\{u,v\\})<1$. If $G$
does not contain two disjoint edges then for any $|A|\geq 2$ with $G[A]$
connected we have ${\rm vol}_{G}(A)>{\rm vol}_{G}(\bar{A})$, so
$h_{G}=h_{G}(A)$ for some $|A|=1$ and thus $h_{G}=1$ and we are done.

To show $\hat{h}_{G}\leq 2$ with equality iff $G$ is $K_{2}$, one can argue as
follows. For nonempty $A\subsetneq V$ with say ${\rm vol}_{G}(A)\leq{\rm
vol}_{G}(\bar{A})$, since ${\rm vol}(G)/{\rm vol}_{G}(\bar{A})\leq 2$ we have

$\hat{h}_{G}(A)\leq\frac{e_{G}(A,\bar{A})}{{\rm vol}_{G}(A)}\cdot 2\leq 2$

with strict inequality unless ${\rm vol}_{G}(A)=\tfrac{1}{2}{\rm vol}(G)$. But
the only graph (without isolated vertices) such that ${\rm
vol}_{G}(A)=\tfrac{1}{2}{\rm vol}(G)$ for each nonempty $A\subsetneq V$ is
$K_{2}$ and we are done.

###  2.1 Proof of Proposition 1.2

###### Proof of Proposition 1.2.

Let $\mathcal{A}$ be a partition of $V(G)$, let
$\mathcal{B}=\mathcal{B}(\mathcal{A},H)$ be the induced partition of $V(H)$
and define $x_{B}={\rm vol}_{H}(B)/{\rm vol}(H)$ for parts $B\in\mathcal{B}$.
Let $\hat{\delta}:=\hat{h}_{H}$. We will prove the statement

$q_{\mathcal{A}}(G)\leq
1-\alpha\hat{\delta}+\alpha(\hat{\delta}-\alpha)\sum_{B\in\mathcal{B}}x_{B}^{2}.$
(2.1)

To see that (2.1) implies the proposition note $0<\sum_{B}x_{B}^{2}\leq 1$ and
hence $q_{\mathcal{A}}(G)\leq 1-\alpha\min\\{\hat{h}_{H},\alpha\\}$. Since
$h_{H}\leq\hat{h}_{H}$ for any graph $H$ this implies $q_{\mathcal{A}}(G)\leq
1-\alpha\min\\{h_{H},\alpha\\}$.

As $H$ is a $\hat{\delta}$-expander (as defined above), for each
$B\in\mathcal{B}$

$e_{H}(B,V(H)\backslash B)/{\rm vol}(H)\geq\hat{\delta}x_{B}(1-x_{B}).$

Thus,

$q_{\mathcal{A}}^{E}(G)\leq 1-\frac{\alpha}{{\rm
vol}(H)}\sum_{B\in\mathcal{B}}e_{H}(B,V(H)\backslash B)\leq
1-\alpha\hat{\delta}\sum_{B\in\mathcal{B}}x_{B}(1-x_{B})$

and hence $q_{\mathcal{A}}^{E}(G)\leq
1-\alpha\hat{\delta}(1-\sum_{B\in\mathcal{B}}x_{B}^{2})$. For the degree tax

$q_{\mathcal{A}}^{D}(G)\geq\frac{\alpha^{2}}{{\rm
vol}(H)^{2}}\sum_{B\in\mathcal{B}}{\rm
vol}_{H}(B)^{2}=\alpha^{2}\sum_{B\in\mathcal{B}}x_{B}^{2}$

which establishes the statement (2.1), and thus completes the proof of
Proposition 1.2.∎

###  2.2 Proof of Proposition 1.3

We shall use two preliminary lemmas in the proof of Proposition 1.3. For a
vertex partition $\mathcal{A}$ we let $\partial_{G}(\mathcal{A})$ denote the
number of edges between the parts of $\mathcal{A}$.

It will be convenient to use a different notion of expansion for the proof of
Lemma 2.2. For a graph $H$, define its _expansion-by-edges_ ,
$h^{\prime}_{H}$, by taking the edge boundary of sets relative to the number
of edges inside the set rather than the volume of the set. Let

Figure 2.1: Step $k$ for the algorithm in Lemma 2.2. Since in $G$ any induced
subgraph $H$ with size $e(H)>e_{0}$ is not a $\delta^{\prime}$-expander-by-
edges (see definition on line (2.2)): if
$e(W)>\max\\{\tfrac{1}{2}e(G),e_{0}\\}$ there is a vertex subset $A_{k}$ with
$e(A_{k})\leq e(W\backslash A_{k})$ and $e(A_{k},W\backslash
A_{k})<\delta^{\prime}e(A_{k})$.

$h^{\prime}_{H}(A)=\frac{e_{H}(A,\bar{A})}{\min\\{e_{H}(A),e_{H}(\bar{A})\\}}\;\;\;\;\;\;\;\mbox{and}\;\;\;\;\;h^{\prime}_{H}=\min_{A}h^{\prime}_{H}(A)\,,$
(2.2)

where $\bar{A}$ denotes $V(H)\backslash A$. We say $H$ is a _$\delta^{\prime}$
-expander-by-edges_ for any $0<\delta^{\prime}\leq h^{\prime}_{H}$.

Since ${\rm vol}_{H}(A)=e_{H}(A,\bar{A})+2e_{H}(A)$, for $0\leq\delta<1$ the
inequality $e_{H}(A,\bar{A})\geq\delta\,{\rm vol}_{H}(A)$ is equivalent to
$e_{H}(A,\bar{A})\geq\frac{2\delta}{1-\delta}\,e_{H}(A)$. Hence, for
$0\leq\delta<1$

$e_{H}(A,\bar{A})\geq\delta\min\\{{\rm vol}_{H}(A),{\rm
vol}_{H}(\bar{A})\\}\;\Leftrightarrow\;e_{H}(A,\bar{A})\geq\tfrac{2\delta}{1-\delta}\min\\{e_{H}(A),e_{H}(\bar{A})\\}.$

Thus $H$ is a $\delta$-expander iff it is a $\delta^{\prime}$-expander-by-
edges where $\delta^{\prime}=\tfrac{2\delta}{1-\delta}$, i.e.
$h^{\prime}_{H}=2h_{H}/(1-h_{H})$.

######  Lemma 2.2.

Let $e_{0}>0$ and $0<\delta<1$; and let $G$ be a graph such that for all
$U\subseteq V(G)$ with $e_{G}(U)>e_{0}$ the graph $G[U]$ is not a
$\delta$-expander. Then there is a partition $\mathcal{A}$ of $V(G)$ such that

  1. (a)

each part $A$ of $\mathcal{A}$ satisfies
$e(A)\leq\max\\{\frac{1}{2}e(G),e_{0}\\}$, and

  2. (b)

$\partial_{G}(\mathcal{A})\leq\tfrac{\delta}{1+\delta}\tfrac{3+\delta}{2}\,e(G)$.

###### Proof.

Let $\delta^{\prime}=2\delta/(1-\delta)$. Observe that for each $W\subseteq
V(G)$ such that $\,e_{G}(W)>\max\\{\tfrac{1}{2}e(G),e_{0}\\}$, the graph
$G[W]$ is not a $\delta^{\prime}$-expander-by-edges, so there is a non-empty
set $A\subset W$ such that $e_{G}(A)\leq e_{G}(W\setminus A)$ and
$e_{G}(A,W\setminus A)<\delta^{\prime}\,e_{G}(A)$. Thus in the following
algorithm there will always be a set $A_{k}$ as required, and so the algorithm
will succeed and will output a partition $\mathcal{A}$ with $k+1\geq 1$ parts
$A_{j}$. See also Figure 2.1.

1

Input : G – graph with no induced $\delta^{\prime}$-expander-by-edges $H$ of
size $e(H)>e_{0}$.

Output : $\mathcal{A}$ – vertex partition of G.

2

3W $\leftarrow$ $V(\textsf{G})$, k $\leftarrow$ $0$

4while  _$e_{\textsf{G}}(\textsf{W}\,)
>\max\\{\frac{1}{2}e(\textsf{G}),e_{0}\\}$ _ do

5 k $\leftarrow$ $\textsf{k}+1$

6 pick $\varnothing\neq\textsf{A}_{\textsf{k}}\subset\textsf{W}$ with
$e_{\textsf{G}}(\textsf{A}_{\textsf{k}})\leq
e_{\textsf{G}}(\textsf{W}\backslash\textsf{A}_{\textsf{k}})$ and
$e_{\textsf{G}}(\textsf{A}_{\textsf{k}},\textsf{W}\backslash\textsf{A}_{\textsf{k}})<\delta^{\prime}e_{\textsf{G}}(\textsf{A}_{\textsf{k}})$.

7 W $\leftarrow$ $\textsf{W}\backslash\textsf{A}_{\textsf{k}}$

8

9 end while

10$\textsf{A}_{\textsf{k}+1}$ $\leftarrow$
$V(\textsf{G})\backslash(\textsf{A}_{1}\cup\ldots\cup\textsf{A}_{\textsf{k}})$

return _ $\mathcal{A}=\\{\textsf{A}_{1},\ldots\textsf{A}_{\textsf{k}+1}\\}$_

Clearly $e_{G}(A_{j})\leq\frac{1}{2}e(G)$ for each $j=1.\ldots,k$ and
$e_{G}(A_{k+1})\leq\max\\{\frac{1}{2}e(G),e_{0}\\}$, so $\mathcal{A}$ has
property (a) in the lemma.

If $k=0$ then $\mathcal{A}$ is trivial and $\partial_{G}(\mathcal{A})=0$. If
$k\geq 1$ then

$\displaystyle\partial_{G}(\mathcal{A})$ $\displaystyle=$ $\displaystyle
e_{G}(A_{1},V(G)\setminus A_{1})+e_{G}(A_{2},V(G)\setminus(A_{1}\cup
A_{2}))+\cdots+e_{G}(A_{k},A_{k+1})$ $\displaystyle\leq$
$\displaystyle\delta^{\prime}e_{G}(A_{1})+\delta^{\prime}e_{G}(A_{2})+\cdots+\delta^{\prime}e_{G}(A_{k})$
$\displaystyle=$
$\displaystyle\delta^{\prime}\,\sum_{j=1,\ldots,k}^{k}e_{G}(A_{j})\;\;=\;\;\delta^{\prime}(e(G)-e_{G}(A_{k+1})-\partial_{G}(\mathcal{A})).$

The last two steps of the algorithm ensure that $e_{G}(A_{k})\leq
e_{G}(A_{k+1})$ and $e_{G}(A_{k}\cup
A_{k+1})>\max\\{\tfrac{1}{2}e(G),e_{0}\\}$. Also, we have

$e_{G}(A_{k}\cup A_{k+1})=e_{G}(A_{k})+e_{G}(A_{k+1})+e_{G}(A_{k},A_{k+1})\leq
e_{G}(A_{k})+e_{G}(A_{k+1})+\delta^{\prime}e_{G}(A_{k}),$

where the inequality comes from line $5$ of the algorithm. Therefore, letting
$x=e_{G}(A_{k})$ and $y=e_{G}(A_{k+1})$,

$x+\delta^{\prime}x+y\geq e_{G}(A_{k}\cup
A_{k+1})>\max\\{\tfrac{1}{2}e(G),e_{0}\\}\geq\tfrac{1}{2}e(G).$

Thus, since $x\leq y$, we have $(2+\delta^{\prime})y>\tfrac{1}{2}e(G)$, and so
$y>\tfrac{1}{4+2\delta^{\prime}}e(G)$. Thus

$(1+\delta^{\prime})\,\partial_{G}(\mathcal{A})\leq\delta^{\prime}(e(G)-y)\leq\delta^{\prime}\,\tfrac{3+2\delta^{\prime}}{4+2\delta^{\prime}}\,e(G)\,.$

Hence

$\partial_{G}(\mathcal{A})\leq\tfrac{\delta^{\prime}}{1+\delta^{\prime}}\,\tfrac{3+2\delta^{\prime}}{4+2\delta^{\prime}}\,e(G)=\tfrac{\delta}{1+\delta}\tfrac{3+\delta}{2}e(G)\,,$

as required for property (b).∎

The following lemma records properties of the resulting partition after
applying the algorithm in Lemma 2.2 to each part of a given partition. Given a
vertex partition $\mathcal{A}$ of a graph $G$, let $\max\\!\texttt{_}{\rm
in}_{G}(\mathcal{A})$ denote $\max\\{e_{G}(A):A\in\mathcal{A}\\}$ and
$\max\\!\texttt{_}{\rm out}_{G}(\mathcal{A})$ denote
$\max\\{e_{G}(A,\bar{A}):A\in\mathcal{A}\\}$. Thus property (a) in the last
lemma says that $\max\\!\texttt{_}{\rm
in}_{G}(\mathcal{A})\leq\max\\{\tfrac{1}{2}e(G),e_{0}\\}$.

######  Lemma 2.3.

Let $e_{0}>0$ and $0<\delta<1$; let
$\rho=\tfrac{\delta}{1+\delta}\tfrac{3+\delta}{2}$ (so
$\delta<\rho<\tfrac{3}{2}\delta$); and let $G$ be a graph such that for all
$U\subseteq V(G)$ with $e_{G}(U)\geq e_{0}$ the graph $G[U]$ is not a
$\delta$-expander. Let $\mathcal{A}$ be a partition of $V(G)$. Then there is a
partition $\mathcal{B}$ refining $\mathcal{A}$ such that

  1. (a)

$\partial_{G}(\mathcal{B})\leq(1-\rho)\,\partial_{G}(\mathcal{A})+\rho\,e(G)\,$,
and

  2. (b)

$\max\\!\texttt{_}{\rm
in}_{G}(\mathcal{B})\leq\max\\{\tfrac{1}{2}\max\\!\texttt{_}{\rm
in}_{G}(\mathcal{A}),e_{0}\\}$, and

  3. (c)

$\max\\!\texttt{_}{\rm out}_{G}(\mathcal{B})\leq\max\\!\texttt{_}{\rm
out}_{G}(\mathcal{A})+\rho\max\\!\texttt{_}{\rm in}_{G}(\mathcal{A})$.

###### Proof.

We consider each part $A\in\mathcal{A}$ separately and apply Lemma 2.2: we see
that there is a partition $\mathcal{B}_{A}$ of $A$ such that

$\max\\!\texttt{_}{\rm
in}_{G}(\mathcal{B}_{A})\leq\max\\{\tfrac{1}{2}e_{G}(A),e_{0}\\}\leq\max\\{\tfrac{1}{2}\max\\!\texttt{_}{\rm
in}_{G}(\mathcal{A}),e_{0}\\}$

and

$\partial_{G}(\mathcal{B}_{A})\leq\rho\,e_{G}(A)\,.$ (2.3)

Putting together the partitions $\mathcal{B}_{A}$ gives a refinement
$\mathcal{B}$ of $\mathcal{A}$ such that

$\max\\!\texttt{_}{\rm
in}_{G}(\mathcal{B})\leq\max\\{\tfrac{1}{2}\max\\!\texttt{_}{\rm
in}_{G}(\mathcal{A}),e_{0}\\}$

and

$\displaystyle\partial_{G}(\mathcal{B})$ $\displaystyle=$
$\displaystyle\partial_{G}(\mathcal{A})+\sum_{A\in\mathcal{A}}\partial_{G}(\mathcal{B}_{A})\;\leq\;\partial_{G}(\mathcal{A})+\rho\sum_{A\in\mathcal{A}}e_{G}(A)$
$\displaystyle\leq$
$\displaystyle\partial_{G}(\mathcal{A})+\rho\,(e(G)-\partial_{G}(\mathcal{A}))\;=\;(1-\rho)\,\partial_{G}(\mathcal{A})+\rho\,e(G).$

For any $B\in\mathcal{B}$ and $A\in\mathcal{A}$ such that
$B\in\mathcal{B}_{A}$ observe that

$e_{G}(B,\bar{B})=e_{G}(B,A\backslash
B)+e_{G}(B,\bar{A})\leq\partial_{G}(\mathcal{B}_{A})+e_{G}(A,\bar{A}).$

and so (c) follows by (2.3) which completes the proof.∎

We may now use Lemma 2.3 to complete the proof of Proposition 1.3.

###### Proof of Proposition 1.3.

Let $k=\lceil\log_{2}\tfrac{1}{\alpha}\rceil$ and $e_{0}=\alpha e(G)$. Start
with the trivial one-part partition $\mathcal{A}^{0}$ of $V(G)$, with
$\max\\!\texttt{_}{\rm in}_{G}(\mathcal{A}^{0})=e(G)$, $\max\\!\texttt{_}{\rm
out}_{G}(\mathcal{A}^{0})=0$ and $\partial_{G}(\mathcal{A}^{0})=0$. Now apply
the last lemma $k$ times, repeatedly refining the partition. We obtain a
sequence $\mathcal{A}^{1},\ldots,\mathcal{A}^{k}$ of partitions of $V(G)$ such
that for each $j=1,\ldots,k$

$\displaystyle\partial_{G}(\mathcal{A}^{j})\leq(1-\rho)\,\partial_{G}(\mathcal{A}^{j-1})+\rho\,e(G)\,,$
(2.4) $\displaystyle\max\\!\texttt{_}{\rm
in}_{G}(\mathcal{A}^{j})\leq\max\\{2^{-j},\alpha\\}\,e(G)\,,\mbox{ }$
$\displaystyle{\max\\!\texttt{_}{\rm
out}_{G}(\mathcal{A}^{j})\leq\max\\!\texttt{_}{\rm
out}_{G}(\mathcal{A}^{j-1})+\rho\max\\!\texttt{_}{\rm
in}_{G}(\mathcal{A}^{j-1})\,.}$

Denote $\mathcal{A}^{k}$ by $\mathcal{B}$. Since $2^{-k}\leq\alpha$ we have

$\max\\!\texttt{_}{\rm in}_{G}(\mathcal{B})\leq\alpha\,e(G).$ (2.5)

Also

$\partial_{G}(\mathcal{B})\leq\rho\,e(G)\left((1-\rho)^{k-1}+\cdots+(1-\rho)+1\right)=e(G)\,(1-(1-\rho)^{k})\,,$

and $1-(1-\rho)^{k}\leq k\rho$, so $\partial_{G}(\mathcal{B})<k\rho\,e(G)$.
Hence $q^{E}_{\mathcal{B}}(G)=1-\partial_{G}(\mathcal{B})/e(G)>1-k\rho\,$.

We may also bound $\max\\!\texttt{_}{\rm out}_{G}(\mathcal{B})$ similarly,

$\max\\!\texttt{_}{\rm
out}_{G}(\mathcal{B})\leq\rho\,e(G)\left(1+\tfrac{1}{2}+\tfrac{1}{4}+\ldots+\tfrac{1}{2^{k-1}}\right)<2\rho\,e(G)\,,$
(2.6)

and hence by (2.5) and (2.6) (and since ${\rm vol}_{G}(A)\leq 2e(G)$)

$\displaystyle\max\\{{\rm vol}_{G}(A):A\in\mathcal{B}\\}$ $\displaystyle=$
$\displaystyle\max\\{2e_{G}(A)+e_{G}(A,\bar{A}):A\in\mathcal{B}\\}$ (2.7)
$\displaystyle\leq$ $\displaystyle 2\max\\!\texttt{_}{\rm
in}_{G}(\mathcal{B})+\max\\!\texttt{_}{\rm
out}_{G}(\mathcal{B})\;\;<\;2\min\\{1,(\alpha+\rho)\\}e(G).$

Recall that by convexity of the sum of squares if we have non-negative
$\\{x_{i}\\}_{i}$ with $\sum_{i}x_{i}=1$ and $\max_{i}x_{i}\leq x$ then the
quantity $\sum_{i}x_{i}^{2}$ is maximized when we take as many $x_{i}=x$ as
possible plus one $x_{j}=1-x\lfloor\frac{1}{x}\rfloor$, hence we always have
$\sum_{i}x_{i}^{2}\leq f(x)$.

For $A\in\mathcal{B}$ set $x_{A}={\rm vol}_{G}(A)/2e(G)$ and thus (2.7) gives
us

$q^{D}_{\mathcal{B}}(G)=\sum_{A\in\mathcal{B}}x_{A}^{2}<f(\min\\{1,\alpha+\rho\\})\,.$

Finally we have

$q^{*}(G)\geq q_{\mathcal{B}}(G)>1-f(\min\\{1,\alpha+\rho\\})-k\rho\,,$

and since $\rho<\frac{3}{2}\delta$ and $f$ is increasing, we obtain

$q^{*}(G)>1-f\left(\min\\{1,\alpha+\tfrac{3}{2}\delta\\}\right)-\tfrac{3k}{2}\delta$

as required. ∎

###  2.3 Proof of Theorem 1.4

Figure 2.2: The three vertex partitions of $H$ considered in the proof of
Theorem 1.4.

###### Proof of Theorem 1.4.

Let $\mathcal{A}$ be an optimal partition of $G$. Since $G$ has no isolated
vertices and $\mathcal{A}$ is optimal: for any $A\in\mathcal{A}$ the induced
subgraph $G[A]$ must be connected. Hence any part in $\mathcal{A}$ is entirely
within $V(H)$ or $V(G)\backslash V(H)$. Let $\mathcal{B}\subset\mathcal{A}$ be
the set of parts in $V(H)$. The contribution of $H$ to the modularity score of
$\mathcal{A}$ is

$\sum_{B\in\mathcal{B}}\frac{e(B)}{e(G)}-\frac{{\rm vol}(B)^{2}}{{\rm
vol}(G)^{2}}$ (2.8)

which we will denote by $q_{\mathcal{B}}(H,m)$. We shall consider three
partitions on $V(H)$: the connected component partition $\mathcal{B}_{\rm
conn}$ placing all of $V(H)$ into one part, $\mathcal{B}_{\rm witn}$ a
bipartition into $\\{U^{*},V(H)\backslash U^{*}\\}$ where $U^{*}$ is any
witness, i.e. such that $\hat{h}_{H}=\hat{h}_{H}(U^{*})$, and
$\mathcal{B}_{\rm split}$ a partition into at least two parts which achieves
the maximal value for (2.8) i.e. $\mathcal{B}_{\rm
split}=\arg\max_{|\mathcal{B}|>1}q_{\mathcal{B}}(H,m)$. See Figure 2.2. Note
it is possible that $\mathcal{B}_{\rm split}=\mathcal{B}_{\rm witn}$. We
proceed via the following three claims which together imply the theorem. Write
$\hat{\delta}=\hat{h}_{H}$.

######  Claim 2.4.

If $\hat{\delta}>\alpha$, then $q_{\mathcal{B}_{\rm
conn}}(H,m)>q_{\mathcal{B}_{\rm split}}(H,m)$.

######  Claim 2.5.

If $\hat{\delta}<\alpha$, then $q_{\mathcal{B}_{\rm
witn}}(H,m)>q_{\mathcal{B}_{\rm conn}}(H,m)$.

######  Claim 2.6.

If $\hat{\delta}=\alpha$, then $q_{\mathcal{B}_{\rm
conn}}(H,m)=q_{\mathcal{B}_{\rm witn}}(H,m)=q_{\mathcal{B}_{\rm split}}(H,m)$.

###### Proof of Claim 2.4.

Observe first that

$q_{\mathcal{B}_{\rm conn}}(H,m)=\frac{e(H)}{e(G)}-\frac{{\rm
vol}(H)^{2}}{{\rm vol}(G)^{2}}=\alpha-\alpha^{2}.$ (2.9)

Denote by $x_{B}$ the proportion of the volume of $H$ contained in part $B$,
$x_{B}={\rm vol}(B)/{\rm vol}(H)$. Then for any partition $\mathcal{B}$ of
$V(H)$

$q_{\mathcal{B}}(H,m)=\frac{e(H)}{e(G)}-\sum_{B\in\mathcal{B}}\big{(}\frac{e(B,V(H)\backslash
B)}{{\rm vol}(G)}+\frac{{\rm vol}(B)^{2}}{{\rm
vol}(G)^{2}}\big{)}=\alpha-\sum_{B\in\mathcal{B}}\big{(}\frac{\alpha\;e(B,V(H)\backslash
B)}{{\rm vol}(H)}+\alpha^{2}x_{B}^{2}\big{)}\,.$

But $e(B,V(H)\backslash B)\geq\hat{\delta}{\rm vol}(B){\rm vol}(V(H)\backslash
B)/{\rm vol}(H)$ and so by the above equation

$q_{\mathcal{B}_{\rm
split}}(H,m)\leq\alpha-\alpha\hat{\delta}\sum_{B\in\mathcal{B}_{\rm
split}}x_{B}(1-x_{B})-\alpha^{2}\sum_{B\in\mathcal{B}_{\rm
split}}x_{B}^{2}=\alpha-\alpha\hat{\delta}+\alpha(\hat{\delta}-\alpha)\sum_{B\in\mathcal{B}_{\rm
split}}x_{B}^{2}$

where the equality above is by noting $\sum_{B\in\mathcal{B}_{\rm
split}}x_{B}=1$. Hence by (2.9)

$q_{\mathcal{B}_{\rm conn}}(H,m)-q_{\mathcal{B}_{\rm
split}}(H,m)\geq\alpha(\hat{\delta}-\alpha)(1-\textstyle{\sum_{B\in\mathcal{B}_{\rm
split}}}x_{B}^{2}).$ (2.10)

Since $\sum_{B\in\mathcal{B}_{\rm split}}x_{B}^{2}<1$, if
$\hat{\delta}>\alpha$ we have $q_{\mathcal{B}_{\rm
conn}}(H,m)>q_{\mathcal{B}_{\rm split}}(H,m)$ as required.∎

###### Proof of Claim 2.5.

Note that since $U^{*}$ a witness of $\hat{h}_{H}=\hat{\delta}$, we get that
$e(U^{*},V(H)\backslash U^{*})=\hat{\delta}{\rm vol}(U^{*}){\rm
vol}(V(H)\backslash U^{*})/{\rm vol}(H)$. Thus similarly to
$q_{\mathcal{B}_{\rm split}}(H,m)$,

$q_{\mathcal{B}_{\rm
witn}}(H,m)=\alpha-\alpha\hat{\delta}+\alpha(\hat{\delta}-\alpha)(x_{U^{*}}^{2}+(1-x_{U^{*}})^{2}),$

and so

$q_{\mathcal{B}_{\rm witn}}(H,m)-q_{\mathcal{B}_{\rm
conn}}(H,m)\geq\alpha(\alpha-\hat{\delta})(1-x_{U^{*}}^{2}-(1-x_{U^{*}})^{2}).$
(2.11)

Hence if $\alpha>\hat{\delta}$ we have $q_{\mathcal{B}_{\rm
witn}}(H,m)>q_{\mathcal{B}_{\rm conn}}(H,m)$ as required. ∎

###### Proof of Claim 2.6.

This follows almost immediately from previous calculations. By (2.9) and
(2.11), if $\hat{\delta}=\alpha$ then $q_{\mathcal{B}_{\rm
conn}}(H,m)=q_{\mathcal{B}_{\rm witn}}(H,m)$; and by (2.10) if
$\hat{\delta}=\alpha$ then $q_{\mathcal{B}_{\rm conn}}(H,m)\geq
q_{\mathcal{B}_{\rm split}}(H,m)$. However by definition, always
$q_{\mathcal{B}_{\rm split}}(H,m)\geq q_{\mathcal{B}_{\rm witn}}(H,m)$; and
hence we must have equality between all three, as required.∎

∎

###  2.4 Proof of Proposition 1.7

In this subsection we often drop the subscript $G$ as it is not needed.

###### Proof of Proposition 1.7.

We first show (a) and (c) to be equivalent.

Let $G=(V,E)$ be a nonempty graph, and let $\nu={\rm vol}(G)$. For $U\subseteq
V$, let $p_{G}(U)=2e(U)\nu-{\rm vol}(U)^{2}$. Observe that
$p_{G}(\emptyset)=p_{G}(V)=0$. If $\mathcal{A}$ is a partition of $V(G)$, then
$q_{\mathcal{A}}(G)=\nu^{-2}\sum_{A\in\mathcal{A}}p_{G}(A)$. Since ${\rm
vol}(U)=2e(U)+e(U,\bar{U})$ (where $\bar{U}$ denotes $V\backslash U$), we have

$\displaystyle p_{G}(U)$ $\displaystyle=$ $\displaystyle 2e(U)\nu-{\rm
vol}(U)^{2}=({\rm vol}(U)-e(U,\bar{U}))\nu-{\rm vol}(U)(\nu-{\rm
vol}(\bar{U}))$ $\displaystyle=$ $\displaystyle-e(U,\bar{U})\nu+{\rm
vol}(U){\rm vol}(\bar{U}).$

Thus we may also write $p_{G}(U)$ as ${\rm vol}(U){\rm
vol}(\bar{U})-e(U,\bar{U})\nu$; and this expression for $p_{G}(U)$ is
symmetric in $U$ and $\bar{U}$, so $p_{G}(U)=p_{G}(\bar{U})$. Now, if
$\mathcal{A}$ is a bipartition with parts $U$ and $\bar{U}$, then

$q_{\mathcal{A}}(G)=\nu^{-2}(p_{G}(U)+p_{G}(\bar{U}))=2\nu^{-2}p_{G}(U).$

Thus there is a bipartition $\mathcal{A}$ with $q_{\mathcal{A}}(G)>0$ iff
there is a set $U$ of vertices with $p_{G}(U)>0$, iff $q^{*}(G)>0$.
Equivalently, $q^{*}(G)=0$ iff $p_{G}(A)\leq 0$ for each $A\subset V$, iff

$e(A,\bar{A})\geq\frac{{\rm vol}(A)\,{\rm vol}(\bar{A})}{{\rm
vol}(G)}\;\;\mbox{ for each }A\subseteq V\,.$

This gives the equivalence of (a) and (c) in Proposition 1.7.

Now let us prove the equivalence of (a) and (b) in Proposition 1.7. Let
$\emptyset\neq A\subset V$ and let $\mathcal{A}$ be the bipartition of $V$
with parts $A$ and $\bar{A}$. Then

$\displaystyle m^{2}q_{\mathcal{A}}(G)$ $\displaystyle=$
$\displaystyle(e(A)+e(\bar{A}))\,m-\tfrac{1}{4}((2e(A)+e(A,\bar{A}))^{2}+(2e(\bar{A})+e(A,\bar{A}))^{2}$
$\displaystyle=$
$\displaystyle(e(A)+e(\bar{A}))\left(e(A)+e(\bar{A})+e(A,\bar{A})\right)$
$\displaystyle-\left(e(A)^{2}+e(\bar{A})^{2}+(e(A)+e(\bar{A}))\,e(A,\bar{A})+\tfrac{1}{2}e(A,\bar{A})^{2}\right)$
$\displaystyle=$
$\displaystyle(e(A)+e(\bar{A}))^{2}-\left(e(A)^{2}+e(\bar{A})^{2}+\tfrac{1}{2}e(A,\bar{A})^{2}\right)$
$\displaystyle=$ $\displaystyle
2e(A)e(\bar{A})-\tfrac{1}{2}e(A,\bar{A})^{2}\,.$

Hence

$q_{\mathcal{A}}(G)>0\;\mbox{ iff }\;e(A,\bar{A})<2\sqrt{e(A)e(\bar{A})}\,,$

and so (since $q^{*}(G)>0$ iff $q_{\mathcal{A}}(G)>0$ for some bipartition
$\mathcal{A}$)

$q^{*}(G)>0\;\mbox{ iff }\;e(A,\bar{A})<2\sqrt{e(A)e(\bar{A})}\;\;\mbox{ for
some }A\subseteq V\,.$

This completes the proof.∎

##  3 Constructions

###  3.1 Constructions related to Theorem 1.1

The following proposition gives example constructions for $G_{\alpha}$ and
$G_{H}$ in the ‘converse’ statements (a)(ii) and (b)(ii) of Theorem 1.1.

######  Proposition 3.1.

Let $f(\alpha)=\alpha^{2}\lfloor 1/\alpha\rfloor+(1-\alpha\lfloor
1/\alpha\rfloor)^{2}$. For all $0<\alpha<1$ and for $m$ large enough,

  1. (a)

For any graph $H$ with $e(H)\leq\alpha m$, let $G_{H}$ on $m$ edges be
constructed by adding $m-e(H)$ disjoint edges. Then $H$ is an induced subgraph
of $G_{H}$ and $q^{*}(G_{H})\geq 1-\alpha^{2}-O(1/m)$.

  2. (b)

Let $G_{\alpha}$ on $m$ edges be constructed by taking as many cliques on
$\lfloor\sqrt{2\alpha m}\rfloor$ vertices as possible, as large as possible a
clique on the remaining edges, and disjoint edges for the rest. Then
$q^{*}(G_{\alpha})=1-f(\alpha)+O(m^{-1/2})$ and any subgraph $H$ of
$G_{\alpha}$ with $e(H)>\alpha m$ is disconnected.

###### Proof of (a).

For the graph $G_{H}$ in part (b), let $\mathcal{A}$ be the partition with one
part $V(H)$ and one part for each added isolated edge. Then

$q^{*}(G_{H})\geq q_{\mathcal{A}}(G_{H})=1-({\rm
vol}(H)^{2}+4(m-e(H))/(4m^{2})\geq 1-\alpha^{2}+O(1/m),$

as required.∎

###### Proof of (b).

By Corollary 1.5, since complete graphs have modularity value 0, the
modularity optimal partition is the connected components partition
$\mathcal{C}$, where we place each disjoint clique (including each disjoint
edge) into a separate part. Clearly
$q_{\mathcal{C}}(G_{\alpha})=1-q^{D}_{\mathcal{C}}(G_{\alpha})$. To calculate
the degree tax requires bounds on the number of edges in each clique. Let $x$
be the number of edges in a clique on $\lfloor\sqrt{2\alpha m}\rfloor$
vertices. Then $x<\alpha m$ and

$x>\tfrac{1}{2}(\sqrt{2\alpha m}-1)(\sqrt{2\alpha m}-2)=\alpha
m(1+O(m^{-1/2})).$

Hence there are $\lfloor\frac{1}{\alpha}\rfloor$ such cliques for $m$
sufficiently large, with a total of $\lfloor\frac{1}{\alpha}\rfloor\alpha
m(1+O(m^{-1/2}))$ edges. Thus the remaining clique has
$(1-\alpha\lfloor\frac{1}{\alpha}\rfloor)m(1+O(m^{-1/2}))$ edges. The degree
tax is at least the contribution of these $\lfloor\frac{1}{\alpha}\rfloor+1$
cliques, (i.e. not including the disjoint edges), thus

$q^{D}_{\mathcal{C}}(G_{\alpha})\geq\lfloor\frac{1}{\alpha}\rfloor\cdot\alpha^{2}(1+O(m^{-1/2}))^{2}+(1-\alpha\lfloor\frac{1}{\alpha}\rfloor)^{2}(1+O(m^{-1/2}))^{2}=f(\alpha)+O(m^{-1/2})$

as required.∎

###  3.2 Constructions related to Proposition 1.2(ii)

(a) The weighted graph constructed by taking the complete graph on four
vertices, $K_{4}$, and adding a loop to each vertex. Note that each weighted
degree is $a+b$.

(b) The graph constructed by taking the complete graph on four vertices,
$K_{4}$, and adding $\ell$ pendant vertices to each of its vertices.

Figure 3.1: Example construction for Proposition 1.2(ii) in (b). In Lemma 3.3
we show the modularity value and expansion constant $\hat{h}$ of the simple
graph in (b) is the same as for the weighted graph with loops in (a) for the
correct parameter values.

In this section we will construct a family of graphs and establish their
modularity values and the expansion $\hat{h}_{H}$ for a subgraph $H$. This
will prove Proposition 1.2(ii), and thus show that the inequality in
Proposition 1.2(i) is tight.

The constructed graph $G$ will consist of disjoint edges together with the
subgraph $H$, where $H$ is a complete graph with pendant vertices (leaves) -
see Figure 3.1(b). Loosely, in $H$ the pendant vertices are always grouped
together with the adjacent vertex, both for minimal expansion vertex subsets
(see Lemma 3.4) and for maximal modularity partitions (see Lemma 3.5). This
will mean that it is enough to establish expansion properties for $H^{\prime}$
a weighted complete graph with loops, and modularity values of $G^{\prime}$
where $H$ is replaced by $H^{\prime}$.

We first show that we may construct a weighted graph with loops $G_{w}$
fulfilling the claims above, and then show that we may approximate this graph
by a simple graph. See Figure 3.1(a) for an illustration of $H_{w}$ which is
used to construct $G_{w}$.

######  Lemma 3.2.

For $k\geq 2$ and $a,b>0$, let $H_{w}=H_{w}(a,b,k)$ be the weighted graph with
loops constructed by taking the complete graph on $k$ vertices with all
$\binom{k}{2}$ edges of weight $b/(k-1)$ and adding a loop of weight $a/2$ at
each vertex. Given also $0<\alpha<1$, construct $G_{w}=G_{w}(H_{w},\alpha)$ by
taking the disjoint union of $H_{w}$ and $\lfloor
e(H_{w})(1-\alpha)/\alpha\rfloor$ disjoint edges each of weight 1. Then

  1. (i)

$\hat{h}_{H_{w}}=\frac{b}{a+b}(1+\frac{1}{k-1});$

  2. (ii)

for any $\varepsilon>0$ we may take $k$ large enough such that

$q^{*}(G_{w})\geq 1-\alpha\min\\{\hat{h}_{H_{w}},\alpha\\}-\varepsilon.$

Observe that the graph $H_{w}$ is regular with weighted degree $a+b$ at each
vertex, and thus ${\rm vol}(H_{w})=k(a+b)$.

###### Proof of (i).

Let $U_{j}$ be a set of $1\leq j<k$ vertices of $H_{w}$ (by symmetry all such
sets of size $j$ are equivalent), and note that

$\hat{h}_{H_{w}}(U_{j})=\frac{e(U_{j},\bar{U_{j}}){\rm vol}(H_{w})}{{\rm
vol}(U_{j}){\rm vol}(\bar{U_{j}})}=\frac{j(k-j)b(k-1)^{-1}\cdot
k(a+b)}{j(a+b)\cdot(k-j)(a+b)}=\frac{b}{a+b}\big{(}1+\frac{1}{k-1}\big{)}$
(3.1)

which is independent of $j$. But then

$\hat{h}_{H_{w}}=\min_{j}\hat{h}_{H_{w}}(U_{j})=\frac{b}{a+b}\big{(}1+\frac{1}{k-1}\big{)}$

as required.∎

###### Proof of (ii).

Let $m=e(G_{w})$ and let $\alpha^{\prime}=e(H_{w})/e(G_{w})$. Note that
$m=e(H_{w})+\lfloor e(H_{w})(\alpha^{-1}-1)\rfloor$ so
$\alpha\leq\alpha^{\prime}<\alpha(1+1/m)$. The modularity optimal partitions
of $G_{w}$ will place each disjoint edge in its own part and hence

$\displaystyle q^{*}(G_{w})$ $\displaystyle=$
$\displaystyle(1-\alpha^{\prime})(1-1/m)+\max_{\mathcal{B}}\sum_{B\in\mathcal{B}}\frac{{\rm
vol}(B)}{{\rm vol}(G_{w})}\Big{(}\frac{2e(B)}{{\rm vol}(B)}-\frac{{\rm
vol}(B)}{{\rm vol}(G_{w})}\Big{)}$ (3.2) $\displaystyle=$
$\displaystyle(1-\alpha^{\prime})(1-1/m)+\alpha^{\prime}\max_{\mathcal{B}}\sum_{B\in\mathcal{B}}\frac{{\rm
vol}(B)}{{\rm vol}(H_{w})}f(B)$

where the max is over partitions $\mathcal{B}$ of $V(H_{w})$ and

$f(B)=\frac{2e(B)}{{\rm vol}(B)}-\frac{{\rm vol}(B)}{{\rm vol}(G_{w})}.$

Again, let $U_{j}$ be a set of $j$ vertices of $H_{w}$. We may calculate that
$e(U_{j})=(\binom{j}{2}b/(k-1)+ja/2)$ and ${\rm vol}(U_{j})=j(a+b)$. Also,
that $2m={\rm vol}(H_{w})/\alpha^{\prime}=k(a+b)/\alpha^{\prime}$. Hence

$f(U_{j})=\frac{j(j-1)b/(k-1)+ja}{j(a+b)}-\frac{\alpha^{\prime}j(a+b)}{k(a+b)}=\frac{(j-1)b/(k-1)+a}{a+b}-\frac{\alpha^{\prime}j}{k}.$

Rearranging, and recalling the expression for $\hat{h}_{H_{w}}$ shown in part
(i), we get

$f(U_{j})=\frac{j}{k}\Big{(}\frac{bk}{(k-1)(a+b)}-\alpha^{\prime}\Big{)}+\frac{a}{a+b}-\frac{b}{(k-1)(a+b)}=\frac{j}{k}(\hat{h}_{H_{w}}-\alpha^{\prime})+1-\hat{h}_{H_{w}},$

where the second equality follows by adding $b/(a+b)$ to the second term and
subtracting $b/(a+b)$ from the third term. Thus the $j$ which maximises
$f(U_{j})$ depends on the relative values of $\hat{h}_{H_{w}}$ and
$\alpha^{\prime}$ :

$\max_{j}f(U_{j})=\begin{cases}f(U_{1})=1-\hat{h}_{H_{w}}+\tfrac{1}{k}(\hat{h}_{H_{w}}-\alpha^{\prime})&\mbox{
if $\hat{h}_{H_{w}}<\alpha^{\prime}$ }\\\ f(U_{k})=1-\alpha^{\prime}&\mbox{ if
$\hat{h}_{H_{w}}\geq\alpha^{\prime}$ .}\end{cases}$

Since the sum in (3.2) is a weighted average of values $f(B)$, its maximum
value is at most $\max_{j}f(U_{j})$, and clearly $f(U_{1})$ and $f(U_{m})$ can
be achieved. Hence

$\max_{\mathcal{B}}\sum_{B\in\mathcal{B}}\frac{{\rm vol}(B)}{{\rm
vol}(H_{w})}f(B)=\begin{cases}1-\hat{h}_{H_{w}}+\frac{1}{k}(\hat{h}_{H_{w}}-\alpha^{\prime})&\mbox{
if $\hat{h}_{H_{w}}<\alpha^{\prime}$ }\\\ 1-\alpha^{\prime}&\mbox{ if
$\hat{h}_{H_{w}}\geq\alpha^{\prime}$ }\end{cases}$

and so by (3.2)

$q^{*}(G_{w})=\begin{cases}(1-\alpha^{\prime})(1-1/m)+\alpha^{\prime}\big{(}1-\hat{h}_{H_{w}}+\frac{1}{k}(\hat{h}_{H_{w}}-\alpha^{\prime})\big{)}&\mbox{
if $\hat{h}_{H_{w}}<\alpha^{\prime}$ }\\\
(1-\alpha^{\prime})(1-1/m)+\alpha^{\prime}(1-\alpha^{\prime})&\mbox{ if
$\hat{h}_{H_{w}}\geq\alpha^{\prime}$ .}\end{cases}$

By taking $k$ large enough (which for fixed $a,b$ implies $m$ large enough)

$q^{*}(G_{w})\geq 1-\alpha\min\\{\hat{h}_{H_{w}},\alpha\\}-\varepsilon$

as required.∎

######  Lemma 3.3.

For $k\geq 2$ and $\ell\geq 1$, let $H=H(k,\ell)$ be the simple graph
constructed by taking the complete graph on $k$ vertices with and adding
$\ell$ leaves at each vertex. Construct $G=G(H,\alpha)$ by taking the disjoint
union of $H$ and $\lfloor e(H)(1-\alpha)/\alpha\rfloor$ disjoint edges. Let
$H_{w}=H_{w}(2\ell,k-1,k)$ and $G_{w}=G_{w}(H_{w},\alpha)$ be the weighted
graphs with loops as defined in Lemma 3.2. Then

  1. (i)

$q^{*}(G)=q^{*}(G_{w})$ and

  2. (ii)

$\hat{h}_{H}=\hat{h}_{H_{w}}$.

To prove Lemma 3.3 we need results on which vertex subsets $U$ minimise
$\hat{h}(U)$ in $G$ and $G_{w}$ and which vertex partitions $\mathcal{A}$
maximise $q_{\mathcal{A}}(G)$ and $q_{\mathcal{A}}(G_{w})$. The following
result is elementary but for completeness we provide a proof.

######  Lemma 3.4.

Let $H$ be a connected graph and let $\emptyset\neq U^{*}\subsetneq V(H)$ be
such that $\hat{h}_{H}=\hat{h}(U^{*})$. Then $H[U^{*}]$ and $H[V\backslash
U^{*}]$ are connected.

###### Proof.

Suppose not and let $U^{*}$ be such that $\hat{h}_{H}=\hat{h}_{H}(U^{*})$ but
at least one of $H[U^{*}]$ and $H[V\backslash U^{*}]$ is disconnected. Choose
$U\in\\{U^{*},V\backslash U^{*}\\}$ with $G[U]$ disconnected. We will show
there exists $\emptyset\neq U^{\prime}\subsetneq U$ such that
$\hat{h}(U^{\prime})<\hat{h}(U)=\hat{h}(U^{*})$ which will prove the result.

As $H[U]$ is disconnected, it is the disjoint union of $H[U_{1}]$ and
$H[U_{2}]$ for some $\emptyset\neq U_{1}\subsetneq U$ and $U_{2}=U\backslash
U_{1}$. Note that since $e(U_{1},U_{2})=0$ we have

$e(U,V\backslash U)=e(U_{1},V\backslash U_{1})+e(U_{2},V\backslash U_{2})$

and thus

$\frac{\hat{h}(U)}{{\rm vol}(H)}=\frac{{\rm vol}(U_{1})}{{\rm
vol}(U_{1})\\!+\\!{\rm vol}(U_{2})}\underbrace{\frac{e(U_{1},V\backslash
U_{1})}{{\rm vol}(U_{1}){\rm vol}(V\backslash U)}}_{\lozenge}+\frac{{\rm
vol}(U_{2})}{{\rm vol}(U_{1})\\!+\\!{\rm
vol}(U_{2})}\underbrace{\frac{e(U_{2},V\backslash U_{2})}{{\rm vol}(U_{2}){\rm
vol}(V\backslash U)}}_{\blacklozenge}.$

Since $\hat{h}(U)/{\rm vol}(H)$ is a weighted average of terms ($\lozenge$)
and ($\blacklozenge$), one of the terms must be at most $\hat{h}(U)/{\rm
vol}(H)$: w.l.o.g. this is ($\lozenge$) the term involving $U_{1}$. Hence we
may assume

$\frac{\hat{h}(U)}{{\rm vol}(H)}\geq\frac{e(U_{1},V\backslash U_{1})}{{\rm
vol}(U_{1}){\rm vol}(V\backslash U)}.$ (3.3)

However, $H$ has no isolated vertices so ${\rm vol}(V\backslash U)<{\rm
vol}(V\backslash U_{1})$, and thus in particular

$\frac{\hat{h}(U_{1})}{{\rm vol}(H)}=\frac{e(U_{1},V\backslash U_{1})}{{\rm
vol}(U_{1}){\rm vol}(V\backslash U_{1})}<\frac{e(U_{1},V\backslash
U_{1})}{{\rm vol}(U_{1}){\rm vol}(V\backslash U)}.$

Hence by (3.3) we have $\hat{h}(U_{1})<\hat{h}(U)$, as required.∎

The following lemma will imply that for the graph $G$ in Lemma 3.3 \- see also
Figure 3.1(b) - for any modularity optimal partition each pendant leaf is
always together in the same part as the vertex in the complete graph which
they are incident with.

######  Lemma 3.5 ([7, 31]).

Suppose that $G$ is a graph that contains no isolated vertices and no loops.
If $\mathcal{A}$ is a partition of $V(G)$ such that
$q_{\mathcal{A}}(G)=q^{*}(G)$ then, for every $A\in\mathcal{A}$, $G[A]$ is a
connected subgraph of $G$ with at least one edge.

We are now ready to prove that the graph illustrated in Figure 3.1(b) has the
modularity claimed.

###### Proof of Lemma 3.3(i).

Given a graph $J$ let $\widetilde{J}$ be the graph obtained as follows: for
each vertex $v$ with degree at least 2 and with $\ell\geq 1$ adjacent leaves,
delete the leaves and add a loop at $v$ with weight $\ell$; and for each
isolated edge $uv$ delete the edge and add a loop of weight 1 at $u$ (say).
Each vertex partition $\mathcal{A}$ of $J$ induces a partition
$\widetilde{\mathcal{A}}$ of $\widetilde{J}$, where $\widetilde{\mathcal{A}}$
is obtained from $\mathcal{A}$ by deleting vertices in $V(J)\backslash
V(\widetilde{J})$.

Recall that the graph $G=G(H,\alpha)$ consists of disjoint edges together with
the graph $H(k,\ell)$ (the $k$-clique with $\ell$ pendant leaves at each of
its $k$ vertices). Thus $\widetilde{G}$ consists of disjoint loops and a
$k$-clique with a weight $\ell$ loop at each vertex and weight 1 edges in the
clique, so $\widetilde{G}$ is the graph $G_{w}$.

We say that a partition $\mathcal{A}$ for a graph $J$ is _pendant-consistent_
if for each pendant vertex $v$ with pendant edge $uv$ there is a part
$A\in\mathcal{A}$ with $u,v\in A$. It is easy to see that if $\mathcal{A}$ is
pendant consistent for $J$ then
$q_{\mathcal{A}}(J)=q_{\widetilde{\mathcal{A}}}(\widetilde{J})$. But by Lemma
3.5, any modularity optimal partition for $J$ is pendant consistent, so
$q^{*}(J)=q^{*}(\widetilde{J})$. Hence
$q^{*}(G)=q^{*}(\widetilde{G})=q^{*}(G_{w})$, as required.∎

###### Proof of Lemma 3.3(ii).

We first observe that for any set $\\{u\\}$ consisting of a single vertex
$u\in V(H)$ we have $\hat{h}_{H}(\\{u\\})>1$. To see this, note that since $H$
has no loops, $e(\\{u\\},V(H)\backslash\\{u\\})=\deg(u)={\rm vol}(\\{u\\})$,
and hence

$\hat{h}_{H}(\\{u\\})=\frac{{\rm vol}(H)}{{\rm
vol}(V(H)\backslash\\{u\\})}=\frac{{\rm vol}(H)}{{\rm vol}(H)-\deg(u)}>1$

as by construction $H$ has no isolated vertices.

Also, note that $\hat{h}_{H}<1$. To see this, for example let $U$ consist of
$1\leq j\leq k-1$ vertices from the $k$-clique together with their $j\ell$
adjacent leaves: then

$\hat{h}_{H}(U)=\frac{j(k-j)\cdot
k(2\ell+k-1)}{j(2\ell+k-1)\cdot(k-j)(2\ell+k-1)}=\frac{k}{2\ell+k-1}<1.$

Let $U_{2}$ minimise $\hat{h}_{H}(U)$ over $\emptyset\neq U\subsetneq V(H)$;
and note that by the above we must have $2\leq|U_{2}|\leq n-2$, where
$n=|V(H)|=k(\ell+1)$.

######  Claim 3.6.

The partition $\\{U_{2},V(H)\backslash U_{2}\\}$ is pendant-consistent.

###### Proof of Claim 3.6.

Suppose for a contradiction that there exists a leaf $u$ and pendant edge $uv$
such that $u\in U_{2}$ and $v\in V(H)\backslash U_{2}$ or vice-versa. W.l.o.g.
we may assume $u\in U_{2}$ and $v\in V(H)\backslash U_{2}$. Recall by Lemma
3.4 both $H[U_{2}]$ and $H[V(H)\backslash U_{2}]$ are connected. Since
$|U_{2}|\geq 2$ there must be another vertex $w$ with $w\in U_{2}$. However,
since $v\notin U_{2}$ and $u$ is a leaf it must be that $H[U_{2}]$ is
disconnected and we have proven the claim. ∎

Similar to the proof of part (i), for $U$ such that the partition
$\\{U,V(H)\backslash U\\}$ is pendant-consistent we have
$\hat{h}_{H}(U)=\hat{h}_{H_{w}}(\widetilde{U})$. Thus by the claim we have

$\hat{h}_{H}(U_{2})=\hat{h}_{H_{w}}(\widetilde{U_{2}})=\hat{h}_{H_{w}}$

since the minimum of $\hat{h}_{H_{w}}(B)$ is obtained by all non-empty sets
$B\subset V(H_{w})$ \- see (3.1). This completes the proof of part (ii). ∎

###  3.3 Constructions related to Corollary 1.8

The following lemma shows that the converse of Corollary 1.8 does not hold.

######  Lemma 3.7.

Windmill graphs. For $\ell\geq 2$ construct the windmill graph $W_{\ell}$ by
taking a star with $2\ell$ leaves and adding a perfect matching between the
leaf vertices. Then

$h_{W_{\ell}}=1/2$ (3.4)

and

$q^{*}(W_{\ell})>0.$ (3.5)

See Figure 3.2 for an illustration of $W_{8}$.

Figure 3.2: The windmill graph $W_{8}$, see Lemma 3.7.

###### Proof of (3.4).

We will show that for each non-empty set $X$ of vertices with ${\rm
vol}(X)\leq{\rm vol}(\bar{X})$ we have

$h_{W_{\ell}}(X)=e(X,\bar{X})/{\rm vol}(X)\geq 1/2$

with equality for some such set $X$. Observe that ${\rm vol}(W_{\ell})=6\ell$,
and so we consider $X$ with ${\rm vol}(X)\leq 3\ell$.

Denote the central vertex by $v$. Notice that to show $h_{W_{\ell}}(X)\geq
1/2$ for all $X$ as above it suffices to show that $h_{W_{\ell}}(X)\geq 1/2$
for $X$ with $W_{\ell}[X]$ connected. Hence if $v\notin X$ there are only two
cases to check: if $|X|=1$ then $X$ consists of a single non-central vertex
and $h_{W_{\ell}}(X)=e(X,\bar{X})/{\rm vol}(X)=2/2=1$, and if $|X|=2$ then $X$
consists of two non-central vertices connected by an edge and
$h_{W_{\ell}}(X)=e(X,\bar{X})/{\rm vol}(X)=2/4=1/2$. Note this second case
shows that $h_{W_{\ell}}\leq 1/2$.

Now it remains only to consider vertex subsets containing the central vertex.
Let $X_{j}$ consist of the central vertex $v$ and $j$ non-central vertices.
Then ${\rm vol}(X_{j})=2\ell+2j$ and thus we may assume $j\leq\ell/2$ (so that
${\rm vol}(X_{j})\leq 3\ell)$. Hence, considering just edges between the
central vertex $v$ and vertices in $\bar{X_{j}}$, we have that
$e(X_{j},\bar{X_{j}})\geq 2\ell-j\geq 3\ell/2$. Thus,

$h_{W_{\ell}}(X_{j})=e(X_{j},\bar{X}_{j})/{{\rm
vol}(X_{j})}\geq(3\ell/2)/(3\ell)\geq 1/2,$

which completes the proof of (3.4).∎

###### Proof of (3.5)..

Let $A$ be a vertex set consisting of an adjacent pair of non-central vertices
and define the bipartition $\mathcal{A}=\\{A,V(W_{\ell})\backslash A\\}$. This
has edge contribution $q^{E}_{\mathcal{A}}(W_{\ell})=1-2/(3\ell)$. To
calculate the degree tax, note ${\rm vol}(A)=4$, and so
$\sum_{A\in\mathcal{A}}{\rm vol}(A)^{2}=4^{2}+(6\ell-4)^{2}$ and thus
$q^{D}_{\mathcal{A}}(W_{\ell})=1-(12\ell-8)/(9\ell^{2})$. Hence for $\ell\geq
2$,

$q^{*}(W_{\ell})\geq q_{\mathcal{A}}(W_{\ell})=\frac{6\ell-8}{9\ell^{2}}>0$

which completes the proof of (3.5). ∎

##  4 Parameterising by volume

In this paper so far we have considered the modularity of graphs $G$ with
subgraphs $H$ of relative size $e(H)/e(G)\geq\alpha$. We also could have
considered subgraphs $H$ of relative volume ${\rm vol}_{G}(H)/{\rm
vol}(G)\geq\beta$; that is, parameterising by the relative volume of the
subgraph instead of the relative number of edges. (Here we write ${\rm
vol}_{G}(H)$ for ${\rm vol}_{G}(V(H))$.) Note that if $H$ has relative size
$\alpha$ then it has relative volume $\geq\alpha/2$ but the relative volume
could be $>1/2$ (even for small $\alpha>0$ \- see the construction that
follows). Let us consider briefly whether there are corresponding versions of
Propositions 1.2 (i) and 1.3 (i) under this parameterisation.

The lower bound for $q^{*}(G)$ (in terms of $\beta$ and $h_{H}$) analogous to
that in Proposition 1.3 (i) (in terms of $\alpha$ and $h_{H}$) works nicely,
see Proposition 4.1 below. However, there is no upper bound for $q^{*}(G)$
corresponding to that in Propositions 1.2 (i), as we may see from the
following example. For any $\varepsilon>0$, we construct a graph $G$ with
modularity $q^{*}(G)\geq 1-\varepsilon$ and an induced subgraph $H$ of $G$
with $h_{H}=1$ which has volume at least half that of $G$. Recall from
Proposition 1.2 (i) that, for all $0<\alpha\leq 1$, for every graph $G$ with
subgraph $H$ of relative size $e(H)/e(G)\geq\alpha$, we have $q^{*}(G)\leq
1-\alpha\min\\{h_{H},\alpha\\}$. Let $\eta>0$ be arbitrarily small. The graphs
$G$ which we shall construct show that it is not true that for all
$0<\beta\leq 1$, for every graph $G$ with an induced subgraph $H$ of relative
volume ${\rm vol}(H)/{\rm vol}(G)\geq\beta$, we have $q^{*}(G)\leq
1-\eta\,\beta\min\\{h_{H},\beta\\}$.

Given $\varepsilon>0$ we construct such a graph $G$ as follows. Let $k\geq
2/\varepsilon$, let $H$ be the $k$-edge star, and let $G$ be formed by
attaching $k$ leaves to each leaf of $H$. Equivalently let $G$ be a $k$-ary
tree of depth two. Thus $G$ has $k^{2}+k+1$ vertices and $k^{2}+k$ edges. Also
$h_{H}=1$; and ${\rm vol}_{G}(H)=k^{2}+2k$, so ${\rm vol}_{G}(H)/{\rm
vol}(G)>1/2$. Let $\mathcal{A}$ be the $(k+1)$-part partition of $V(G)$ with a
part for each leaf of the inner star $H$ along with its adjacent leaves, and a
part for the central vertex (on in its own). Then
$q_{\mathcal{A}}^{E}(G)=1-k/(k^{2}+k)>1-1/k$. Also $\mathcal{A}$ has $k$ parts
of the same volume (namely $2k+1$) and one of smaller volume (namely $k$), so
$q_{\mathcal{A}}^{D}(G)<1/k$. Thus $q^{*}(G)\geq q_{\mathcal{A}}(G)>1-2/k\geq
1-\varepsilon$, as claimed.

The following result gives a lower bound on $q^{*}(G)$ corresponding to that
in Proposition 1.3 (i). The function $f$ is defined in (1.4).

######  Proposition 4.1.

Let $0<\beta,\delta\leq 1$, let $G$ be a graph, and suppose that each induced
subgraph $H$ with relative volume ${\rm vol}_{G}(H)/{\rm vol}(G)>\beta$ has
$h_{H}<\delta$. Then

$q^{*}(G)\geq 1-f(\beta)-2\delta\,\lceil\log_{2}\tfrac{1}{\beta}\rceil\,.$

The proof follows the general approach of Lasoń and Sulkowska [24].

###### Proof.

Let $V=V(G)$. Given a graph $J$ on $V$ we let $\mathcal{C}(J)$ denote the
partition of $V$ into the vertex sets of the connected components of $J$. We
start with the graph $G$ and $\mathcal{C}(G)$, and repeatedly delete edges to
form a subgraph $G^{\prime}$ with partition $\mathcal{C}(G^{\prime})$, until
no large components remain. Each component of each graph $G^{\prime}$ is an
induced subgraph of $G$.

while the current graph $J$ is such that some part $A$ in $\mathcal{C}(J)$ has
${\rm vol}_{G}(A)>\beta\,{\rm vol}(G)$

find $\emptyset\neq S\subset A$ such that ${\rm vol}_{G}(S)\leq{\rm
vol}_{G}(A\backslash S)$ and $e_{G}(S,A\backslash S)<\delta\,{\rm
vol}_{G}(S)$, and

delete the edges in $E_{G}(S,A\backslash S)$ to form the next current graph.

Note that in the ‘while loop’ above, the component of $J$ on $A$ is the
induced subgraph $G[A]$ and (hence by assumption) is not a $\delta$-expander,
so we may choose $S$ such that

$e_{G}(S,A\backslash S)<\delta\,\min\\{{\rm vol}_{H}(S),{\rm
vol}_{H}(A\backslash S)\\}\leq\delta\,{\rm vol}_{G}(S)\,.$

Let $\hat{G}$ be the final graph, and let $\mathcal{Q}$ be the final partition
$\mathcal{C}(\hat{G})$ of $V$. Note that each part $Q$ has ${\rm
vol}_{G}(Q)\leq\beta\,{\rm vol}(G)$, so $q_{\mathcal{Q}}^{D}(G)\leq f(\beta)$.
Let $X$ be the set of all edges deleted in the process, so
$X=\bigcup_{Q\in\mathcal{Q}}\,e_{G}(Q,V\backslash Q)$ and
$q_{\mathcal{Q}}^{E}(G)=1-|X|/e(G)$. We shall upper bound $|X|$.

Initially assign weight $w(v)=0$ for each $v\in V(G)$. Each time in the ‘while
loop’, when we use $S$ to split $A$, the total number of edges deleted
increases by $e_{G}(S,A\backslash S)<\delta\,{\rm vol}_{G}(S)$. For each $v\in
S$ we increase the weight $w(v)$ by $\delta\,\deg_{G}(v)$, so $\sum_{v\in
V}w(v)$ increases by $\delta\,{\rm vol}_{G}(S)$. Thus at each stage of the
process the number of edges deleted so far is at most $\sum_{v\in V}w(v)$; and
so for the final weights $w(v)$ at the end of the process, $|X|\leq\sum_{v\in
V}w(v)$. But when a vertex $v$ in a part $A$ has its weight increased, the new
part $A^{\prime}$ containing $v$ has ${\rm
vol}_{G}(A^{\prime})\leq\frac{1}{2}{\rm vol}_{G}(A)$, so this can happen at
most $\lceil\log_{2}\frac{1}{\beta}\rceil$ times. Thus
$w(v)\leq\lceil\log_{2}\frac{1}{\beta}\rceil\,\delta\,\deg_{G}(v)$ for each
$v\in V$, and so $|X|\leq\delta\,\lceil\log_{2}\frac{1}{\beta}\rceil\cdot{\rm
vol}(G)$.

Finally we have

$q^{*}(G)\geq
q_{\mathcal{Q}}(G)=q_{\mathcal{Q}}^{E}(G)-q_{\mathcal{Q}}^{D}(G)\geq
1-|X|/e(G)-f(\beta)\geq
1-f(\beta)-2\delta\,\lceil\log_{2}\tfrac{1}{\beta}\rceil\,,$

as required.∎

##  5 Open questions

A direct consequence of Proposition 1.2, taking $H=G$ and $\alpha=1$, is the
following. (Recall that $h_{G}$ and $\hat{h}_{G}$ are the edge expansion
parameters defined in Section 1.1.)

######  Corollary 5.1.

For any graph $G$ we have

$q^{*}(G)\leq 1-\max\\{\hat{h}_{G},1\\}\leq 1-h_{G}.$ (5.1)

In Proposition 1.2(ii) we showed that the first inequality in (5.1) is tight :
for all $\varepsilon>0$ and $0\leq\hat{\delta}\leq 1$, we can find a graph $G$
with $|\hat{h}_{G}-\hat{\delta}|<\varepsilon$ and with $q^{*}(G)\geq
1-\hat{h}_{G}-\varepsilon$. The construction is a clique with pendant leaves
as depicted in Figure 3.1(b).

However, it is not clear whether the second bound in (5.1) is tight for all
values of edge expansion. The open question is to find the right upper bound
for modularity in terms of $h_{G}$.

######  Open Question 5.2.

What is the optimal function $f$ for which is it true that for any graph $G$
we have $q^{*}(G)\leq 1-f(h_{G})$?

We have a family of examples such that $q^{*}(G)\geq 1-2h_{G}-\varepsilon$.
Hence by these examples and Corollary 5.1, $x\leq f(x)\leq 2x$.

For $\delta=1$ we may take $G$ a single edge, then $h_{G}=1$ and $q^{*}(G)=0$
and thus the bound $q^{*}(G)\leq 1-h_{G}$ in (5.1) is tight for $G=K_{2}$.
Similarly for all $\varepsilon>0$ if we take $G$ a sufficiently long path then
$h_{G}<\varepsilon$ and $q^{*}(G)>1-\varepsilon$ which gives an example where
the bound in (5.1) is tight for $\delta=0$. For $0<\delta<1$ we have no such
examples, and the question is open.

If Corollary 5.1 is tight, this means that a very regular expander exists, in
which all big subsets of vertices have roughly the same edge expansion.
Otherwise, it would imply that there is a structural reason why, in any graph,
big subsets of vertices cannot all have the same edge expansion.

## Acknowledgements

We are grateful to Prasad Tetali for helpful discussions.

## References

  * [1] M. Ajtai, J. Komlos, and E. Szemeredi.  Deterministic simulation in logspace.  In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, page 132–140, New York, NY, USA, 1987. Association for Computing Machinery.
  * [2] N. Alon.  Eigenvalues and expanders.  Combinatorica, 6(2):83–96, 1986.  Theory of computing (Singer Island, Fla., 1984).
  * [3] P. J. Bickel and A. Chen.  A nonparametric view of network models and newman–girvan and other modularities.  Proceedings of the National Academy of Sciences, 106(50):21068–21073, 2009.
  * [4] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre.  Fast unfolding of communities in large networks.  Journal of Statistical Mechanics: Theory and Experiment, 10, 2008\.
  * [5] M. Bolla, B. Bullins, S. Chaturapruek, S. Chen, and K. Friedl.  Spectral properties of modularity matrices.  Linear Algebra and Its Applications, 473:359–376, 2015.
  * [6] J. Böttcher, K. P. Pruessmann, A. Taraz, and A. Würfl.  Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs.  European Journal of Combinatorics, 31(5):1217–1227, 2010.
  * [7] U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner.  On modularity clustering.  Knowledge and Data Engineering, IEEE Transactions on, 20(2):172–188, 2008.
  * [8] D. Chakraborti, J. Kim, J. Kim, M. Kim, and H. Liu.  Well-mixing vertices and almost expanders.  Proceedings of the American Mathematical Society, 2022.
  * [9] J. Cheeger.  A lower bound for the smallest eigenvalue of the laplacian.  In Proceedings of the Princeton conference in honor of Professor S. Bochner, pages 195–199, 1969.
  * [10] F. Chung.  Spectral graph theory, volume 92.  American Mathematical Soc. Providence, RI, 1997.
  * [11] V. Cohen-Addad, A. Kosowski, F. Mallmann-Trenn, and D. Saulpic.  On the power of louvain in the stochastic block model.  Advances in Neural Information Processing Systems, 33, 2020.
  * [12] E. Davis and S. Sethuraman.  Consistency of modularity clustering on random geometric graphs.  Annals of Applied Probability, 28(4):2003–2062, 2018.
  * [13] D. Fasino and F. Tudisco.  An algebraic analysis of the graph modularity.  SIAM Journal on Matrix Analysis and Applications, 35(3):997–1018, 2014.
  * [14] S. Fortunato.  Community detection in graphs.  Phys. Rep., 486(3-5):75–174, 2010.
  * [15] S. Fortunato and M. Barthélemy.  Resolution limit in community detection.  Proceedings of the National Academy of Sciences, 104(1):36–41, 2007\.
  * [16] D. Gillman.  A Chernoff bound for random walks on expander graphs.  SIAM J. Comput., 27(4):1203–1220, 1998.
  * [17] S. Hoory, N. Linial, and A. Wigderson.  Expander graphs and their applications.  Bull. Amer. Math. Soc. (N.S.), 43(4):439–561, 2006.
  * [18] R. Kannan, L. Lovász, and M. Simonovits.  Isoperimetric problems for convex bodies and a localization lemma.  Discrete & Computational Geometry, 13(3):541–559, 1995.
  * [19] R. Kannan, S. Vempala, and A. Vetta.  On clusterings: good, bad and spectral.  J. ACM, 51(3):497–515, 2004.
  * [20] M. Koshelev.  Modularity in planted partition model.  Computational Management Science, 20(1):34, 2023.
  * [21] M. Krivelevich.  Finding and using expanders in locally sparse graphs.  SIAM J. Discrete Math., 32(1):611–623, 2018.
  * [22] M. Krivelevich.  Expanders—how to find them, and what to find in them.  Surveys in Combinatorics, pages 115–142, 2019.
  * [23] A. Lancichinetti and S. Fortunato.  Limits of modularity maximization in community detection.  Physical Review E, 84(6):066122, 2011.
  * [24] M. Lasoń and M. Sulkowska.  Modularity of minor-free graphs.  Journal of Graph Theory, 2022.
  * [25] L. Lichev and D. Mitsche.  On the modularity of 3‐regular random graphs and random graphs with given degree sequences.  Random Structures & Algorithms, 61(4):754–802, 2022.
  * [26] B. Louf and F. Skerman.  Finding large expanders in graphs: from topological minors to induced subgraphs.  Electronic Journal of Combinatorics, 30(1), 2023.
  * [27] S. Majstorovic and D. Stevanovic.  A note on graphs whose largest eigenvalues of the modularity matrix equals zero.  Electronic Journal of Linear Algebra, 27(1):256, 2014.
  * [28] C. McDiarmid and F. Skerman.  Modularity of regular and treelike graphs.  Journal of Complex Networks, 6(4), 2018.
  * [29] C. McDiarmid and F. Skerman.  Modularity of Erdős-Rényi random graphs.  Random Structures & Algorithms, 57(1):211–243, 2020.
  * [30] C. McDiarmid and F. Skerman.  Modularity of nearly complete graphs and bipartite graphs.  arXiv preprint arXiv:2311.06875, 2023.
  * [31] K. Meeks and F. Skerman.  The parameterised complexity of computing the maximum modularity of a graph.  Algorithmica, 82(8):2174–2199, 2020.
  * [32] F. de Montgolfier, M. Soto, and L. Viennot.  Asymptotic modularity of some graph classes.  In Algorithms and Computation, pages 435–444. Springer, 2011.
  * [33] M. E. J. Newman and M. Girvan.  Finding and evaluating community structure in networks.  Physical Review E, 69(2):026113, 2004.
  * [34] M. A. Porter, J.-P. Onnela, and P. J. Mucha.  Communities in networks.  Notices Amer. Math. Soc., 56(9):1082–1097, 2009.
  * [35] L. O. Prokhorenkova, P. Prałat, and A. Raigorodskii.  Modularity in several random graph models.  Electronic Notes in Discrete Mathematics, 61:947–953, 2017.
  * [36] V. A. Traag, L. Waltman, and N. J. Van Eck.  From louvain to leiden: guaranteeing well-connected communities.  Scientific reports, 9(1):5233, 2019.
  * [37] P. Van Mieghem, X. Ge, P. Schumm, S. Trajanovski, and H. Wang.  Spectral graph analysis of modularity and assortativity.  Physical Review E, 82(5):056113, 2010.