Theoretical bounds on the network community profile from low-rank semi-definite programming

Yufan Huang, S. Seshadhri, D. Gleich
2/12/2026

No official code found. Best implementation: luotuoqingshan/mu-conductance-low-rank-sdp (0 stars, MIT, last commit 2026-03-02).

Abstract

We study a new connection between a technical measure called $\mu$-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 $\mu$-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 $\mu$-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.

View on arXivView PDF

Code Implementations(1)

luotuoqingshan/mu-conductance-low-rank-sdpCommunity100%
MIT

Codes for the paper: Theoretical bounds on the network community profile from low-rank semi-definite programming

01JuliaFeb 8, 20237 months agoMIT
low-rank-approximationnetwork-sciencereal-world-graphssemidefinite-programmingsparse-cuts

Similar Papers

Phase transition for detecting a small community in a large network

81% match2023

Metrics for Parametric Families of Networks

79% match1 repo2025

Optimal Noise Reduction in Dense Mixed-Membership Stochastic Block Models under Diverging Spiked Eigenvalues Condition

78% match2023

Semi-supervised Community Detection via Structural Similarity Metrics

78% match2023

Fair Information Spread on Social Networks with Community Structure

77% match2023

Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model

77% match2026

Cite this paper

@article{huang2026theoretical,
  title  = {Theoretical bounds on the network community profile from low-rank semi-definite programming},
  author = {Yufan Huang and S. Seshadhri and D. Gleich},
  year   = {2026},
  eprint = {2303.14550},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/pdf/2303.14550},
  journal = {ICML 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2303.14550.svg)](https://codeofpaper.com/paper/2303.14550)

Discussion