39
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Personalized PageRank Estimation and Search: A Bidirectional Approach

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          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 new bidirectional estimator with simple yet strong guarantees on correctness and performance, and 3x to 8x speedup over existing estimators in experiments on a diverse set of networks. Moreover, it has a clean algebraic structure which enables it to be used as a primitive for the Personalized PageRank Search problem: Given a network like Facebook, a query like "people named John", and a searching user, return the top nodes in the network ranked by PPR from the perspective of the searching user. Previous solutions either score all nodes or score candidate nodes one at a time, which is prohibitively slow for large candidate sets. We develop a new algorithm based on our bidirectional PPR estimator which identifies the most relevant results by sampling candidates based on their PPR; this is the first solution to PPR search that can find the best results without iterating through the set of all candidate results. Finally, by combining PPR sampling with sequential PPR estimation and Monte Carlo, we develop practical algorithms for PPR search, and we show via experiments that our algorithms are efficient on networks with billions of edges.

          Related collections

          Most cited references9

          • Record: found
          • Abstract: not found
          • Article: not found

          An Efficient Method for Generating Discrete Random Variables with General Distributions

            Bookmark
            • Record: found
            • Abstract: not found
            • Conference Proceedings: not found

            Scaling personalized web search

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient

                Bookmark

                Author and article information

                Journal
                2015-07-21
                2015-12-14
                Article
                10.1145/2835776.2835823
                1507.05999
                e3b64e41-107c-4304-ae07-acd982e8eee4

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                WSDM 2016
                cs.DS cs.IR cs.SI

                Social & Information networks,Data structures & Algorithms,Information & Library science

                Comments

                Comment on this article