Modularity of Complex Networks Models

Classical Models. Let us recall two classical models of random graphs that are extensively studied in the literature. The binomial random graph\({\mathcal {G}}(n,p)\) is the random graph G with the vertex set \([n] := \{ 1, 2, \ldots , n\}\) in which every pair \(\{i,j\} \in \left( {\begin{array}{c}[n]\\ 2\end{array}}\right) \) appears independently as an edge in G with probability p. Note that \(p=p(n)\) may (and usually does) tend to zero as n tends to infinity.

However, in this paper we concentrate on another probability space, the probability space of random d-regular graphs with uniform probability distribution. This space is denoted \(\mathcal {G}_{n,d}\), and asymptotics are for \(n\rightarrow \infty \) with \(d\ge 2\) fixed, and n even if d is odd.

We say that an event in a probability space holds asymptotically almost surely (or a.a.s.) if the probability that it holds tends to 1 as n goes to infinity. Since we aim for results that hold a.a.s., we will always assume that n is large enough.

Preferential Attachment. The Preferential Attachment (PA) model, introduced by Barabási and Albert [5], was an early stochastic model of complex networks. We will use the following precise definition of the model, as considered by Bollobás and Riordan in [10] as well as Bollobás et al. [11].

For \(m \in \mathbb N \setminus \{1\}\), the process \((G_m^t)_{t \ge 0}\) is defined similarly with the only difference that m edges are added to \(G_m^{t-1}\) to form \(G_m^t\) (one at a time), counting previous edges as already contributing to the degree distribution. Equivalently, one can define the process \((G_m^t)_{t \ge 0}\) by considering the process \((G_1^t)_{t \ge 0}\) on a sequence \(v'_1, v'_2, \ldots \) of vertices; the graph \(G_m^t\) is formed from \(G_1^{tm}\) by identifying vertices \(v'_1, v'_2, \ldots , v'_m\) to form \(v_1\), identifying vertices \(v'_{m+1}, v'_{m+2}, \ldots , v'_{2m}\) to form \(v_2\), and so on. Note that in this model \(G_m^t\) is in general a multigraph, possibly with multiple edges between two vertices (if \(m\ge 2\)) and self-loops.

It was shown in [11] that for any \(m \in \mathbb N \) a.a.s. the degree distribution of \(G_m^n\) follows a power law: the number of vertices with degree at least k falls off as \((1+o(1)) ck^{-2} n\) for some explicit constant \(c=c(m)\) and large \(k \le n^{1/15}\). Also, in the case \(m=1\), \(G_1^n\) is a forest. Each vertex sends an edge either to itself or to an earlier vertex, so the graph consists of components which are trees, each with a loop attached. The expected number of components is then \(\sum _{t=1}^n 1/(2t-1) \sim (1/2) \log n\) and, since events are independent, we derive that a.a.s. there are \((1/2+o(1)) \log n\) components in \(G_1^n\) by Chernoff’s bound. Moreover, Pittel [32] essentially showed that a.a.s. the largest distance between two vertices in the same component of \(G_1^n\) is \((\gamma ^{-1} + o(1)) \log n\), where \(\gamma \) is the solution of \(\gamma e^{1+\gamma } = 1\). In contrast, for the case \(m \ge 2\) it is known that a.a.s. \(G_m^n\) is connected and its diameter is \((1+o(1)) \log n / \log \log n\) [10].

Spatial Preferential Attachment. The Spatial Preferential Attachment (SPA) model [1], designed as a model for the World Wide Web, combines geometry and preferential attachment, as its name suggests. Setting the SPA model apart is the incorporation of ‘spheres of influence’ to accomplish preferential attachment: the greater the degree of a vertex, the larger its sphere of influence, and hence the higher the likelihood of the vertex gaining more neighbors.

The process begins at \(t=0\), with \(G_0\) being the null graph. Time-step t, \(t\ge 1\), is defined to be the transition between \(G_{t-1}\) and \(G_t\). At the beginning of each time-step t, a new vertex \(v_t\) is chosen uniformly at random from S, and added to \(V_{t-1}\) to create \(V_{t}\). Next, independently, for each vertex \(u\in V_{t-1}\) such that \(v_t \in S(u,t-1)\), a directed link \((v_{t},u)\) is created with probability p. Thus, the probability that a link \((v_t,u)\) is added in time-step t equals \(p\,|S(u,t-1)|\).

The SPA model produces scale-free networks, which exhibit many of the characteristics of real-life networks (see [1, 13]). In [19], it was shown that the SPA model gave the best fit, in terms of graph structure, for a series of social networks derived from Facebook. In [20], some properties of common neighbors were used to explore the underlying geometry of the SPA model and quantify vertex similarity based on distance in the space. However, the distribution of vertices in space was assumed to be uniform [20] and so in [21] non-uniform distributions were investigated which is clearly a more realistic setting.

In this section we discuss known bounds for modularity in different random graph models.

Investigating random d-regular graphs continues in [24], a very recent paper. In fact, some of our results for this model mentioned below are obtained independently there. Moreover, they investigate the class of graphs whose product of treewidth and maximum degree is much less than the number of edges. This shows, for example, that random planar graphs typically have modularity close to 1, which is another indication that clusters naturally emerge where geometry is included.

Theorem 1 provides an upper bound that can be easily numerically computed for a given \(d \in \mathbb N \setminus \{1,2\}\). Next, we present a slightly weaker but an explicit bound that can be obtained using the expansion properties of random d-regular graphs that follow from their eigenvalues. In particular, it will imply that a.a.s. \(q^*({\mathcal {G}}_{n,d}) = O(1/\sqrt{d})\) and so \(q^*({\mathcal {G}}_{n,d}) \rightarrow 0\) as \(d \rightarrow \infty \).

In order to obtain a lower bound for modularity of Preferential Attachment graphs, we first analyze graphs with constant average degree in general. In this section, we extend the results of [26] and we start with the analysis of trees. It was proven in [26] that trees with maximum degree \(\varDelta = o(\root 5 \of {n})\) have asymptotic modularity 1. We generalize this result in two ways: first, we relax the condition on maximum degree; second, we allow our graphs to be disconnected, that is, we consider forests instead of trees. We prove the following theorem.

Note that it is also known that the asymptotic modularity of trees with maximum degree \(\varDelta = \Omega (n)\) is strictly less than 1 [26]. Hence, the assumption \(\varDelta = o(n)\) cannot be eliminated. Now we can use the previous theorem to get the following result for graphs of bounded average degree.

The following theorem easily follows from the above result.

As in the case of random d-regular graphs, it is natural to conjecture that the above lower bound is not sharp. Let \(c \in (0,1)\) and consider the following partition: \(A_1 = \{v_1, \ldots , v_{cn} \}\), \(A_2 = V(G_m^n) \setminus A_1 = \{ v_{cn+1}, \ldots , v_n\}\). Using martingales, it is possible to show that a.a.s. \(\sum _{v \in A_1} \deg (v, n) \sim 2mn\sqrt{c}\) (and so \(\sum _{v \in A_2} \deg (v, n) \sim 2mn(1-\sqrt{c})\)). Clearly, \(e(A_1) = mcn\) and so a.a.s. \(e(A_1,A_2) \sim 2mn(\sqrt{c}-c)\) and \(e(A_2) \sim mn(1+c-2\sqrt{c})\). The edge contribution and the degree tax are then both asymptotic to \(1+2c-2\sqrt{c}\). Not surprisingly, such partition cannot be used to get a non-trivial lower bound for the modularity but, similarly to the situation for random d-regular graphs, we may try to use it as a starting point to get slightly better partition. The basic idea is very simple: one can start with a given partition (or partition the vertices randomly into two classes), and if a vertex has more neighbors in the other class than in its own, then we randomly decide whether to shift it to the other class or leave it where it is. This approach proved to be useful to get a bound for the bisection width in random d-regular graphs [3] which, in turn, yields a lower bound for the modularity [24]. We plan to investigate it further in the journal version of this paper.

Much stronger expansion property was recently obtained in [15]. We are currently working on using this property to obtain general upper bound for \(q^*(G_m^n)\) that holds for any integer m as well as specific stronger bounds for small values of m. Details will be provided in the journal version of this paper.