Small world graphs by iterated local edge formation.
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.
Blanchard
Ph
P
Faculty of Physics and Research Center Bielefeld-Bonn-Stochastics, University of Bielefeld, D-33615 Bielefeld, Germany.
Krueger
T
T
Ruschhaupt
A
A