Modularity of preferential attachment graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914243354296320 |
|---|---|
| author | Rybarczyk, Katarzyna Sulkowska, Małgorzata |
| author_facet | Rybarczyk, Katarzyna Sulkowska, Małgorzata |
| contents | 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 $μ$, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06771 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Modularity of preferential attachment graphs Rybarczyk, Katarzyna Sulkowska, Małgorzata Probability 05C80, 60G42, 60C05 G.2.1; G.2.2; G.3 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 $μ$, 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. |
| title | Modularity of preferential attachment graphs |
| topic | Probability 05C80, 60G42, 60C05 G.2.1; G.2.2; G.3 |
| url | https://arxiv.org/abs/2501.06771 |