Small World Model based on a Sphere Homeomorphic Geometry

2018/08/02 by Viertel, Santiago, Vignatti, André Luís
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Social and Information Networks (cs.SI)

paper · doi:10.48550/arxiv.1808.01028

Abstract

We define a small world model over the octahedron surface and relate its distances with those of embedded spheres, preserving constant bounded distortions. The model builds networks with both number of vertices and size Θ(n²), where n is the size parameter. It generates long-range edges with probability proportional to the inverse square of the distance between the vertices. We show a greedy routing algorithm that finds paths in the small world network with O(log²n) expected size. The probability of creating cycles of size three (C3) with long-range edges in a vertex is O(log^-1n). Furthermore, there are Θ(n²) expected number of C3's in the entire network.

Related

• Labeling Algorithm and Compact Routing Scheme for a Small World Network Model
• Small worlds
• Growing Small-World Networks Generated by Attaching to Edges
• The small-world phenomenon: a model, explanations, characterizations and examples
• Routing in Poisson small-world networks