Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering
We analyse a mean-field model of Personalized PageRank on the Erdos-Renyi random graph containing a denser planted Erdos-Renyi subgraph. We investigate the regimes where the values of Personalized PageRank concentrate around the mean-field value. We also study the optimization of the damping factor, the only parameter in Personalized PageRank. Our theoretical results help to understand the applicability of Personalized PageRank and its limitations for local graph clustering.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringGraph ClusteringSimilar Papers 제목 키워드 기반
Fast Incremental and Personalized PageRank
In this paper, we analyze the efficiency of Monte Carlo methods for incremental computation of PageRank, personalized PageRank, and similar random walk based methods (with focus on SALSA), on large-scale dynamically evol…
Effective Resistance-based Germination of Seed Sets for Community Detection
Community detection is, at its core, an attempt to attach an interpretable function to an otherwise indecipherable form. The importance of labeling communities has obvious implications for identifying clusters in social …
Community DetectionVarying Vector Representations and Integrating Meaning Shifts into a PageRank Model for Automatic Term Extraction
We perform a comparative study for automatic term extraction from domain-specific language using a PageRank model with different edge-weighting methods. We vary vector space representations within the PageRank graph algo…
Term ExtractionEfficient Algorithms for Personalized PageRank
We present new, more efficient algorithms for estimating random walk scores such as Personalized PageRank from a given source node to one or several target nodes. These scores are useful for personalized search and recom…
Personalized PageRank Estimation and Search: A Bidirectional Approach
We present new algorithms for Personalized PageRank estimation and Personalized PageRank search. First, for the problem of estimating Personalized PageRank (PPR) from a source distribution to a target node, we present a …