3
$\begingroup$

The Watts-Strogatz model describes a mechanism of generating small-world networks.

The idea is to start from a ring network in which each node is connected a fixed number of its closest neighbors. After that, a rewiring is performed in which each link present in the network has a probability $p$ of changing one of its endpoints to a new random node. The closer $p$ to 1, the more random is the network.

Is there a similar small-world model for bipartite graphs? That is, is there a mechanism for generating random bipartite graphs that possess the usual properties of small-world networks (a.k.a., the maximum of the minimum distance between any pair of nodes scales no higher than as the logarithm of the number of nodes)?

Improve this question
$\endgroup$
3
  • $\begingroup$ Currently I have the idea of using two initial rings (top and bottom) instead of one, such that edges connect nodes from different rings. Then each node from the top ring is connected to a fixed number of its "closest neighbors" in the bottom ring. The rewiring step is the same as in the Watts-Strogatz model, only that each rewired links still connect top nodes to bottom nodes. $\endgroup$
    – a06e
    Commented Jul 4, 2014 at 0:35
  • $\begingroup$ Sounds good to me. Did you try that? BTW, you might want to have a look at this proposal: area51.stackexchange.com/proposals/61500/network-science $\endgroup$
    – Vincent Labatut
    Commented Jul 4, 2014 at 10:46
  • $\begingroup$ goldreich 1-way function built out of bipartite graphs seems to have interesting but so-far unanalyzed graph properties. wonder if it could be small world or scale free for some choice of parameters. also expander graphs maybe have some overlap or relationship with either small world or scale free graphs for some parameters? $\endgroup$
    – vzn
    Commented Jul 8, 2014 at 20:32

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.