






















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$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。