





















We relate two important notions in graph theory: expanders which are highly connected graphs, and modularity a parameter of a graph that is primarily used in community detection. More precisely, we show that a graph having modularity bounded below 1 is equivalent to it having a large subgraph which is an expander. We further show that a connected component $H$ will be split in an optimal partition of the host graph $G$ if and only if the relative size of $H$ in $G$ is greater than an expansion constant of $H$. This is a further exploration of the resolution limit known for modularity, and indeed recovers the bound that a connected component $H$ in the host graph~$G$ will not be split if~$e(H)<\sqrt{2e(G)}$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。