Modularity of preferential attachment graphs

Abstract

We study the preferential attachment model $G_n^h$. A 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\ge 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 the 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 the function $\hat{I}¼$, 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, Pralat, Pérez-Giménez, and Reiniger from 2019.

24 pages