Document Open Access Logo

It’s a Small World for Random Surfers

Authors Abbas Mehrabian, Nick Wormald

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.857.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Abbas Mehrabian
Nick Wormald

Cite As Get BibTex

Abbas Mehrabian and Nick Wormald. It’s a Small World for Random Surfers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 857-871, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.857

Abstract

We prove logarithmic upper bounds for the diameters of the random-surfer Webgraph model and the PageRank-based selection Webgraph model, confirming the small-world phenomenon holds for them. In the special case when the generated graph is a tree, we get close lower and upper bounds for the diameters of both models.

Subject Classification

Keywords
  • random-surfer webgraph model
  • PageRank-based selection model
  • smallworld phenomenon
  • height of random trees
  • probabilistic analysis
  • large deviations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. Google Scholar
  2. S. Bhamidi. Universal techniques to analyze preferential attachment trees: global and local analysis. preprint, available via http://www.unc.edu/~bhamidi/, 2007.
  3. G. Bianconi and A.-L. Barabási. Competition and multiscaling in evolving networks. Europhys. Lett., 54(4):436-442, 2001. Google Scholar
  4. A. Blum, T.-H. H. Chan, and M. R. Rwebangira. A random-surfer web-graph model. In Proc. of 8th Workshop on Algorithm Engineering and Experiments and 3rd Workshop on Analytic Algorithmics and Combinatorics, pages 238-246, 2006. Google Scholar
  5. B. Bollobás and O. Riordan. The diameter of a scale-free random graph. Combinatorica, 24(1):5-34, January 2004. Google Scholar
  6. A. Bonato. A course on the web graph, volume 89 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2008. Google Scholar
  7. N. Broutin and L. Devroye. Large deviations for the weighted height of an extended class of trees. Algorithmica, 46(3-4):271-297, 2006. Google Scholar
  8. D. Chakrabarti and C. Faloutsos. Graph Mining: Laws, Tools, and Case Studies. Synthesis Lectures on Data Mining and Knowledge Discovery. Morgan & Claypool Publishers, 2012. Google Scholar
  9. P. Chebolu and P. Melsted. Pagerank and the random surfer model. In Proceedings of the 19th annual ACM-SIAM symposium on Discrete algorithms, SODA'08, pages 1010-1018, Philadelphia, PA, USA, 2008. Google Scholar
  10. F. Chung and L. Lu. Complex graphs and networks, volume 107 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 2006. Google Scholar
  11. A. Dembo and O. Zeitouni. Large deviations techniques and applications, volume 38 of Stochastic Modelling and Applied Probability. Springer-Verlag, Berlin, 2010. Corrected reprint of the second (1998) edition. Google Scholar
  12. L. Devroye, O. Fawzi, and N. Fraiman. Depth properties of scaled attachment random recursive trees. Random Structures Algorithms, 41(1):66-98, 2012. Google Scholar
  13. S. Dommers, R. van der Hofstad, and G. Hooghiemstra. Diameters in preferential attachment models. Journal of Statistical Physics, 139(1):72-107, 2010. Google Scholar
  14. E. Drinea, A. Frieze, and M. Mitzenmacher. Balls and bins models with feedback. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, SODA'02, pages 308-315, Philadelphia, PA, USA, 2002. Google Scholar
  15. R. Durrett. Random graph dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2010. Google Scholar
  16. G. Ergün and G.J. Rodgers. Growing random networks with fitness. Physica A: Statistical Mechanics and its Applications, 303(1-2):261-272, 2002. Google Scholar
  17. P. L. Krapivsky and S. Redner. Organization of growing random networks. Phys. Rev. E, 63:066123, May 2001. Google Scholar
  18. J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data, 1(1), March 2007. Google Scholar
  19. L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, 1999. Google Scholar
  20. G. Pandurangan, P. Raghavan, and E. Upfal. Using pagerank to characterize web structure. In Proceedings of the 8th Annual International Conference on Computing and Combinatorics, COCOON'02, pages 330-339, London, UK, UK, 2002. Google Scholar
  21. G. Pandurangan, P. Raghavan, and E. Upfal. Using pagerank to characterize web structure. Internet Mathematics, 3(1):1-20, 2006. Google Scholar
  22. B. Pittel. Note on the heights of random recursive trees and random m-ary search trees. Random Structures and Algorithms, 5(2):337-347, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact