Modularity of preferential attachment graphs

Identifying communities in a complex network is a task of a great importance. It has a number of practical applications, varying from identifying the groups of common interests in social networks, through classifying fake news or spam, searching articles on related topic, identifying proteins with the same biological functions, optimizing large technological infrastructures, up to networks visualization [19, 27].

The notion of a graph featuring a community structure may be understood in a variety of ways. Therefore, some measures of the presence of community structure in the network had to be introduced. One of them is modularity proposed by Newman and Girvan in 2004 [27, 28]. 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 Louvain algorithm [5], Leiden algorithm [33] or 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) or [21] by Lichev and Mitsche (for $3$-regular graphs and graphs with given degree sequence).

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 basic and most studied random graph, binomial $G(n,p)$, were given by McDiarmid and Skerman just in 2020 [26]. It is commonly known that $G(n,p)$ does not reflect well most of real-world networks [19]. So-called preferential attachment models usually perform here much better. The first in this family were random recursive trees, see for example [22, 32]. 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 Bolloá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\geq 1$ edges at each time step) and preferential attachment (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, 27]. Nevertheless, experimental study shows that its modularity, unlike in real networks, is low. Prokhorenkova, Prałat and Raigorodskii opened the preliminary study on modularity of a basic preferential attachment graph in [29, 30]. They obtained non-trivial upper and lower bounds, however, the gap to close remained big. They conjectured that modularity of such 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 basic preferential attachment model might have too small modularity to mirror well the behavior of real networks. As a byproduct we obtain new interesting concentration results for the volume and the edge density parameters of a given subset of vertices in such graph. These results are interesting in their own right and may have future applications to other problems involving 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 a basic preferential attachment graph. Section 7 contains concluding remarks.

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

All 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\neq\emptyset\wedge e\cap U\neq\emptyset\}|$. The degree of a vertex $v\in V$ in $G$, denoted by $\deg_{G}(v)$, is the number of edges to which $v$ belongs but loops are counted twice, i.e., $\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 $\operatorname{vol}_{G}(S)=\sum_{v\in S}\deg_{G}(v)$. By the volume of the graph, $\operatorname{vol}(G)$, we understand $\operatorname{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)$, $\deg(v)$ instead of $\deg_{G}(v)$ and $\operatorname{vol}(S)$ instead of $\operatorname{vol}_{G}(S)$.

We focus on a particular random graph model, called here simply a 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}$, its vertices are called mini-vertices. (We call $T_{hn}$ a tree, however 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 details.
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 degree of vertex $1$ is $2$). For $t\geq 1$ 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,\ldots,h(i-1)+h\}$ to a single vertex $i$ for $i\in\{1,2,\ldots,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 a 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 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$ if we considered a certain random multigraph on $V$ with the expected degree sequence given by $G$ (see, e.g., [18]). It is easy to check that $\operatorname{mod}(G)\in[0,1)$.

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

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

In this paper we present much better upper bound for 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 $\operatorname{vol}_{G_{n}^{h}}(S)=\operatorname{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 $\operatorname{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}}\rightarrow[0,\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 $\operatorname{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 $\hat{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 (consult Section 4 in [7] by Bollobás and Riordan).

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

while the number of edges between $\tilde{S}$ and $[M]\setminus\tilde{S}$, $e_{\hat{G}}(\tilde{S},[M]\setminus\tilde{S})$, fulfills

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

Therefore 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 $\hat{G}$. We will see later (consult Lemma 14) that the value of $\sqrt{\pi}c_{j}$ is asymptotically close to $1/\sqrt{j}$. Thus in particular $\mu(\{i\})\sim\frac{1}{2\sqrt{i}}$ for $i\xrightarrow{n\rightarrow\infty}\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 $\operatorname{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 Azuma-Hoeffding martingale inequality. The first one is basic. 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 22 of [34] 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 with the use of Stirling’s approximation.

Lemmas 17, 18 and 19 are auxiliary calculations for expressions involving the volumes of the subsets of $\tilde{V}$ (however the reader might not notice the connection with volumes at this point). They will be directly used in Section 5 in the proof of Theorem 9 stating the result on the concentration of $e_{G_{n}^{h}}(S)$ for $S\subseteq V$. Their proofs utilize the following well known 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 $\operatorname{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.