Small World Graphs by the iterated "My Friends are Your Friends'' Principle

Abstract

We study graphs obtained by successive creation and destruction of edges into small neighborhoods of the vertices. Starting with a circle graph of large diameter we obtain small world graphs with logarithmic diameter, high clustering coefficients and a fat tail distribution for the degree. Only local edge formation processes are involved and no preferential attachment was used. Furthermore we found an interesting phase transition with respect to the initial conditions.

Latex, 12 pages with 10 figures

References in corpus (7)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Growing Scale-Free Networks with Tunable Clustering
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Emergence of a small world from local interactions: Modeling acquaintance networks
• Evolving networks with distance preferences
• The "Cameo Principle" and the Origin of Scale-Free Graphs in Social Networks

Cited by in corpus (7)

• Evolving Apollonian Networks with Small-world Scale-free topologies
• The Network of EU-Funded Collaborative R&D Projects
• Evolving small-world networks with geographical attachment preference
• How Do Networks Become Navigable?
• From regular to growing small-world networks
• The Epidemics of Corruption
• Modelling Complex Networks: Cameo Graphs And Transport Processes