nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Bidirectional PageRank Estimation: From Average-Case to Worst-Case

verfasst von : Peter Lofgren, Siddhartha Banerjee, Ashish Goel

Erschienen in: Algorithms and Models for the Web Graph

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We present a new algorithm for estimating the Personalized PageRank (PPR) between a source and target node on undirected graphs, with sublinear running-time guarantees over the worst-case choice of source and target nodes. Our work builds on a recent line of work on bidirectional estimators for PPR, which obtained sublinear running-time guarantees but in an average-case sense, for a uniformly random choice of target node. Crucially, we show how the reversibility of random walks on undirected networks can be exploited to convert average-case to worst-case guarantees. While past bidirectional methods combine forward random walks with reverse local pushes, our algorithm combines forward local pushes with reverse random walks. We also discuss how to modify our methods to estimate random-walk probabilities for any length distribution, thereby obtaining fast algorithms for estimating general graph diffusions, including the heat kernel, on undirected networks.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel PageRank in Undirected Random Graphs

Nächstes Kapitel Distributed Algorithms for Finding Local Clusters Using Heat Kernel Pagerank

Specifically, for each node u in the original graph, SALSA creates two virtual nodes, a “consumer-node” \(u'\) and a “producer-node” \(u''\), which are linked by an undirected edge. Any directed edge (u, v) is then converted into an undirected edge \((u', v'')\) from u’s consumer node to v’s producer node.

Following convention, we use w.h.p. to mean with probability greater than \(1-\frac{1}{n}\).

Andersen, R., Borgs, C., Chayes, J., Hopcraft, J., Mirrokni, V.S., Teng, S.-H.: Local computation of pagerank contributions. In: Bonato, A., Chung, F.R.K. (eds.) WAW 2007. LNCS, vol. 4863, pp. 150–165. Springer, Heidelberg (2007) CrossRef

Andersen, R., Chung, F., Lang, K.: Local graph partitioning using pagerank vectors. In: 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 (2006)

Avrachenkov, K., Gonçalves, P., Sokol, M.: On the choice of kernel and labelled data in semi-supervised learning methods. In: Bonato, A., Mitzenmacher, M., Prałat, P. (eds.) WAW 2013. LNCS, vol. 8305, pp. 56–67. Springer, Heidelberg (2013) CrossRef

Avrachenkov, K., Litvak, N., Nemirovsky, D., Osipova, N.: Monte carlo methods in pagerank computation: when one iteration is sufficient. SIAM J. Numer. Anal. 45, 890–904 (2007)CrossRefMathSciNetMATH

Backstrom, L., Leskovec, J.: Supervised random walks: predicting and recommending links in social networks. In: Proceedings of the Fourth ACM International Conference on Web Search and Data Mining. ACM (2011)

Bahmani, B., Chowdhury, A., Goel, A.: Fast incremental and personalized pagerank. Proc. VLDB Endowment 4(3), 173–184 (2010)CrossRef

Baluja, S., Seth, R., Sivakumar, D., Jing, Y., Yagnik, J., Kumar, S., Ravichandran, D., Aly, M.: Video suggestion and discovery for youtube: taking random walks through the view graph. In: Proceedings of the 17th International Conference on World Wide Web. ACM (2008)

Banerjee, S., Lofgren, P.: Fast bidirectional probability estimation in markov models. In: NIPS (2015)

Borgs, C., Brautbar, M., Chayes, J., Teng, S.-H.: A sublinear time algorithm for pagerank computations. In: Bonato, A., Janssen, J. (eds.) WAW 2012. LNCS, vol. 7323, pp. 41–53. Springer, Heidelberg (2012) CrossRef

10.

Bressan, M., Peserico, E., Pretto, L.: Approximating pagerank locally with sublinear query complexity. arXiv preprint arXiv:1404.1864 (2014)

11.

Chung, F.: The heat kernel as the pagerank of a graph. Proc. Nat. Acad. Sci. 104, 19735–19740 (2007)CrossRef

12.

Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York (2009)CrossRefMATH

13.

Gleich, D.F.: PageRank beyond the web. arXiv, cs.SI:1407.5107 (2014). Accepted for publication in SIAM Review

14.

Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 68–75. Springer, Heidelberg (2011)

15.

Grolmusz, V.: A note on the pagerank of undirected graphs. Inf. Process. Lett. 115, 633–634 (2015)CrossRefMathSciNet

16.

Gupta, P., Goel, A., Lin, J., Sharma, A., Wang, D., Zadeh, R.: Wtf: the who to follow service at twitter. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 505–514. International World Wide Web Conferences Steering Committee (2013)

17.

Kale, S., Peres, Y., Seshadhri, C.: Noise tolerance of expanders and sublinear expander reconstruction. In: Proceedings of the IEEE FOCS 2008. IEEE (2008)

18.

Kloster, K., Gleich, D.F.: Heat kernel based community detection. In: Proceedings of the ACM SIGKDD 2014 (2014)

19.

Lempel, R., Moran, S.: The stochastic approach for link-structure analysis (salsa) and the tkc effect. Comput. Netw. 33(1), 387–401 (2000)CrossRef

20.

Lofgren, P., Banerjee, S., Goel, A.: Personalized pagerank estimation and search: A bidirectional approach. Technical report (2015)

21.

Lofgren, P., Goel, A.: Personalized pagerank to a target node. arXiv preprint arXiv:1304.4658 (2013)

22.

Lofgren, P.A., Banerjee, S., Goel, A., Seshadhri, C.: FAST-PPR: scaling personalized pagerank estimation for large graphs. In: Proceedings of the ACM SIGKDD 2014. ACM (2014)

23.

Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: bringing order to the web (1999)

Titel: Bidirectional PageRank Estimation: From Average-Case to Worst-Case
verfasst von: Peter Lofgren
Siddhartha Banerjee
Ashish Goel
Verlag: Springer International Publishing
Buch: Algorithms and Models for the Web Graph
Print ISBN: 978-3-319-26783-8

Electronic ISBN: 978-3-319-26784-5

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-26784-5_13

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"