Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Robustness of Spatial Preferential Attachment Networks Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Strong Localization in Personalized PageRank Vectors

Authors : Huda Nassar, Kyle Kloster, David F. Gleich

Published in: Algorithms and Models for the Web Graph

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The personalized PageRank diffusion is a fundamental tool in network analysis tasks like community detection and link prediction. It models the spread of a quantity from a set of seed nodes, and it has been observed to stay localized near this seed set. We derive an upper-bound on the number of entries necessary to approximate a personalized PageRank vector in graphs with skewed degree sequences. This bound shows localization under mild assumptions on the maximum and minimum degrees. Experimental results on random graphs with these degree sequences show the bound is loose and support a conjectured bound.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Distributed Algorithms for Finding Local Clusters Using Heat Kernel Pagerank
Literature
1.
Andersen, R., Chung, F., Lang, K.: Local graph partitioning using PageRank vectors. In: FOCS 2006 (2006)
2.
Avrachenkov, K., Litvak, N., Sokol, M., Towsley, D.: Quick detection of nodes with large degrees. In: Bonato, A., Janssen, J. (eds.) WAW 2012. LNCS, vol. 7323, pp. 54–65. Springer, Heidelberg (2012) CrossRef
3.
Baeza-Yates, R., Boldi, P., Castillo, C.: Generalizing PageRank: damping functions for link-based ranking algorithms. In: SIGIR 2006, pp. 308–315 (2006)
4.
5.
Benzi, M., Razouk, N.: Decay bounds and O(n) algorithms for approximating functions of sparse matrices. ETNA 28, 16–39 (2007)MathSciNetMATH
6.
Benzi, M., Boito, P., Razouk, N.: Decay properties of spectral projectors with applications to electronic structure. SIAM Rev. 55(1), 3–64 (2013)CrossRefMathSciNetMATH
7.
8.
Bonchi, F., Esfandiar, P., Gleich, D.F., Greif, C., Lakshmanan, L.V.: Fast matrix computations for pairwise and columnwise commute times and Katz scores. Internet Math. 8(1–2), 73–112 (2012)CrossRefMathSciNetMATH
9.
Chen, P., Xie, H., Maslov, S., Redner, S.: Finding scientific gems with Google pagerank algorithm. J. Informetrics 1(1), 8–15 (2007)CrossRef
10.
Chung, F.: The heat kernel as the PageRank of a graph. Proc. Natl. Acad. Sci. 104(50), 19735–19740 (2007)CrossRef
11.
Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: ACM SIGCOMM Computer Communication Review (1999)
12.
Freschi, V.: Protein function prediction from interaction networks using a random walk ranking algorithm. In: BIBE, pp. 42–48 (2007)
13.
Ghosh, R., Teng, S.-H., Lerman, K., Yan, X.: The interplay between dynamics and networks: centrality, communities, and cheeger inequality, pp. 1406–1415 (2014)
14.
Gleich, D.F., Kloster, K.: Sublinear column-wise actions of the matrix exponential on social networks. Internet Math. 11(4–5), 352–384 (2015)CrossRefMathSciNet
15.
Gori, M., Pucci, A.: ItemRank: a random-walk based scoring algorithm for recommender engines. In: IJCAI, pp. 2766–2771 (2007)
16.
Huberman, B.A., Pirolli, P.L.T., Pitkow, J.E., Lukose, R.M.: Strong regularities in World Wide Web surfing. Science 280(5360), 95–97 (1998)CrossRef
17.
Jain, A., Pantel, P.: Factrank: random walks on a web of facts. In: COLING, pp. 501–509 (2010)
18.
Jeh, G., Widom, J.: Scaling personalized web search. In: WWW, pp. 271–279 (2003)
19.
Kloster, K., Gleich, D.F.: Heat kernel based community detection. In: KDD, pp. 1386–1395 (2014)
20.
McSherry, F.: A uniform approach to accelerated PageRank computation. In: WWW, pp. 575–582 (2005)
21.
Morrison, J.L., Breitling, R., Higham, D.J., Gilbert, D.R.: Generank: using search engine technology for the analysis of microarray experiments. BMC Bioinformatics 6(1), 233 (2005)CrossRef
22.
Nie, Z., Zhang, Y., Wen, J.R., Ma, W.Y.: Object-level ranking: bringing order to web objects. In: WWW, pp. 567–574 (2005)
23.
Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank citation ranking: bringing order to the web. Technical Report 1999–66, Stanford University (1999)
24.
Winter, C., Kristiansen, G., Kersting, S., Roy, J., Aust, D., Knsel, T., Rmmele, P., Jahnke, B., Hentrich, V., Rckert, F., Niedergethmann, M., Weichert, W., Bahra, M., Schlitt, H.J., Settmacher, U., Friess, H., Bchler, M., Saeger, H.D., Schroeder, M., Pilarsky, C., Grtzmann, R.: Google goes cancer: improving outcome prediction for cancer patients by network-based ranking of marker genes. PLoS Comput. Biol. 8(5), e1002511 (2012)CrossRef
Metadata
Title
Strong Localization in Personalized PageRank Vectors
Authors
Huda Nassar
Kyle Kloster
David F. Gleich
Copyright Year
2015
Book
Algorithms and Models for the Web Graph

Print ISBN: 978-3-319-26783-8

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

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-26784-5_15

Premium Partner

    Image Credits