Related Experiment Videos
Small world graphs by iterated local edge formation.
Ph Blanchard1, T Krueger, A Ruschhaupt
1Faculty of Physics and Research Center Bielefeld-Bonn-Stochastics, University of Bielefeld, D-33615 Bielefeld, Germany.
Summary
This study introduces a novel method for generating small-world graphs using local edge dynamics, achieving logarithmic diameter and high clustering without preferential attachment. The research reveals a phase transition dependent on initial conditions.
Area of Science:
- Graph theory
- Network science
- Complex systems
Background:
- Traditional network models often rely on global rules or preferential attachment.
- Understanding the emergence of small-world properties in networks is crucial for various scientific domains.
Purpose of the Study:
- To investigate graph evolution through local edge creation and destruction.
- To characterize the resulting network properties, such as diameter and clustering coefficients.
- To explore the influence of initial conditions on graph formation.
Main Methods:
- Starting with a large-diameter circle graph.
- Implementing successive local edge creation and destruction within vertex neighborhoods.
- Analyzing network metrics including diameter, clustering coefficients, and degree distribution.
Main Results:
- Successfully generated small-world graphs.
- Observed logarithmic diameter and high clustering coefficients.
- Identified a fat-tailed degree distribution.
- Discovered a phase transition related to initial conditions.
Conclusions:
- Local edge dynamics can effectively create small-world networks.
- The absence of preferential attachment does not preclude small-world properties.
- Initial conditions play a significant role in the emergent network structure.