iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/978-3-319-26784-5_12
PageRank in Undirected Random Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

PageRank in Undirected Random Graphs

  • Conference paper
  • First Online:
Algorithms and Models for the Web Graph (WAW 2015)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9479))

Included in the following conference series:

Abstract

PageRank has numerous applications in information retrieval, reputation systems, machine learning, and graph partitioning. In this paper, we study PageRank in undirected random graphs with expansion property. The Chung-Lu random graph represents an example of such graphs. We show that in the limit, as the size of the graph goes to infinity, PageRank can be represented by a mixture of the restart distribution and the vertex degree distribution.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    For a vector \(x \in \mathbf {R}^n,\) \(\left| \left| x\right| \right| _2 = \sqrt{\sum _i |x_i|^2}\) is the 2-norm.

  2. 2.

    For any matrix \(A \in \mathbf {R}^{m,n}, \left| \left| A\right| \right| _2 = \sup _{x, \left| \left| x\right| \right| _2=1} \left| \left| Ax\right| \right| _2\) [6].

  3. 3.

    For two matrices \(A \in \mathbf {R}^{m,n},\) and \(B \in \mathbf {R}^{n,p},\) \(\left| \left| AB\right| \right| _2 \le \left| \left| A\right| \right| _2 \left| \left| B\right| \right| _2\).

References

  1. Andersen, R., Chung, F., Lang, K.: Local graph partitioning using pagerank vectors. In: Proceedings of IEEE FOCS (2006)

    Google Scholar 

  2. Avrachenkov, K., Cottatellucci, L., Kadavankandy, A.: Spectral properties of random matrices for stochastic block model. In Proceedings of WiOpt Workshop PhysComNet (2015)

    Google Scholar 

  3. Avrachenkov, K., Dobrynin, V., Nemirovsky, D., Pham, S.K., Smirnova, E.: Pagerank based clustering of hypertext document collections. In: Proceedings of ACM SIGIR, pp. 873–874 (2008)

    Google Scholar 

  4. Avrachenkov, K., Gonçalves, P., Mishenin, A., Sokol, M.: Generalized optimization framework for graph-based semi-supervised learning. In: Proceedings of SIAM Conference on Data Mining, vol. 9 (2012)

    Google Scholar 

  5. Avrachenkov, K., Lebedev, D.: PageRank of scale-free growing networks. Internet Math. 3(2), 207–231 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bhatia, R.: Matrix analysis. Springer Sci. Bus. Media 169, (2013)

    Google Scholar 

  7. Billingsley, P.: Probability and measure. Wiley, New York (2008)

    Google Scholar 

  8. Boudin, F.: A comparison of centrality measures for graph-based keyphrase extraction. In: Proceedings of the International Joint Conference on Natural Language Processing (IJCNLP) (2013)

    Google Scholar 

  9. Chen, N., Litvak, N., Olvera-Cravioto, M.: Pagerank in scale-free random graphs. In: Bonato, A., Graham, F.C., Prałat, P. (eds.) WAW 2014. LNCS, vol. 8882, pp. 120–131. Springer, Heidelberg (2014)

    Google Scholar 

  10. Chen, N., Litvak, N., Olvera-Cravioto, M.: Ranking algorithms on directed configuration networks (2014). Preprint arXiv:1409.7443

  11. Chung, F.: A local graph partitioning algorithm using heat kernel pagerank. In: Avrachenkov, K., Donato, D., Litvak, N. (eds.) WAW 2009. LNCS, vol. 5427, pp. 62–75. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  12. Chung, F.: Spectral Graph Theory. American Mathematical Soc, Providence (1997)

    MATH  Google Scholar 

  13. Chung, F., Lu, L.: The average distances in random graphs with given expected degrees. PNAS 99(25), 15879–15882 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  14. Chung, F., Lu, L., Vu, V.: Spectra of random graphs with given expected degrees. PNAS 100(11), 6313–6318 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  15. Chung, F., Radcliffe, M.: On the spectra of general random graphs. Electron. J. Comb. 18(1), 215 (2011)

    MathSciNet  Google Scholar 

  16. Ding, C., He, X., Husbands, P., Zha, H., Simon, H.D.: PageRank. In: Proceedings of ACM SIGIR HITS and a Unified Framework for Link Analysis (2002)

    Google Scholar 

  17. Erdős, P., Rényi, A.: On random graphs. Publicationes Math. Debrecen 6, 290–297 (1959)

    Google Scholar 

  18. Fortunato, S., Boguñá, M., Flammini, A., Menczer, F.: Approximating pagerank from in-degree. In: Aiello, W., Broder, A., Janssen, J., Milios, E.E. (eds.) WAW 2006. LNCS, vol. 4936, pp. 59–71. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  19. Gkorou, D., Vinko, T., Pouwelse, J., Epema, D.: Leveraging node properties in random walks for robust reputations in decentralized networks. In: Proceedings of IEEE Peer-to-Peer Computing (P2P) (2013)

    Google Scholar 

  20. Haveliwala, T.H.: Topic-sensitive pagerank. In: Proceedings of WWW, pp. 517–526 (2002)

    Google Scholar 

  21. Kamvar, S.D., Schlosser, M.T., Garcia-Molina, H.: The eigentrust algorithm for reputation management in p2p networks. In: Proceedings of WWW (2003)

    Google Scholar 

  22. Langville, A.N., Meyer, C.D.: Deeper inside pagerank. Internet Math. 1(3), 335–380 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  23. Litvak, N., Scheinhardt, W.R., Volkovich, Y.: In-degree and pagerank: why do they follow similar power laws? Internet Math. 4(2–3), 175–198 (2007)

    Article  MathSciNet  Google Scholar 

  24. Levin, D.A., Peres, Y., Wilmer, E.L.: Markov chains and mixing times. American Mathematical Soc, Providence (2009)

    MATH  Google Scholar 

  25. Moler, C., Moler, K.: Numerical Computing with MATLAB. SIAM (2003)

    Google Scholar 

  26. Page, L., Brin, S., Motwani, R., Winograd, T.: Pagerank: bringing order to the web. Stanford Digital Libraries Working Paper, v. 72 (1997)

    Google Scholar 

  27. Perra, N., Fortunato, S.: Spectral centrality measures in complex networks. Phys. Rev. E 78, 036107 (2008)

    Article  MathSciNet  Google Scholar 

  28. Vadhan, S.: Pseudorandomness. Found. Trends Theoret. Comput. Sci. 7(1–3), 1–336 (2012)

    Article  MathSciNet  Google Scholar 

  29. Volkovich, Y., Litvak, N.: Asymptotic analysis for personalized web search. Adv. Appl. Prob. 42(2), 577–604 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  30. Yeh, E., Ramage, D., Manning, C.D., Agirre, E., Soroa, A.: WikiWalk: random walks on Wikipedia for semantic relatedness. In: Proceedings of the Workshop on Graph-based Methods for Natural Language Processing (2009)

    Google Scholar 

Download references

Acknowledgements

We would like to thank Nelly Litvak for stimulating discussions on the topic of the paper. This work was partially supported by the French Government (National Research Agency, ANR) through the “Investments for the Future” Program reference ANR-11-LABX-0031-01 and ADR “Network Science” from Joint Inria Alcatel-Lucent Lab.

Author information

Authors and Affiliations

  1. Inria Sophia Antipolis, Valbonne, France

    Konstantin Avrachenkov & Arun Kadavankandy

  2. Yandex, Moscow, Russia

    Liudmila Ostroumova Prokhorenkova & Andrei Raigorodskii

  3. Moscow Institute of Physics and Technology, Moscow, Russia

    Andrei Raigorodskii

  4. Moscow State University, Moscow, Russia

    Andrei Raigorodskii

  5. Buryat State University, Ulan-ude, Russia

    Andrei Raigorodskii

Authors
  1. Konstantin Avrachenkov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Arun Kadavankandy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Liudmila Ostroumova Prokhorenkova
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andrei Raigorodskii
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Arun Kadavankandy .

Editor information

Editors and Affiliations

  1. Purdue University, West Lafayette, Indiana, USA

    David F. Gleich

  2. Eindhoven University of Technology, Eindhoven, The Netherlands

    Júlia Komjáthy

  3. University of Twente, Enschede, The Netherlands

    Nelly Litvak

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Avrachenkov, K., Kadavankandy, A., Ostroumova Prokhorenkova, L., Raigorodskii, A. (2015). PageRank in Undirected Random Graphs. In: Gleich, D., Komjáthy, J., Litvak, N. (eds) Algorithms and Models for the Web Graph. WAW 2015. Lecture Notes in Computer Science(), vol 9479. Springer, Cham. https://doi.org/10.1007/978-3-319-26784-5_12

Download citation

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

  • Published:

  • Publisher Name: Springer, Cham

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

  • Online ISBN: 978-3-319-26784-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation