<p>You could apply the principle of the Configuration Model <a href="http://ms.mcmaster.ca/tom/Research%20Papers/MollReed95.pdf" rel="nofollow">(Molloy &amp; Reed'95)</a> to bipartite graphs. It allows generating a network possessing any predefined degree distribution. In the original version, you first generate a set of "stubs", where each node is repeated as many times as its targeted degree (i.e. a node whose degree should be 5 will appear as 5 distinct stubs). Then, you randomly draw pairs of stubs, and connect the corresponding nodes in your graph. See <a href="http://mathinsight.org/generating_networks_desired_degree_distribution" rel="nofollow">this page</a> for additional details.</p>

<p>In the case of a bipartite network, you could do the same thing, but using two distinct sets of stubs (corresponding to both types of nodes). The pairs you draw should be constituted of one stub from each set.</p>

<p>If you want to keep the growth property of the model, you could also directly modify the Barabasi-Albert model you mention, by adding two extra constraints. First, alternate the type of the inserted nodes (I mean: once a node of the first type, then a node of the second type, then another node of the first type, and so on). Second, connect it only to nodes of the other type, using the preferential attachment principle.</p>

<p><em>Edit</em>: you might be interested by the Networkx library, cf. the <em>Bipartite</em> section in <a href="https://networkx.github.io/documentation/latest/reference/generators.html" rel="nofollow">this page</a>.</p>

CC BY-SA 3.0
2014-07-04T10:35:36.883Z
2014-07-04T10:43:57.177Z
2014-07-04T10:43:57.177Z
Vincent Labatut
<p>The <a href="http://www.scholarpedia.org/article/Scale-free_networks#The_Barabasi-Albert_model" rel="nofollow">Barabasi-Albert</a> model describes a mechanism of generating random scale-free networks:</p>

<ol>
<li>Growth: Starting with a small number ($m_0$) of connected nodes, at every time step, we add a new node with $m$ ($&lt;m0$) edges that link the new node to $m$ different nodes already present in the network. </li>
<li>Preferential attachment: When choosing the nodes to which the new node connects, we assume that the probability $P$ that a new node will be connected to node $i$ depends on the degree $k_i$ of node $i$, such that </li>
</ol>

<p>$$P\propto \frac{k_i}{\sum_i k_i}$$</p>

<p>Is there a similar model for scale-free <strong>bipartite</strong> networks? That is, is there a mechanism for generating random bipartite graphs that possess the usual properties of scale-free networks?</p>

CC BY-SA 3.0
2014-07-04T00:34:30.737Z
related: http://cstheory.stackexchange.com/q/25129/5982
a06e
<graph-theory><network-modeling>
Bipartite scale-free networks
a06e
# Bipartite scale-free networks

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

The [Barabasi-Albert](http://www.scholarpedia.org/article/Scale-free_networks#The_Barabasi-Albert_model) model describes a mechanism of generating random scale-free networks:

1. Growth: Starting with a small number ($m\_0$) of connected nodes, at every time step, we add a new node with $m$ ($- Preferential attachment: When choosing the nodes to which the new node connects, we assume that the probability $P$ that a new node will be connected to node $i$ depends on the degree $k\_i$ of node $i$, such that

$$P\propto \frac{k\_i}{\sum\_i k\_i}$$

Is there a similar model for scale-free **bipartite** networks? That is, is there a mechanism for generating random bipartite graphs that possess the usual properties of scale-free networks?

**Tags:** graph-theory, network-modeling
> **Comments:**
> **username_0**: related: http://cstheory.stackexchange.com/q/25129/5982  

---

## 1 answers

### Answer by username_1 on 2014-07-04. Score: 2

You could apply the principle of the Configuration Model [(Molloy & Reed'95)](http://ms.mcmaster.ca/tom/Research%20Papers/MollReed95.pdf) to bipartite graphs. It allows generating a network possessing any predefined degree distribution. In the original version, you first generate a set of "stubs", where each node is repeated as many times as its targeted degree (i.e. a node whose degree should be 5 will appear as 5 distinct stubs). Then, you randomly draw pairs of stubs, and connect the corresponding nodes in your graph. See [this page](http://mathinsight.org/generating_networks_desired_degree_distribution) for additional details.

In the case of a bipartite network, you could do the same thing, but using two distinct sets of stubs (corresponding to both types of nodes). The pairs you draw should be constituted of one stub from each set.

If you want to keep the growth property of the model, you could also directly modify the Barabasi-Albert model you mention, by adding two extra constraints. First, alternate the type of the inserted nodes (I mean: once a node of the first type, then a node of the second type, then another node of the first type, and so on). Second, connect it only to nodes of the other type, using the preferential attachment principle.

*Edit*: you might be interested by the Networkx library, cf. the *Bipartite* section in [this page](https://networkx.github.io/documentation/latest/reference/generators.html).


---

