Premium
Justifying the small‐world phenomenon via random recursive trees
Author(s) -
Mehrabian Abbas
Publication year - 2017
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20648
Subject(s) - random graph , logarithm , mathematics , combinatorics , mathematical proof , upper and lower bounds , simple (philosophy) , computer science , graph , discrete mathematics , mathematical analysis , philosophy , geometry , epistemology
We present a new technique for proving logarithmic upper bounds for diameters of evolving random graph models, which is based on defining a coupling between random graphs and variants of random recursive trees. The advantage of the technique is three‐fold: it is quite simple and provides short proofs, it is applicable to a broad variety of models including those incorporating preferential attachment, and it provides bounds with small constants. We illustrate this by proving, for the first time, logarithmic upper bounds for the diameters of the following well known models: the forest fire model, the copying model, the PageRank‐based selection model, the Aiello‐Chung‐Lu models, the generalized linear preference model, directed scale‐free graphs, the Cooper‐Frieze model, and random unordered increasing k ‐trees. Our results shed light on why the small‐world phenomenon is observed in so many real‐world graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 201–224, 2017