Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The WattsStrogatzGraphDistribution function is a way to construct random graphs based on Watts and Strogatz small world model. The WattsStrogatzGraphDistribution is constructed starting from CirculantGraph[n,Range[k]] (k=2 unless you assign another value for it)and rewiring each edge with probability p. Each edge is rewired by changing one of the vertices, making sure that no loop or multiple edge is created. For instance,


can give: Random Graph

I need to distinguish the rewired(short-cut) edges from the original ones so I can measure some of their statistical properties(Average of short-cut and non-short-cut edge betweenness). One possibility was to forget about this subroutine in Mathematica, and construct everything I need from scratch. I have not ruled out that possibility yet, but since I will be dealing with not so tiny graphs(about 500 nodes) and I will have to repeat the procedure few hundred times in order to obtain reliable average values; I would rather do something more efficient.

Another idea which I had was to calculate the EdgeBetweennessCentrality of all the edges and then cluster them into two groups(one naively expects the betweenness of the short-cut edges to be higher). Unfortunately this doesn't work because the edges close to rewired edge will also get higher betweenness centrality and I couldn't distinguish them apart from the each other.

share|improve this question
up vote 3 down vote accepted

Here's the brute force way:

og = CirculantGraph[100, Range[2]];

g = RandomGraph[WattsStrogatzGraphDistribution[100, 0.05]];

oelist = Sort /@ EdgeList[og];

elist = Sort /@ EdgeList[g];

rewired = Complement[oelist, elist]

{4 <-> 6, 19 <-> 20, 21 <-> 23, 26 <-> 27, 31 <-> 32, 33 <-> 35, 44 <-> 45, 55 <-> 56, 56 <-> 58, 59 <-> 61, 70 <-> 72}

share|improve this answer
Although it's brute force, I like this answer. Also, I didn't know WattsStrogatz literally uses circulantgraph!! Thanks. – Ali Apr 16 '14 at 14:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.