Home / Events / Community Detection on the Weighted Stochastic Block Model
Seminars

Community Detection on the Weighted Stochastic Block Model

With Min Xu (U Penn)

Community Detection on the Weighted Stochastic Block Model

Ever since the seminal paper of Decelle et al appeared in 2011, Stochastic Block Model has become the most well-studied and well-understood model for network data with an underlying community structure. Yet SBM has a limitation: it assumes that each network edge is Bernoulli 0/1—either on or off; this is restrictive because weighted edges are ubiquitous and, when edge weights are present, it may be important to incorporate them into a clustering algorithm. In this talk, we study the weighted generalization of the stochastic block model in which an edge random variable can have a general mixed distribution rather than Bernoulli; we propose and analyze an algorithm for the weighted SBM based a binning procedure for nonparametric density estimation. We show that this procedure has error rate exponential in the information divergence that governs the thresholds for the unweighted Stochastic Block Model—a rate that in many cases have matching lower bounds.

Joint work with Varun Jog and Po-Ling Loh from University of Wisconsin Madison and Zongming Ma from the University of Pennsylvania.

Add to your calendar or Include in your list