Modularity of Preferential Attachment Graphs

Real-world networks, ranging from social and information networks to biological and technological infrastructures, often exhibit a rich community structure. Detecting and analyzing such communities has far-reaching applications: identifying groups of common interest in social media, classifying spam and misinformation, retrieving related content, uncovering proteins with similar biological functions, optimizing large-scale infrastructures, improving network visualization, etc. [19, 28].

To model these networks mathematically, preferential attachment graphs have become one of the main paradigms. Their early forms appeared as random recursive trees [22, 35]. However, the in-depth study of preferential attachment models was initiated in 1999 by the work of Barabási and Albert [3], who indicated the applications of such graphs in network modeling. The preferential attachment model was subsequently formally defined and analyzed by Bollobás, Riordan, Spencer, and Tusnády [8], and Bollobás and Riordan in [6, 7]. It relies on two mechanisms: growth (the graph is growing over time, gaining a new vertex and a bunch of $h\ge 1$ edges at each time step) and preferential attachment (an arriving vertex is more likely to attach to other vertices with high degree rather than with low degree), for a precise definition check Section 2. Its degree distribution as well as diameter often fit in with the ones spotted in reality [15, 28]. Nevertheless, an experimental study shows that, unlike real networks, it lacks apparent community structure.

Quantifying community structure itself is a subtle task. Among the many measures proposed, modularity, introduced by Newman and Girvan in 2004 [28, 29], has emerged as a central metric. The vertices of a graph with high modularity may be partitioned into subsets in which there are much more internal edges than we would expect by chance (see Definition 1). Nowadays, modularity is widely used not only as a quality function judging the performance of community detection algorithms [19], but also as a central ingredient of such algorithms, like in the Louvain algorithm [5], the Leiden algorithm [36] or the Tel-Aviv algorithm [13]. Early theoretical results on modularity were given for trees [2] and regular graphs [24]. For a summary of results for various families of graphs check the appendix of [26] by McDiarmid and Skerman from $2020$. More recent discoveries include [9] by Chellig, Fountoulakis, and Skerman (for random graphs on the hyperbolic plane), [20] by Lasoń and Sulkowska (for minor-free graphs), [21] by Lichev and Mitsche (for $3$-regular graphs and graphs with a given degree sequence), or [32] by Rybarczyk (for random intersection graphs).

Despite being so widely used in practice, modularity still suffers from a narrow theoretical study in the families of random graphs devoted to modeling real-life networks. The first results for the well-known and most studied random graph, the binomial $G(n,p)$, were given by McDiarmid and Skerman just in 2020 [26]. It is commonly known that $G(n,p)$ is a poor fit to real networks [19]. Preferential attachment models perform here much better. Prokhorenkova, Prałat, and Raigorodskii opened the preliminary study on modularity of a standard preferential attachment graph in [30]. They obtained non-trivial upper and lower bounds, however, the gap to close remained big. They conjectured that the modularity of such a graph with high probability tends to $0$ with $h$ (the number of edges added per step) tending to infinity (see Conjecture 3). In this paper we prove their conjecture, confirming the supposition that a standard preferential attachment model might have too small modularity to mirror well the behavior of real networks.

As a result, we derive new and interesting concentration results for the volume and edge density parameters of a given subset of vertices in the preferential attachment graph. To this end, we introduce a new function $\mu$, which serves as a natural measure for vertex subsets, and is proportional to the average size of their volumes. These findings are noteworthy on their own and could have potential applications to other problems related to the model in the future. They extend previous results from [12] by Frieze, Pérez-Giménez, Prałat, and Reiniger (see lemmas 3 and 4 therein), which were utilized in the context of Hamilton cycles in the preferential attachment model.

In the following section we give the formal definition of the preferential attachment model and state the main result. Section 3 is devoted to presenting the results regarding the volume and the edge density parameters of subsets of vertices in $G_n^h$. Section 4 is technical, it contains several facts and auxiliary lemmas used in the latter parts of the paper. In Section 5 we derive concentration results stated in Section 3. These results are used in Section 6 to prove the main theorem about vanishing modularity in the standard preferential attachment graph. Section 7 contains concluding remarks.

Let $\mathbb{N}$ denote the set of natural numbers, $\mathbb{N}=\{1,2,3,\mathrm{\dots }\}$. For $n\in \mathbb{N}$ let $[n]=\{1,2,\mathrm{\dots },n\}$. For functions $f(n)$ and $g(n)$ we write $f(n)\sim g(n)$ if ${lim}_{n\to \mathrm{\infty }}f(n)/g(n)=1$. We say that an event $ℰ$ occurs with high probability (whp) if the probability $\mathbb{P}[ℰ]$ depends on a certain number $n$ and tends to $1$ as $n$ tends to infinity.

All of the graphs considered in this paper are finite, undirected, and loops and multiple edges are allowed. Thus a graph is a pair $G=(V,E)$, where $V$ is a finite set of vertices and $E$ is a finite multiset of elements from $V^{(1)}\cup V^{(2)}$ with $V^{(k)}$ being a set of all $k$-element subsets of $V$. Let $e(G)=|E|$ and for $S,U\subseteq V$ set $e_G(S)=|\{e\in E\cap (S^{(1)}\cup S^{(2)})|$ and $e_G(S,U)=|\{e\in E:e\cap S\ne \mathrm{\varnothing }\wedge e\cap U\ne \mathrm{\varnothing }\}|$. The degree of a vertex $v\in V$ in $G$, denoted by ${\mathrm{deg}}_G(v)$, is the number of edges to which $v$ belongs but loops are counted twice, i.e., ${\mathrm{deg}}_G(v)=2|\{e\in E:v\in e\wedge e\in V^{(1)}\}|+|\{e\in E:v\in e\wedge e\in V^{(2)}\}|$. We define the volume of $S\subseteq V$ in $G$ by ${\mathrm{vol}}_G(S)={\sum }_{v\in S}{\mathrm{deg}}_G(v)$. By the volume of a graph, $\mathrm{vol}(G)$, we understand ${\mathrm{vol}}_G(V)$. Whenever the context is clear we write $e(S)$ instead of $e_G(S)$, $e(S,U)$ instead of $e_G(S,U)$, $\mathrm{deg}(v)$ instead of ${\mathrm{deg}}_G(v)$ and $\mathrm{vol}(S)$ instead of ${\mathrm{vol}}_G(S)$.

We focus on a particular random graph model, called here simply the preferential attachment graph (consult [3, 6, 15]). Given $h,n\in \mathbb{N}$, we construct a preferential attachment graph $G_n^h$ in two phases. In the first phase we sample a particular random tree $T_{hn}$, whose vertices are called mini-vertices. (We call $T_{hn}$ a tree, however it might be disconnected, and loops, i.e. single-vertex edges, are allowed in $T_{hn}$.) Next, the appropriate mini-vertices of $T_{hn}$ are grouped to form vertices of $G_n^h$. Let us describe this procedure in detail.

Phase 1.

We start the whole process with $T_1$ which is a graph consisting of a single mini-vertex $1$ with a single loop (thus the degree of vertex $1$ is $2$). For $t\ge 1$, the graph $T_{t+1}$ is built upon $T_t$ by adding a mini-vertex $(t+1)$ and joining it by an edge with a mini-vertex $i$ according to the following probability distribution:

Note that we allow a newly arrived vertex to connect to itself. We continue the process until we get the random tree $T_{hn}$.

Phase 2.

A random multigraph $G_n^h$ is obtained from $T_{hn}$ by merging each set of mini-vertices $\{h(i-1)+1,h(i-1)+2,\mathrm{\dots },h(i-1)+h\}$ into a single vertex $i$ for $i\in \{1,2,\mathrm{\dots },n\}$, keeping loops and multiple edges.

Note that if $G_n^h=(V,E)$ then $V=[n]$, $|V|=n$ and $|E|=hn$. Since we will refer very often to the number of edges of $G_n^h$, it will be also denoted by $M$, i.e., $M:=hn$. Given $G_n^h$, by $G_t^h$, where $t\in [n]$, we understand the subgraph of $G_n^h$ induced by the set of vertices $[t]$.

Our main goal is to upper bound the graph parameter called modularity for $G_n^h$. Its formal definition is given just below.

Conventionally, a graph with no edges has the modularity equal to $0$. A single summand of the modularity score is the difference between the fraction of edges within $S$ and the expected fraction of edges within $S$ in a certain random multigraph on $V$ with the expected degree sequence given by $G$ (see, e.g., [18]). It is easy to check that $\mathrm{mod}(G)\in [0,1)$.

Non-trivial lower and upper bounds for the modularity of $G_n^h$ obtained by Prokhorenkova, Prałat and Raigorodskii in [30] are the following.

Applying the results for the edge expansion of $G_n^h$ by Mihail, Papadimitriou and Saberi from [27] to the upper bound one obtains that whp $\mathrm{mod}(G_n^h)\le 1-O(1/h)$. Indeed, the gap between the upper and the lower bound remained big. The authors stated the following two conjectures suggesting that the upper bound could be improved.

In this paper we present a much better upper bound for the modularity of $G_n^h$ than the one from Theorem 2 when $h$ is large, resolving, in the positive, Conjecture 3. Conjecture 4 still remains open. The main result of the paper may be presented as follows.

When talking about $G_n^h=(V,E)$ we will very often refer to its corresponding random tree $T_{hn}=(\tilde{V},\tilde{E})$. Recall that $V=[n]$, $\tilde{V}=[hn]$ and $|\tilde{E}|=|E|=hn=:M$. For $S\subseteq V$ the corresponding set of its mini-vertices in $\tilde{V}$ will be denoted by $\tilde{S}$, thus $|\tilde{S}|=h|S|$. For $i\in [n]$ and $S\subseteq V$ let $S_i=S\cap [i]$, in particular $S_n=S$. Analogously, for $i\in [M]$ and $\tilde{S}\subseteq \tilde{V}$ set ${\tilde{S}}_i=\tilde{S}\cap [i]$, in particular ${\tilde{S}}_M=\tilde{S}$. Note that for $S\subseteq V$ we have ${\mathrm{vol}}_{G_n^h}(S)={\mathrm{vol}}_{T_{hn}}(\tilde{S})$ and $e_{G_n^h}(S)=e_{T_{hn}}(\tilde{S})$.

When working with modularity we need to have a control over $e_{G_n^h}(S)$ and ${\mathrm{vol}}_{G_n^h}(S)$, where $S\subseteq V$. Those values depend a lot on the arrival times of vertices from $S$. To capture this phenomenon we define a special measure $\mu :2^{\tilde{V}}\to [0,\mathrm{\infty })$, where $2^{\tilde{V}}$ stands for the set of all subsets of $\tilde{V}$.

We use the measure $\mu$ to express the following novel concentration results for ${\mathrm{vol}}_{G_n^h}(S)$, $e_{G_n^h}(S)$, and $e_{G_n^h}(S,V\setminus S)$, where $S$ is an arbitrary subset of $V$.

To grasp the intuition hidden behind the above concentration results, it is helpful to know that there is a relation between the structure of the graph $T_{hn}$ and the structure of a random graph $\widehat{G}$ on the vertex set $[M]$ in which every edge $\{i,j\}$ (for $i,j\in [M]$) is present with probability $1/(2\sqrt{ij})$, independently of the other possible edges (in particular, a loop at vertex $i$ is present with probability $1/(2i)$, consult Section 4 in [7] by Bollobás and Riordan). We will see that, for any set $\tilde{S}$, the values $\mu (\tilde{S})$ and $\mu {(\tilde{S})}^2$ are closely related to the expected value of ${\mathrm{vol}}_{\widehat{G}}(\tilde{S})$ and $e_{\widehat{G}}(\tilde{S})$, respectively.

Let $\tilde{S}\subseteq [M]$. The number of inner edges of $\tilde{S}$ in $\widehat{G}$, $e_{\widehat{G}}(\tilde{S})$, satisfies

Analogously one shows that the number of edges between $\tilde{S}$ and $[M]\setminus \tilde{S}$, $e_{\widehat{G}}(\tilde{S},[M]\setminus \tilde{S})$, fulfills

Since ${\mathrm{vol}}_{\widehat{G}}(\tilde{S})=2e_{\widehat{G}}(\tilde{S})+e_{\widehat{G}}(\tilde{S},\tilde{V}\setminus \tilde{S})$ one also gets

We will see later (consult Lemma 14) that the value of $\sqrt{\pi }{c}_j$ is asymptotically close to $1/\sqrt{j}$ thus the measure $\mu$ is constructed in such a way that $\mu (\tilde{S})$ mimics the behavior of ${\sum }_{i\in \tilde{S}}\frac{1}{2\sqrt{i}}$ in $\widehat{G}$. In particular $\mu (\{i\})\sim \frac{1}{2\sqrt{i}}$ for $i\underset{n\to \mathrm{\infty }}{\overset{}{\to }}\mathrm{\infty }$ and $\mu ([M])\sim \sqrt{M}$. Therefore we may expect that in $T_{hn}$ we will get $e(\tilde{S})\approx \mu {(\tilde{S})}^2$, $e(\tilde{S},V\setminus \tilde{S})\approx 2\mu (\tilde{S})(\sqrt{M}-\mu (\tilde{S}))$ and $\mathrm{vol}(\tilde{S})\approx 2\sqrt{M}\mu (\tilde{S})$.

The current section gathers all technical lemmas needed in the latter parts of the paper.

The concentration results presented in Section 3 and proved in Section 5 are based on two variants of the Azuma-Hoeffding martingale inequality. The first one is standard. We state it as it appears in [16] by Janson, Łuczak and Ruciński.

The second one is Freedman’s inequality. We state it below in the form very similar to the one presented in Lemma 2.2 of [37] by Warnke (one may consult also [4] by Bennett and Dudek).

Next, we present bounds for the values of $c_j$ and an upper bound for the function $\mu (\tilde{S})$, both introduced in Definition 7. These results will be referred to very often later on. They are derived using Stirling’s approximation.

In this section we use martingale techniques to prove theorems 8, 9, and 10 stated in Section 3, i.e., we derive concentration results for $\mathrm{vol}(S)$, $e(S)$, and $e(S,V\setminus S)$ for an arbitrary subset $S\subseteq V$ in $G_n^h$. A series of results will lead us to Corollary 22 which implies, as a special case, Theorem 8. We start with analyzing the volumes.