DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.76

Modularity of Preferential Attachment Graphs

Authors: Katarzyna Rybarczyk and Małgorzata Sulkowska

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

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.

Cite as

Katarzyna Rybarczyk and Małgorzata Sulkowska. Modularity of Preferential Attachment Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 76:1-76:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rybarczyk_et_al:LIPIcs.STACS.2026.76,
  author =	{Rybarczyk, Katarzyna and Sulkowska, Ma{\l}gorzata},
  title =	{{Modularity of Preferential Attachment Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{76:1--76:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.76},
  URN =		{urn:nbn:de:0030-drops-255658},
  doi =		{10.4230/LIPIcs.STACS.2026.76},
  annote =	{Keywords: Modularity, preferential attachment model, edge expansion}
}

Search Results

Documents authored by Rybarczyk, Katarzyna

Modularity of Preferential Attachment Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message