STA 290 Seminar Series
Thursday, March 3rd, 4:10pm, MSB 1147 (Colloquium Room) (note: rescheduled from Feb 4)
Refreshments at 3:30pm in MSB 4110 (Statistics Lounge)
Speaker: Xiaodong Li (Statistics, UC Davis)
Title: “Convexified modularity maximization for degree-corrected stochastic block models”
Abstract: The stochastic block model (SBM) is a popular framework for studying community detection in networks. This model is limited by the assumption that all nodes in the same community are statistically equivalent and have equal expected degrees. The degree-corrected stochastic block model (DCSBM) is a natural extension of SBM that allows for degree heterogeneity within communities. This paper proposes a convexified modularity maximization approach for estimating the hidden communities under DCSBM. This approach is based on a convex programming relaxation of the classical (generalized) modularity maximization formulation, followed by a novel doubly-weighted `1-norm k-median procedure. We establish nonasymptotic theoretical guarantees for both approximate clustering and perfect clustering. In the special case of SBM, these theoretical results match the best-known performance guarantees of computationally feasible algorithms. Numerically, we provide an efficient implementation of our algorithm, which is applied to both synthetic and real-world networks. Experiment results show that our method enjoys competitive empirical performance compared to the state-of-the-art tractable methods in the literature.
This is a joint work with Yudong Chen and Jiaming Xu.