It's a Small World for Random Surfers

作者：Mehrabian Abbas^*; Wormald Nick

来源：Algorithmica, 2016, 76(2): 344-380.

DOI：10.1007/s00453-015-0034-6

• Random-surfer Webgraph model
• PageRank-based selection model
• Small-world phenomenon
• Height of random trees
• Probabilistic analysis
• Large deviations

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 provide close lower and upper bounds for the diameters of both models.

• 出版日期2016-10