How to efficiently distinguish the rewired edges in WattsStrogatzGraphDistribution?

Question

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,

WattsStrogatzGraphDistribution[100,0.05]

can give:

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.

Answer 1

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}