文章基本信息

标题：It's a Small World for Random Surfers
本地全文：下载
作者：Abbas Mehrabian ; Nick Wormald
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：28
页码：857-871
DOI：10.4230/LIPIcs.APPROX-RANDOM.2014.857
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：random-surfer webgraph model; PageRank-based selection model; smallworld phenomenon; height of random trees; probabilistic analysis; large deviations