2023/12/12 by Baptiste Louf, Colin McDiarmid, Louf, Baptiste +3 · 1 citation
Physics and Astronomy · Computer Science · Mathematics · #Complex Network Analysis Techniques #Advanced Graph Theory Research #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2312.07521
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)<√(2e(G)).