Note on edge expansion and modularity in preferential attachment graphs
Colin McDiarmid, Katarzyna Rybarczyk, Fiona Skerman, Małgorzata Sulkowska · 2026
Read Note on edge expansion and modularity in preferential attachment graphs by Colin McDiarmid, Katarzyna Rybarczyk, Fiona Skerman, Małgorzata Sulkowska (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-05953.txt.
Introduction
Colin McDiarmid and 3 co-authors study in 2026 two network quality measures, edge expansion and modularity, inside random preferential attachment graphs. Preferential attachment grows a network by linking new nodes preferentially to already popular ones, mimicking real social and information networks. Expansion measures connectedness, while modularity measures how cleanly a graph splits into communities.
The authors establish new bounds for the likely edge expansion in two standard preferential attachment models where each step adds at least two edges. Bounds for expansion of small vertex subsets then yield new upper bounds on modularity for small numbers of added edges. Both parameters matter for robust network design, random walk analysis, and clustering applications.
Catalog record
| CREATOR | Colin McDiarmid, Katarzyna Rybarczyk, Fiona Skerman, Małgorzata Sulkowska |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-05953
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Note on edge expansion and modularity in preferential attachment graphs Colin McDiarmid, Katarzyna Rybarczyk, Fiona Skerman, Małgorzata Sulkowska Abstract Edge expansion is a parameter indicating how well-connected a graph is. It is useful for designing robust networks, analysing random walks or information flow through a network and is an important notion in theoretical computer science. Modularity is a measure of how well a graph can be partitioned into communities and is widely used in clustering applications. We study these two parameters in two commonly considered models of random preferential attachment graphs, with h ≥ 2 h\geq 2 edges added per step. We establish new bounds for the likely edge expansion for both random models. Using bounds for edge expansion of small subsets of vertices, we derive new upper bounds also for the modularity values for small h h . 1 Introduction and statement of results 1.1 Introduction "Preferential attachment", often referred to as the "rich get richer" effect, describes a pattern in the growth of dynamic graph models where new nodes tend to form links with nodes that already have numerous connections. The earliest random graphs incorporating the idea of preferential attachment were random recursive trees [ 17 , 29 ] . However, it was not until the results of Barabási and Albert [ 7 ] that the connection between the phenomenon of "preferential attachment" and certain natural properties of networks was demonstrated, initiating more in-depth research into various models based on this property. In this paper, we focus on two fundamental models of such graphs, G_{n}^{h} and \tilde{G}_{n}^{h} . They are generated from a finite initial graph by adding new vertices one at a time. Each new vertex connects to h\geq 2 already existing vertices, and these are chosen with probability proportional to their current degrees (for the exact definitions consult Section 1.3 ). For generalised preferential attachment models – see [ 1 , 12 ] . We investigate two parameters that describe certain important characteristics of networks: edge expansion and modularity. Edge expansion (also known as isoperimetric number, Cheeger constant or, simply, expansion), denoted by \alpha(G) , is a parameter indicating how well-connected a graph G is. It lower bounds the ratio of the number of edges leaving a set S of vertices to the size of S (see Definition 1.1 ). Edge expansion is particularly important in the study of network robustness or efficiency of communication in complex systems and also in the theory of error correcting codes [ 13 ] . The second graph parameter we consider is modularity, denoted by q^{*}(G) . It was introduced in 2004 by Newman and Girvan [ 23 ] as a measure of how well a graph can be partitioned into communities. Roughly speaking, a vertex-partition with high modularity score has many more internal edges than we would expect if the edges were re-wired randomly, matching the original degree sequence of the graph (see Definition 1.2 ). The modularity score of a partition is used in clustering algorithms popular in applications [ 8 , 14 , 24 , 30 ] . Early theoretical research on modularity was conducted for trees [ 6 ] and random regular graphs and lattices [ 18 ] . Results for the basic and most studied random graph, binomial G(n,p) , were given in [ 19 ] and recently partially extended in [ 27 ] . See the final section of [ 21 ] for a summary of known modularity values, and for further recent work consult [ 15 , 16 , 4 , 28 ] . First, we revisit the result of Mihail, Papadimitriou and Saberi [ 2 ] who proved that for large h the expansion of \tilde{G}_{n}^{h} is greater than 1/5 with high probability (whp) – that is, with probability tending to one as n\to\infty . We show that, with slight modifications of their proof, one may obtain a whp lower bound on expansion (and also expansion of small sets), in both G_{n}^{h} and \tilde{G}_{n}^{h} , which is linear in h , see Theorem 1.2 and Corollary 1.1 . (Note that similar linear dependence on h for \tilde{G}_{n}^{h} was claimed, but not proved, in the conference version of the paper by Mihail et al. [ 22 ] . The journal version of the Mihail et. al. paper, i.e. [ 2 ] contains the full proof but the dependence is not linear in h , see Theorem 1.1 below.) In a related direction, Hazra, van der Hofstad and Ray [ 1 ] studied expansion of large sets for very general classes of preferential attachment graphs (including both G_{n}^{h} and \tilde{G}_{n}^{h} ) though they also did not obtain linear dependence in h . By considering our new expansion result for small sets, we improve the whp upper bound for q^{*}(\tilde{G}_{n}^{h}) obtained by Prokhorenkova, Prałat and Raigorodskii [ 5 ] , and show that our bound extends to G_{n}^{h} also (see Corollary 1.2 ). The previous best upper bound for fixed h (from [ 5 ] ) is q^{*}(\tilde{G}_{n}^{h})\leq 1-1/10h (see Section 1.5 and Remark 1.1 for details). Our methods give the whp upper bound on q^{*}(\tilde{G}_{n}^{h}) and q^{*}(G_{n}^{h}) of 0.92383 , which is independent of h and thus whp bounds the modularity values away from 1 for all h\geq 2 . As a byproduct of our proofs we also obtain a general upper bound on modularity value in terms of expansion of small sets, see Theorem 1.3 . The second and fourth author proved recently in [ 26 ] that q^{*}(G_{n}^{h}) may be whp upper bounded by a function of h which tends to 0 as h\rightarrow\infty – see Theorem 1.4 . However, for 2\leq h\leq 959 the upper bound obtained in this paper is tighter. We recall that for practical applications the average degree is often relatively small, so the results in this paper fill an important gap. 1.2 Basic definitions All the graphs considered in this paper are finite, and loops and multiple edges are allowed (thus they are multigraphs). For any set S , S^{(k)} stands for the set of all k -element subsets of S . 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)} . For S\subseteq V let \bar{S}=V\setminus S . For S,U\subseteq V set E_{G}(S)=\{e\in E\cap(S^{(1)}\cup S^{(2)})\} (the set of inner edges of S ) and E_{G}(S,U)=\{e\in E:e\cap S\neq\emptyset\wedge e\cap U\neq\emptyset\} (the set of edges between S and U ). Denote also e(G)=|E| , e_{G}(S)=|E_{G}(S)| and e_{G}(S,U)=|E_{G}(S,U)| . 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)}\}| . In some special cases a loop may contribute only 1 to the degree of a vertex but this will be always clearly indicated. Next, we define the volume of S\subseteq V in G by {\rm vol}_{G}(S)=\sum_{v\in S}\deg_{G}(v) , and write {\rm vol}(G) for {\rm vol}_{G}(V) . Whenever the context is clear we omit the subscript G and write, e.g., e(S) instead of e_{G}(S) . We focus on two important graph parameters: edge expansion (also