.png){kind=icon}
.png){kind=icon}
Return
Modularity of Preferential Attachment Graphs
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.76.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study a preferential attachment model G(n)(h). The graph G(n)(h) is generated from a finite initial graph by adding new vertices one at a time. Each new vertex connects to h >= 1 already existing vertices, and these are chosen with probability proportional to their current degrees. We are particularly interested in the community structure of G(n)(h), which is expressed in terms of the so-called modularity. We prove that the modularity of G(n)(h) is, with high probability, upper bounded by a function that tends to 0 as h tends to infinity. This resolves a conjecture of Prokhorenkova, Pralat, and Raigorodskii from 2016. As a byproduct, we obtain novel concentration results (which are interesting in their own right) for the volume and edge density parameters of vertex subsets of G(n)(h). The key ingredient here is the definition of a function mu, which serves as a natural measure for vertex subsets, and is proportional to the average size of their volumes. This extends previous results on the topic by Frieze, Perez-Gimenez, Pralat, and Reiniger from 2019.
Keywords:
Modularity
preferential attachment model
edge expansion
Journal
4
IF:
0
Papers:
81
Citations:
0