2026-08-07T20:31:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19606 2024-03-06T11:04:27Z ddc:004 open_access

Modularity and Graph Expansion Louf, Baptiste McDiarmid, Colin Skerman, Fiona edge expansion modularity community detection resolution limit conductance 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)}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Baptiste Louf and Colin McDiarmid and Fiona Skerman 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.78 urn:nbn:de:0030-drops-196063 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.78 eng https://creativecommons.org/licenses/by/4.0/legalcode