Timezone: »
Real world networks often have nodes belonging to multiple communities. We consider the detection of overlapping communities under the popular Mixed Membership Stochastic Blockmodel (MMSB). Using the inherent geometry of this model, we link the inference of overlapping communities to the problem of finding corners in a noisy rotated and scaled simplex, for which consistent algorithms exist. We use this as a building block for our algorithm to infer the community memberships of each node, and prove its consistency. As a byproduct of our analysis, we derive sharp row-wise eigenvector deviation bounds, and provide a cleaning step that improves the performance drastically for sparse networks. We also propose both necessary and sufficient conditions for identifiability of the model, while existing methods typically present sufficient conditions. The empirical performance of our method is shown using simulated and real datasets scaling up to 100,000 nodes.
Author Information
Xueyu Mao (University of Texas at Austin)
More from the Same Authors
-
2018 Poster: Overlapping Clustering Models, and One (class) SVM to Bind Them All »
Xueyu Mao · Purnamrita Sarkar · Deepayan Chakrabarti -
2018 Spotlight: Overlapping Clustering Models, and One (class) SVM to Bind Them All »
Xueyu Mao · Purnamrita Sarkar · Deepayan Chakrabarti -
2017 : Posters »
Reihaneh Rabbany · Tianxi Li · Jacob Carroll · Yin Cheng Ng · Xueyu Mao · Alexandre Hollocou · Jeric Briones · James Atwood · John Santerre · Natalie Klein · Pranamesh Chakraborty · Zahra Razaee · Chandan Singh · Arun Suggala · Beilun Wang · Andrew R. Lawrence · Aditya Grover · FARSHAD HARIRCHI · radhika arava · Qing Zhou · Takatomi Kubo · Josue Orellana · Govinda Kamath · Vivek Kumar Bagaria