start at some node N0. randomly select one of its neighbors N1. erase the edge N0-N1. randomly select one of N1's non-neighbors N2. (because we had erased N0-N1, it is guaranteed N1 has at least one non-neighbor, namely N0.) add the edge N1-N2. now, N0 is deficient, N1 has the right degree, and N2 has too many edges. if N0 = N2, then the algorithm exits having completed a cycle; in this case, nothing changed.
randomly select one of N2's neighbors N3. erase edge N2-N3. now, N2 has the right degree, but N3 is deficient. randomly select one of N3's non-neighbors N4. add edge N3-N4. now, N3 has the right degree, N4 has too many edges, and N0 remains deficient. if N0 = N4, then the algorithm exits having completed a cycle.
alternative: first, see if there is a possible selection of N3 and N4 such that N4 = N0. if so, choose one of those possibilities randomly, completing the cycle as quickly as possible. if not, do random selection as before.
if a cycle was not completed, repeat, ending with N6 with too many edges. eventually, one will cycle back to N0.
the cycle will always be of even length. does this cause statistical problems?
if desired, repeat the algorithm starting from another node, rewiring another cycle.
this is intended for the second phase of the Watts-Strogatz algorithm for generating random small-world networks. if all nodes after the first phase, typically a ring lattice, have the same degree, then this second phase will preserve that property.
how many times should the algorithm be repeated? perhaps until the average shortest path length is low enough. what is the expected value and variance of average shortest path length among random graphs whose nodes are all the same degree?
No comments :
Post a Comment