Algorithms for creating a directed network with a given 3-node motifs distribution

Question

I am looking for algorithms to create directed networks with an arbitrary distribution of 3-node network motifs (i.e. subgraphs of the order 3), see this picture from O. Sporns, R. Kotter, Motifs in Brain Networks, (2004).

It should work in a reasonable time for up to 10,000 nodes with total graph density of $p=0.1$ (probability of every connection + no self-connectivity). Of course, some distributions are impossible because motifs in the network overlap with each other. Thus, it should work for distributions relatively close to a random-network distribution (let's say, it should give a result for input motif numbers of $50-200\%$ of mean numbers in random networks).

Answer 1

As I understand, you are interested in an approximate solution. I have two heuristic ideas, maybe they can serve as a starting point.

However, if you want more (e.g. randomness in the Haar-measure sense or fixing other properties (graph diameter, spectrum, number of connected components, ...)) they are not sufficient.

Rewiring

Especially when you want to have distributions of network motifs close to a 'random' one.

• Generate a graph with desired distribution of in-degrees and out-degrees.
• For each pair of nodes $(x,y)$ calculate the number of each motif $m_i(x,y)$
• Now, in each step:
  • Randomly draw two edges.
  • Perform rewiring (i.e. $(a\rightarrow b, c \rightarrow d) \mapsto (a\rightarrow d, c \rightarrow b) $) if it is possible and if it results in distribution of motifs closer to the desired one (e.g. in the sense of the Kullback-Leibler divergence or perhaps the Euclidian distance). Modify $4\times13$ affected $m_i(x,y)$.

As variance is of order $\sqrt{n}$, each rewiring takes a fixed time, you need roughly $n^3/\sqrt{n}$ steps, so I guess that it should scale as $O(n^{2.5})$.

Addition

Alternatively, you can try to add edges to an empty graph in such way it produces the desired distribution. Also, one need to hold $m_i(x,y)$.

For each step one randomly draws a pair of nodes and put an edge if it results in a desired distribution at this step (perhaps with some randomness).

Then the time cost is $O(n^2)$ (or rather $O(\#\text{edges})$ ), so better by $\sqrt{n}$ than the rewiring.

The tricky part is to calculate the desired distribution at each step (or rather - at each edge count). For example, even if one wants to have only $(\bullet\leftrightarrows \bullet\quad \bullet)$ and $(\bullet\quad \bullet\quad \bullet)$ 3-motifs, then when starting one needs to create mostly $(\bullet\rightarrow \bullet\quad \bullet)$ 3-motifs.

I would guess that the desired distribution at a given edge count $E$ is the one resulting from the final motif distribution with removed edges with the probability $1-\frac{E}{E_{final}}$.

Answer 2

Adding to Piotr's answer: I would do the random rewiring suggested by Piotr, but in a simulated annealing way, rather than only doing swaps when it gets you closer to the desired 3-motif distribution [1, 2]. I have had some success using this approach to take a given graph and then generate random graphs with the same degree and 3-motif distribution. The simulated annealing can take some time, but should be reasonable on the graph sizes you mentioned.

On the other hand, I have no experience with how well it would work if you have a target 3-motif distribution and you start from a random graph. But perhaps starting from a graph built from something like Piotr's "Addition" suggestion would work better.

Note that for 4-node motifs this approach seems to get stuck in local optima [2].

[1] Priya Mahadevan, Dmitri Krioukov, Kevin Fall, and Amin Vahdat, Systematic topology analysis and generation using degree correlations, ACM SIGCOMM (2006).

[2] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, Network motifs: simple building blocks of complex networks, Science 298 (2002), no. 5594, 824–827.