Modularity of Preferential Attachment Graphs

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, Prałat, 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 μ, 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, Pérez-Giménez, Prałat, and Reiniger from 2019.