Skip to main content
SpringerLink
Log in

Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering

  • Published:
Journal of Statistical Physics Aims and scope Submit manuscript

Abstract

We analyse a mean-field model of Personalized PageRank (PPR) on the Erdős–Rényi (ER) random graph containing a denser planted ER subgraph. We investigate the regimes where the values of PPR concentrate around the mean-field value. We also study the optimization of the damping factor, the only parameter in PPR. Our theoretical results help to understand the applicability of PPR and its limitations for local graph clustering.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Allahverdyan, A.E., Ver Steeg, G., Galstyan, A.: Community detection with and without prior information. Europhys. Lett. 90(1), 18002 (2010)

    Article  ADS  Google Scholar 

  2. Andersen, R., Lang, K.J.: Communities from seed sets. In: Proceedings of ACM WWW’06, pp. 223–232 (2006)

  3. Andersen, R., Chung, F., Lang, K.: Local graph partitioning using PageRank vectors. In: Proceedings of IEEE FOCS’06, pp. 475–486 (2006)

  4. Andersen, R., Gharan, S.O., Peres, Y., Trevisan, L.: Almost optimum local graph clustering using evolving sets. J. ACM 63(2), 15 (2016)

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  6. Avrachenkov, K., Litvak, N.: The effect of new links on Google PageRank. Stoch. Models 22(2), 319–331 (2006)

    Article  MathSciNet  Google Scholar 

  7. Avrachenkov, K., Litvak, N., Pham, K.S.: Distribution of PageRank mass among principle components of the web. In: Proceedings of WAW, pp. 16–28 (2007)

  8. Avrachenkov, K., Litvak, N., Pham, K.S.: A singular perturbation approach for choosing the PageRank damping factor. Internet Math. 5(1–2), 47–69 (2008)

    Article  MathSciNet  Google Scholar 

  9. Avrachenkov, K., Kadavankandy, A., Prokhorenkova, L.O., Raigorodskii, A.: PageRank in undirected random graphs. Internet Math. 13(1) (2017). https://doi.org/10.24166/im.09.2017

  10. Chan, S.O., Kwok, T.C., Lau, L.C.: Random walks and evolving sets: Faster convergences and limitations. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1849–1865 (2017)

  11. Chen, N., Litvak, N., Olvera-Cravioto, M.: Generalized PageRank on directed configuration networks. Random Struct. Algorithms 51(2), 237–274 (2017)

    Article  MathSciNet  Google Scholar 

  12. Dickison, M.E., Magnani, M., Rossi, L.: Multilayer Social Networks. Cambridge University Press, New York (2016)

    Book  Google Scholar 

  13. Fortunato, S., Boguñá, M., Flammini, A., Menczer, F.: On local estimations of PageRank: a mean field approach. Internet Math. 4(2–3), 245–266 (2007)

    Article  MathSciNet  Google Scholar 

  14. Garavaglia, A., van der Hofstad, R., Litvak, N.: Local weak convergence for PageRank. arXiv preprint. arXiv:1803.06146 (2018)

  15. Gleich, D., Mahoney, M.: Anti-differentiating approximation algorithms: a case study with min-cuts, spectral, and flow. In: Proceedings of International Conference on Machine Learning (ICML), pp. 1018–1025 (2014)

  16. Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. The Johns Hopkins University Press, Baltimore (2013)

    MATH  Google Scholar 

  17. Hajek, B., Wu, Y., Xu, J.: Recovering a hidden community beyond the spectral limit in \(O(|E|\log ^*|V|)\) time.” arXiv preprint. arXiv:1510.02786 (2015)

  18. Hajek, B., Wu, Y., Xu, J.: Semidefinite programs for exact recovery of a hidden community. In: Proceedings of COLT’16, pp. 1–44 (2016)

  19. Halu, A., Mondragón, R.J., Panzarasa, P., Bianconi, G.: Multiplex pagerank. PLoS ONE 8(10), e78293 (2013)

    Article  ADS  Google Scholar 

  20. Haveliwala, T.H.: Topic-sensitive PageRank: a context-sensitive ranking algorithm for web search. IEEE Trans. Knowl. Data Eng. 15(4), 784–796 (2003)

    Article  Google Scholar 

  21. Van Der Hofstad, R.: Random Graphs and Complex Networks. Cambridge University Press, New York (2016)

    Google Scholar 

  22. Jelenković, P.R., Olvera-Cravioto, M.: Information ranking and power laws on trees. Adv. Appl. Probab. 42(4), 1057–1093 (2010)

    Article  MathSciNet  Google Scholar 

  23. Jeub, L.G., Balachandran, P., Porter, M.A., Mucha, P.J., Mahoney, M.W.: Think locally, act locally: detection of small, medium-sized, and large communities in large networks. Phys. Rev. E 91(1), 012821 (2015)

    Article  ADS  Google Scholar 

  24. Kadavankandy, A., Cottatellucci, L., Avrachenkov, K.: Characterization of \(L^1\)-norm statistic for anomaly detection in Erdős Rényi graphs. In: Proceedings of IEEE CDC’16, pp. 4600–4605 (2016)

  25. Kadavankandy, A., Avrachenkov, K., Cottatellucci, L., Sundaresan, R.: The power of side-information in subgraph detection. IEEE Trans. Signal Process. 66(7), 1905–1919 (2018)

    Article  ADS  MathSciNet  Google Scholar 

  26. Kloumann, I.M., Ugander, J., Kleinberg, J.: Block models and personalized PageRank. Proc. Natl Acad. Sci. U.S.A. (2016). https://doi.org/10.1073/pnas.1611275114

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  28. Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29–123 (2009)

    Article  MathSciNet  Google Scholar 

  29. Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank citation ranking: bringing order to the web. Stanford InfoLab Research Report (1999)

  30. Spielman, D.A., Teng, S.-H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. Proc. STOC 2004, 81–90 (2004)

    MathSciNet  MATH  Google Scholar 

  31. Spielman, D.A., Teng, S.-H.: A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM J. Comput. 42(1), 1–26 (2013)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  33. Zhang, P., Moore, C., Zdeborova, L.: Phase transitions in semisupervised clustering of sparse networks. Phys. Rev. E 90(5), 052802 (2014)

    Article  ADS  Google Scholar 

  34. Zhu, Z.A., Lattanzi, S., Mirrokni, V.S.: A local algorithm for finding well-connected clusters. Proc. ICML 3, 396–404 (2013)

    Google Scholar 

Download references

Acknowledgements

This work was partly funded by the French Government (National Research Agency, ANR) through the “Investments for the Future” Program reference #ANR-11-LABX-0031-01, Inria - IIT Bombay joint team (grant IFC/DST-Inria-2016-01/448) and by EU COST Project COSTNET (CA15109).

Author information

Authors and Affiliations

  1. Inria Sophia Antipolis, Valbonne, France

    Konstantin Avrachenkov

  2. CentraleSupélec, University of Paris Saclay, Gif-sur-Yvette, France

    Arun Kadavankandy

  3. University of Twente, Enschede, The Netherlands

    Nelly Litvak

  4. Eindhoven University of Technology, Eindhoven, The Netherlands

    Nelly Litvak

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. Nelly Litvak
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Konstantin Avrachenkov.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Avrachenkov, K., Kadavankandy, A. & Litvak, N. Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering. J Stat Phys 173, 895–916 (2018). https://doi.org/10.1007/s10955-018-2099-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10955-018-2099-5

Keywords

Search

Navigation