<p>The <a href="http://www.scholarpedia.org/article/Small-world_network#Watts-Strogatz_networks" rel="nofollow">Watts-Strogatz model</a> describes a mechanism of generating small-world networks.</p>

<p>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.</p>

<p>Is there a similar small-world model for <strong>bipartite</strong> 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)?</p>

CC BY-SA 3.0
2014-07-04T00:35:05.000Z
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.
a06e
CC BY-SA 3.0
2014-07-04T10:46:24.383Z
Sounds good to me. Did you try that? BTW, you might want to have a look at this proposal: http://area51.stackexchange.com/proposals/61500/network-science
Vincent Labatut
CC BY-SA 3.0
2014-07-08T20:32:20.493Z
[goldreich 1-way function](http://eccc.hpi-web.de/report/2012/175/) 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](http://en.wikipedia.org/wiki/Expander_graph) maybe have some overlap or relationship with either small world or scale free graphs for some parameters?
vzn
<graph-theory><network-modeling>
Bipartite small-world networks
a06e
# Bipartite small-world networks

(Asked by: username_0 on 2014-07-04)

The [Watts-Strogatz model](http://www.scholarpedia.org/article/Small-world_network#Watts-Strogatz_networks) 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)?

**Tags:** graph-theory, network-modeling
> **Comments:**
> **username_0**: 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.  
> **username_1**: Sounds good to me. Did you try that? BTW, you might want to have a look at this proposal: http://area51.stackexchange.com/proposals/61500/network-science  
> **username_2**: [goldreich 1-way function](http://eccc.hpi-web.de/report/2012/175/) 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](http://en.wikipedia.org/wiki/Expander_graph) maybe have some overlap or relationship with either small world or scale free graphs for some parameters?  

---

## 0 answers

