New bounds on the modularity of 𝐆 ( 𝐧 , 𝐩 ) \mathbf{G(n,p)}
Katarzyna Rybarczyk * {}^{\textrm{*}}, Małgorzata Sulkowska ⋆ {}^{\textrm{$\star$}} · 2025
Read New bounds on the modularity of 𝐆 ( 𝐧 , 𝐩 ) \mathbf{G(n,p)} by Katarzyna Rybarczyk * {}^{\textrm{*}}, Małgorzata Sulkowska ⋆ {}^{\textrm{$\star$}} (2025) 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-2504-16254.txt.
Introduction
Katarzyna Rybarczyk and Małgorzata Sulkowska sharpen bounds on how much community structure a random graph can hold. Their 2025 paper studies modularity, the score behind popular clustering tools, for the classic binomial random graph G(n,p). A 2020 result capped the score near a constant over the square root of the average degree, but the constant was huge and hard to compute.
The authors push the constant below three using basic probabilistic tools rather than heavy spectral machinery. They also improve the lower bound, drawing on estimates for graph bisections proved in 2017. Random graphs serve as the null case for community detection, so tighter bounds calibrate what counts as real structure in observed networks.
Catalog record
| CREATOR | Katarzyna Rybarczyk * {}^{\textrm{*}}, Małgorzata Sulkowska ⋆ {}^{\textrm{$\star$}} |
|---|---|
| YEAR | 2025 |
| 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/2504-16254
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
New bounds on the modularity of 𝐆 ( 𝐧 , 𝐩 ) \mathbf{G(n,p)} Thanks: This research was funded in part by National Science Centre, Poland, grant OPUS-25 no 2023/49/B/ST6/02517. Katarzyna Rybarczyk * {}^{\textrm{*}}, Małgorzata Sulkowska ⋆ {}^{\textrm{$\star$}} Abstract . Modularity is a parameter indicating the presence of community structure in the graph. Nowadays it lies at the core of widely used clustering algorithms. We study the modularity of the most classical random graph, binomial G ( n , p ) G(n,p) . In 2020 McDiarmid and Skerman proved, taking advantage of the spectral graph theory and a specific subgraph construction by Coja-Oghlan from 2007, that there exists a constant b b such that with high probability the modularity of G ( n , p ) G(n,p) is at most b / n p b/\sqrt{np} . The obtained constant b b is very big and not easily computable. We improve upon this result showing that a constant under 3 3 may be derived here. Interesting is the fact that it might be obtained by basic probabilistic tools. We also address the lower bound on the modularity of G ( n , p ) G(n,p) and improve the results of McDiarmid and Skerman from 2020 using estimates of bisections of random graphs derived by Dembo, Montanari, and Sen in 2017. 1. Introduction Identifying communities in a graph 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 [ 13 , 22 ] . Therefore various algorithmic approaches to graph clustering arose over the years. Just to mention a few: some are based on random walks, others on hierarchical clustering, label propagation, or spectral bisection method [ 13 ] . Recently widely used algorithms that offer a good trade-off between the time complexity and the quality of identified communities are Louvain algorithm [ 2 ] and its follow-ups - Leiden algorithm [ 28 ] , and Tel-Aviv algorithm [ 10 ] . They are similar in nature, i.e., they heuristically try to optimize a parameter called modularity . Modularity (introduced by Newman and Girvan in 2004 [ 23 ] ) serves as a measure of the presence of community structure in the graph. As mentioned, it is commonly utilized in practice, however many theoretical questions about it, even for very classical families of graphs, still remain unanswered. We study the modularity function of the most classical random graph, binomial G(n,p) . First such results were given by McDiarmid and Skerman just in 2020 [ 20 ] . One can check the appendix therein for a summary of results on modularity for various graph classes ( [ 3 , 4 , 17 , 19 , 21 , 24 ] ) and further references. More recent discoveries one finds in [ 5 ] by Chellig, Fountoulakis and Skerman (for random graphs on the hyperbolic plane), [ 14 ] by Lasoń and Sulkowska (for minor-free graphs), [ 15 ] by Lichev and Mitsche (for 3 -regular graphs and graphs with a given degree sequence), [ 27 ] by Rybarczyk and Sulkowska and [ 18 ] by McDiarmid, Rybarczyk, Skerman, and Sulkowska (for preferential attachment graphs), and [ 26 ] by Rybarczyk for random intersection graphs. The authors of [ 20 ] showed that the modularity of G(n,p) with high probability decreases at the rate 1/\sqrt{np} by n tending to infinity (note that np may be asymptotically interpreted as an average degree). In this paper we study the upper and the lower bound on the modularity of G(n,p) . We show how, using basic probabilistic methods, significantly improve the upper bound presented in [ 20 ] . We also improve upon the lower bound from [ 20 ] using the estimates of bisections of random graphs from [ 9 ] . Notation, previous results, and our findings are presented in Section 2 . In Section 3 we derive a new upper bound on the modularity of G(n,p) . Doing that, we use a technical lemma bounding the number of edges of induced subgraphs of G(n,p) - its proof may be found in Section 4 . The last section is devoted to the lower bound on G(n,p) . 2. Notation and statement of results 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\} . If a random variable X follows a binomial distribution with parameters n\in\mathbb{N} and p\in[0,1] we write X\sim\textrm{Bin}\left(n,p\right) . For the functions f,g:\mathbb{N}\rightarrow\mathbb{R} we use the notation f(n)=o(g(n)) and f(n)\ll g(n) interchangeably and understand it as \lim_{n\rightarrow\infty}f(n)/g(n)=0 . Unless otherwise stated, o(\cdot) relates to n\to\infty . By f(n)\sim g(n) we mean \lim_{n\rightarrow\infty}f(n)/g(n)=1 . We say that an event \mathscr{E}=\mathscr{E}_{n} occurs with high probability (whp) if the probabilities \mathbb{P}\left(\mathscr{E}_{n}\right) tend to 1 as n tends to infinity. All inequalities in the paper are true for n large enough and, for clarity of notation, we omit floors and ceilings when it does not influence a reasoning. The graphs considered are finite, simple and undirected. Thus a graph is a pair G=(V(G),E(G)) , where V(G) is a finite set of vertices and E(G)\subseteq V(G)^{(2)} where, for any set S , S^{(2)} stands for a set of all 2 -element subsets of S . Let e(G)=|E(G)| and for S\subseteq V(G) set \bar{S}=V(G)\setminus S , e(S)=|\{e\in E(G)\cap S^{(2)}\}| , and e(S,\bar{S})=|\{e\in E(G):e\cap S\neq\emptyset\wedge e\cap\bar{S}\neq\emptyset\}| . The degree of a vertex v\in V(G) in G , denoted by \deg(v) , is the number of edges to which v belongs, i.e., \deg(v)=|\{e\in E(G):v\in e\}| . We define the volume of S\subseteq V in G by \vol(S)=\sum_{v\in S}\deg(v) . By the volume of the graph, \vol(G) , we understand \vol(V(G)) . We also introduce several basic definitions originating from spectral graph theory. We do not make use of its tools in our proofs, however we refer to the results that do that. For a graph G on the vertex set [n] by A=\{a_{i,j}\}_{i,j\in[n]} denote its adjacency matrix (i.e. a_{i,j}=1 if \{i,j\}\in E(G) and a_{i,j}=0 otherwise) and by D=\{d_{i,j}\}_{i,j\in[n]} its diagonal degree matrix (i.e. d_{i,i}=\deg(i) and d_{i,j}=0 for i\neq j ). A matrix {\mathscr{L}}=I-D^{-1/2}AD^{-1/2} is called a normalized Laplacian of G (here D^{-1/2} stands for a diagonal matrix with diagonal entries \deg(i)^{-1/2} if \deg(i)\neq 0 and 0 otherwise). By 0=\lambda_{0}\leq\lambda_{1}\leq\ldots\leq\lambda_{n-1}\leq 2 denote the eigenvalues of \mathscr{L} (see [ 6 ] ). Then \bar{\lambda}(G)=\max_{i\neq 0}|1-\lambda_{i}|=\max\{|1-\lambda_{1}|,|1-\lambda_{n-1}|\} is called the spectral gap of G . We work with the classical binomial random graph and state its definition as it appears in [ 11 ] by Janson, Łuczak, and Ruciński. Definition 1 (Binomial random graph G(n,p) ) . Let n\in\mathbb{N} and p\in[0,1] . The binomial random graph is defined by taking the set of all graphs on vertex set [n] as a sample space \Omega , defining \mathscr{F}=2^{\Omega} as an event space, and for G\in\Omega setting \mathbb{P}\left(G\right)=p^{e(G)}(1-p)^{{n\choose 2}-e(G)}. Obviously, G(n,p) may be seen as a result of {n\choose 2} independent Bernoulli trials, one for each pair of vertices from [n] , with the probability of success (which