Theoretical Bounds on the Network Community Profile from Low-rank Semi-definite Programming
Yufan Huang, C. Seshadhri, David F. Gleich
Abstract
We study a new connection between a technical measure called -conductance that arises in the study of Markov chains for sampling convex bodies and the network community profile that characterizes size-resolved properties of clusters and communities in social and information networks. The idea of -conductance is similar to the traditional graph conductance, but disregards sets with small volume. We derive a sequence of optimization problems including a low-rank semi-definite program from which we can derive a lower bound on the optimal -conductance value. These ideas give the first theoretically sound bound on the behavior of the network community profile for a wide range of cluster sizes. The algorithm scales up to graphs with hundreds of thousands of nodes and we demonstrate how our framework validates the predicted structures of real-world graphs.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Related papers
- Practical Almost-Linear-Time Approximation Algorithms for Hybrid and Overlapping Graph ClusteringLorenzo Orecchia, Konstantinos Ameranis, Charalampos E. Tsourakakis, Kunal TalwarICML 2022 · 12 citations
- Hypergraph Clustering Based on PageRankYuuki Takai, Atsushi Miyauchi, Masahiro Ikeda, Yuichi YoshidaKDD 2020 · 38 citations
- Local Algorithms for Finding Densely Connected ClustersPeter Macgregor, He SunICML 2021 · 10 citations
- p-Norm Flow Diffusion for Local Graph ClusteringKimon Fountoulakis, Di Wang, Shenghao YangICML 2020 · 30 citations
- Why the Metric Backbone Preserves Community StructureMaximilien Dreveton, Charbel Chucri, Matthias Grossglauser, Patrick ThiranNeurIPS 2024 · 3 citations
