Timezone: »
Poster
The Consistency of Common Neighbors for Link Prediction in Stochastic Blockmodels
Purnamrita Sarkar · Deepayan Chakrabarti · peter j bickel
Link prediction and clustering are key problems for network-structureddata. While spectral clustering has strong theoretical guaranteesunder the popular stochastic blockmodel formulation of networks, itcan be expensive for large graphs. On the other hand, the heuristic ofpredicting links to nodes that share the most common neighbors withthe query node is much fast, and works very well in practice. We showtheoretically that the common neighbors heuristic can extract clustersw.h.p. when the graph is dense enough, and can do so even in sparsergraphs with the addition of a ``cleaning'' step. Empirical results onsimulated and real-world data support our conclusions.
Author Information
Purnamrita Sarkar (UT Austin)
Deepayan Chakrabarti (UT Austin)
peter j bickel (U C Berkeley)
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 -
2018 Poster: Mean Field for the Stochastic Blockmodel: Optimization Landscape and Convergence Issues »
Soumendu Sundar Mukherjee · Purnamrita Sarkar · Y. X. Rachel Wang · Bowei Yan -
2017 Poster: Convergence of Gradient EM on Multi-component Mixture of Gaussians »
Bowei Yan · Mingzhang Yin · Purnamrita Sarkar -
2017 Poster: On clustering network-valued data »
Soumendu Sundar Mukherjee · Purnamrita Sarkar · Lizhen Lin -
2016 Poster: On Robustness of Kernel Clustering »
Bowei Yan · Purnamrita Sarkar