title: Hybrid graphs as a framework for the small-world effect.
abstract: In this paper we formalize the small-world effect which describes the surprising fact that a hybrid graph composed of a local graph component and a very sparse random graph has a diameter of O(ln n) whereby the diameter of both components alone is much higher. We show that a large family of these hybrid graphs shows this effect and that this generalized family also includes classic small-world models proposed by various authors although not all of them are captured by the small-world definition given by Watts and Strogatz. Furthermore, we give a detailed upper bound of the hybrid's graph diameter for different choices of the expected number of random edges by applying a new kind of proof pattern that is applicable to a large number of hybrid graphs. The focus in this paper is on presenting a flexible family of hybrid graphs showing the small-world effect that can be tuned closely to real-world systems.
authors.affiliation: Wilhelm-Schickard-Institut für Informatik, Universität Tübingen.
authors.forename: Katharina A
authors.initials: KA
authors.lastname: Lehmann
authors.forename: Hendrik D
authors.initials: HD
authors.lastname: Post
authors.forename: Michael
authors.initials: M
authors.lastname: Kaufmann