From Random Graph to Small World by Wandering

2008/04/01 by Bruno Gaume, Fabien Mathieu, Gaume, Bruno +1
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Opinion Dynamics and Social Influence #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.0804.0149

openalex publication_date 2008/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Numerous studies show that most known real-world complex networks share similar properties in their connectivity and degree distribution. They are called small worlds. This article gives a method to turn random graphs into Small World graphs by the dint of random walks.

Citations

• Evolution of networks
• Power laws, Pareto distributions and Zipf's law

Related

• The evolution of navigable small-world networks
• A simple and flexible algorithm to generate real-world networks
• On Small-World Networks: Survey and Properties Analysis
• The ubiquity of small-world networks
• Intentional Walks on Scale Free Small Worlds