Note on edge expansion and modularity in preferential attachment graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912812223168512 |
|---|---|
| author | McDiarmid, Colin Rybarczyk, Katarzyna Skerman, Fiona Sulkowska, Małgorzata |
| author_facet | McDiarmid, Colin Rybarczyk, Katarzyna Skerman, Fiona Sulkowska, Małgorzata |
| contents | Edge expansion is a parameter indicating how well-connected a graph is. It is useful for designing robust networks, analysing random walks or information flow through a network and is an important notion in theoretical computer science. Modularity is a measure of how well a graph can be partitioned into communities and is widely used in clustering applications. We study these two parameters in two commonly considered models of random preferential attachment graphs, with $h \geq 2$ edges added per step. We establish new bounds for the likely edge expansion for both random models. Using bounds for edge expansion of small subsets of vertices, we derive new upper bounds also for the modularity values for small $h$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_05953 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Note on edge expansion and modularity in preferential attachment graphs McDiarmid, Colin Rybarczyk, Katarzyna Skerman, Fiona Sulkowska, Małgorzata Probability Social and Information Networks Combinatorics 05C80, 60C05 G.2.1; G.2.2; G.3 Edge expansion is a parameter indicating how well-connected a graph is. It is useful for designing robust networks, analysing random walks or information flow through a network and is an important notion in theoretical computer science. Modularity is a measure of how well a graph can be partitioned into communities and is widely used in clustering applications. We study these two parameters in two commonly considered models of random preferential attachment graphs, with $h \geq 2$ edges added per step. We establish new bounds for the likely edge expansion for both random models. Using bounds for edge expansion of small subsets of vertices, we derive new upper bounds also for the modularity values for small $h$. |
| title | Note on edge expansion and modularity in preferential attachment graphs |
| topic | Probability Social and Information Networks Combinatorics 05C80, 60C05 G.2.1; G.2.2; G.3 |
| url | https://arxiv.org/abs/2601.05953 |