The networks in consideration are directed graphs without loops or multiple edges. Similar networks have the same vertex set and the same in-degrees and out-degrees. Ideally we want to sample uniformly at random from the set of similar graphs.
As I understand it, network motif detection programs typically use a well-studied switching process: take two directed edges (a,c) and (b,d) uniformly at random, then replace with (a,d) and (b,c). Reject if a loop or multiple edge is formed. (see e.g. http://arxiv.org/abs/cond-mat/0312028)
Judging from its source code, Kavosh seems to speed-up this process in the following way. For all vertices v do:
- Let a=v.
- b is a random vertex b<>a.
- c is a random out-neighbour of a.
- d is a random out-neighbour of c.
And as before, replace edges (a,c) and (b,d) with (a,d) and (b,c). Reject if a loop or multiple edge is formed. Repeat this whole process three times (so there can be up to 3|V| switches applied in total, where |V| is the number of vertices). [For some reason I'm unsure of, the last two steps are also repeated up to three times.]
Question: What effects could one expect to see as a result of this change? How concerned should one be about this change?
The Kavosh paper does not say much about it:
In our approach, similar to Milo's random model [17,18] switching operations are applied on the edges of the input network repeatedly, until the network is well randomized.