Note on edge expansion and modularity in preferential attachment graphs

Colin McDiarmid, Katarzyna Rybarczyk, Fiona Skerman, Małgorzata Sulkowska

arXivarxiv/2601.05953Jan 9, 2026math.PRscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2601.05953
curl -X POST /api/v1/records/arxiv/2601.05953/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.05953/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'