It’s a small world for random surfers

Abbas Mehrabian; Nicholas Wormald

doi:10.1007/s00453-015-0034-6

It’s a small world for random surfers

Abbas Mehrabian
, Nicholas Wormald

School of Mathematics

Research output: Contribution to journal › Article › Research › peer-review

2 Citations (Scopus)

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

Original language	English
Pages (from-to)	344-380
Number of pages	37
Journal	Algorithmica
Volume	76
Issue number	2
DOIs	https://doi.org/10.1007/s00453-015-0034-6
Publication status	Published - 1 Oct 2016

Keywords

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

Access to Document

10.1007/s00453-015-0034-6

Cite this

@article{8988e26866bd4fe6b75496932eb3a5dc,

title = "It{\textquoteright}s a small world for random surfers",

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

keywords = "Height of random trees, Large deviations, PageRank-based selection model, Probabilistic analysis, Random-surfer Webgraph model, Small-world phenomenon",

author = "Abbas Mehrabian and Nicholas Wormald",

year = "2016",

month = oct,

day = "1",

doi = "10.1007/s00453-015-0034-6",

language = "English",

volume = "76",

pages = "344--380",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer",

number = "2",

}

TY - JOUR

T1 - It’s a small world for random surfers

AU - Mehrabian, Abbas

AU - Wormald, Nicholas

PY - 2016/10/1

Y1 - 2016/10/1

N2 - 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.

AB - 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.

KW - Height of random trees

KW - Large deviations

KW - PageRank-based selection model

KW - Probabilistic analysis

KW - Random-surfer Webgraph model

KW - Small-world phenomenon

UR - https://www.scopus.com/pages/publications/84937856319

U2 - 10.1007/s00453-015-0034-6

DO - 10.1007/s00453-015-0034-6

M3 - Article

AN - SCOPUS:84937856319

SN - 0178-4617

VL - 76

SP - 344

EP - 380

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -

It’s a small world for random surfers

Abstract

Keywords

Access to Document

Other files and links