3
$\begingroup$

Kavosh is a recent package designed for network motif discovery. To give a comparison, Kavosh generates a collection of similar networks using an MCMC process.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.