Bipartite scale-free networks

Question

The Barabasi-Albert 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$ ($<m0$) edges that link the new node to $m$ different nodes already present in the network.
2. 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?

Answer 1

You could apply the principle of the Configuration Model (Molloy & Reed'95) 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 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.