Block models and personalized PageRank
Abstract
Methods based on PageRank have been fundamental to work on identifying communities in networks, but, to date, there has been little formal basis for the effectiveness of these methods. We establish a surprising connection between the personalized PageRank algorithm and the stochastic block model for random graphs, showing that personalized PageRank, in fact, provides the optimal geometric discriminant function for separating the communities in stochastic block models over a wide class of functions. Building on this result, we develop stronger classifiers that, although scalable, are competitive with computationally much more demanding methods such as belief propagation.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 20, 2016
- Source ID
- 10.1073/pnas.1611275114
Entities
People
- Isabel M. Kloumann
- Johan Ugander
- Jon Kleinberg
Organizations
- Army Research Office
- Cornell University
- Meta
- Simons Foundation
- Stanford University