Sarah Frenkel, Johannes Carmesin (2025), arXiv preprint — ARXIV-2504.14501
Key takeaways
- Decomposing a graph at local 1-separators (local cut-vertices) finds the densest communities, denser than modularity-based methods produce, on large sparse real networks and especially road networks. Local 2-separators then expose hierarchical sub-structure, at the risk of over-fragmenting small clusters.
Seeded from the abstract and a skim, before the reading in NOTE-085. What follows is what the work says about itself.
Standard community detection, such as modularity optimization, looks for densely connected groups and can miss natural local bottlenecks. The authors study local-separator methods, which split a network at small vertex sets that separate their local neighbourhood. They compare these methods systematically with established algorithms on large real networks. Local 1-separators consistently find the densest communities. Local 2-separators reveal hierarchy but may break up small clusters. Results are strongest on road networks, and the authors present local separators as a scalable, interpretable alternative.
Standing in the record
Filed from the survey of 2026-09-25 of work the anthology set aside as out of scope (tier C): 300 seconds of active reading over 3 sessions in the papers-feed tracker. It was filed Deferred, unread. NOTE-085 is the close reading of 2026-09-25, and it placed the work: Rejected — not worth a reader’s time. Its critique of modularity (§2.4) contains two false statements. Its own “community detection problem” (§2.5) is defined but never scored. Read at the paper’s own thresholds, the figures do not support “consistently identify the densest communities”. The method itself is never defined here, so a reader wanting local separators should go to Carmesin & Frenkel, arXiv:2312.12354 (its ref. [9]).
When seeded, before the reading in NOTE-085, the entry gave a priority for a deeper reading: low — A short empirical comparison that the skim captures. Moderate owner time (t=300 s over 3 sessions). Worth filing only if the Ricci-flow community-detection note wants a comparison partner.
What the seeding asked a deeper reading to check (NOTE-085 is that reading):
- The paper is useful mainly for its argument against using modularity as the sole evaluation criterion, which applies to any community-detection comparison.
- Its own density criterion (§2.5) needs scrutiny, since the authors define it themselves and it may favour their method despite the stated intent. A deeper reading should also check the scalability claims (runtime is not obviously reported) and whether the theory of local separators (the authors’ refs [7, 9]) should be the cited source instead.
Access when seeded: I read the arXiv abstract page (v1 20 Apr 2025, cs.SI and cs.DM) and the full PDF (15 pp.): §1, §2.1–2.5 (methodology and critique of modularity), the empirical sections by heading and figure (Netscience, Euroroads, NRW road network), and §6 (Concluding Remarks). arXiv lists no journal reference. Note that the text never mentions Ricci flow, so the survey’s “companion of held Ricci-flow community detection” is the survey’s own link, not the paper’s.