2026-10-01T07:51:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25565 2026-09-23T23:44:09Z ddc:004 open_access

Modularity of Preferential Attachment Graphs Rybarczyk, Katarzyna Sulkowska, Małgorzata Modularity preferential attachment model edge expansion 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Katarzyna Rybarczyk and Małgorzata Sulkowska 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.76 urn:nbn:de:0030-drops-255658 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.76 eng https://creativecommons.org/licenses/by/4.0/legalcode