<p>Adding to Piotr's answer: I would do the random rewiring suggested by Piotr, but in a <b>simulated annealing</b> 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. </p>

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

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

<p>[1] Priya Mahadevan, Dmitri Krioukov, Kevin Fall, and Amin Vahdat, <a href="http://arxiv.org/abs/cs/0605007" rel="nofollow">Systematic topology analysis and generation using degree correlations</a>, ACM
SIGCOMM (2006).</p>

<p>[2] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon,
<a href="http://www.sciencemag.org/content/298/5594/824.full" rel="nofollow">Network motifs: simple building blocks of complex networks</a>, Science
298 (2002), no. 5594, 824–827.</p>

CC BY-SA 3.0
2012-05-14T13:33:45.357Z
This is a very good suggestion, however I tried annealing for Monte Carlo search and unfortunately I couldn't get better than 500 nodes. The time cost grew exponentially, starting from <1s for 50 nodes, and reaching more than 1.5h for 500 nodes, so I have no clue of how to reach 10,000 nodes this way. My intuition is that starting from something more or less in between random network and what we want wouldn't improve time expenditure much because it is way harder to proceed since we already are halfway than from the beginning...
user9324
CC BY-SA 3.0
2012-05-15T23:00:32.440Z
@user9324 I have definitely done this for networks of ~1500 nodes in less time than that (though it's hard to compare since we haven't mentioned the computers these were run on). If you want you can contact me by email and maybe we can see if there is some slight change in the implementation that would yield an improvement.
Joshua Grochow
CC BY-SA 3.0
2012-05-08T16:47:13.450Z
2012-05-08T16:47:13.450Z
Joshua Grochow
<p>As I understand, you are interested in an approximate solution. I have two heuristic ideas, maybe they can serve as a starting point.</p>

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

<h2>Rewiring</h2>

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

<ul>
<li>Generate a graph with desired distribution of in-degrees and out-degrees.</li>
<li>For each pair of nodes $(x,y)$ calculate the number of each motif $m_i(x,y)$</li>
<li>Now, in each step:
<ul>
<li>Randomly draw two edges.</li>
<li>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 <a href="http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence" rel="nofollow">Kullback-Leibler divergence</a> or perhaps the Euclidian distance). Modify $4\times13$ affected $m_i(x,y)$.</li>
</ul></li>
</ul>

<p>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})$.</p>

<h2>Addition</h2>

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

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

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

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

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

CC BY-SA 3.0
2012-05-07T13:57:40.070Z
2012-05-07T15:43:24.870Z
2012-05-07T15:43:24.870Z
Piotr Migdal
<p>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 <a href="http://www.plosbiology.org/article/slideshow.action?uri=info%3adoi/10.1371/journal.pbio.0020369&amp;imageURI=info%3adoi/10.1371/journal.pbio.0020369.g001" rel="nofollow">this picture</a> from <a href="http://dx.doi.org/10.1371/journal.pbio.0020369" rel="nofollow">O. Sporns, R. Kotter, Motifs in Brain Networks, (2004)</a>.</p>

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

<ds.algorithms><graph-theory><graph-algorithms><planar-graphs><network-modeling>
Algorithms for creating a directed network with a given 3-node motifs distribution
user9324
# Algorithms for creating a directed network with a given 3-node motifs distribution

(Asked by: username_0 on 2012-05-05)

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](http://www.plosbiology.org/article/slideshow.action?uri=info%3adoi/10.1371/journal.pbio.0020369&imageURI=info%3adoi/10.1371/journal.pbio.0020369.g001) from [O. Sporns, R. Kotter, Motifs in Brain Networks, (2004)](http://dx.doi.org/10.1371/journal.pbio.0020369).

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).

**Tags:** ds.algorithms, graph-theory, graph-algorithms, planar-graphs, network-modeling

---

## 2 answers

### Answer by username_1 on 2012-05-08. Score: 3

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](http://arxiv.org/abs/cs/0605007), 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](http://www.sciencemag.org/content/298/5594/824.full), Science
298 (2002), no. 5594, 824–827.

> **Comments:**
> **username_0**: This is a very good suggestion, however I tried annealing for Monte Carlo search and unfortunately I couldn't get better than 500 nodes. The time cost grew exponentially, starting from <1s for 50 nodes, and reaching more than 1.5h for 500 nodes, so I have no clue of how to reach 10,000 nodes this way. My intuition is that starting from something more or less in between random network and what we want wouldn't improve time expenditure much because it is way harder to proceed since we already are halfway than from the beginning...  
> **username_1**: @user9324 I have definitely done this for networks of ~1500 nodes in less time than that (though it's hard to compare since we haven't mentioned the computers these were run on). If you want you can contact me by email and maybe we can see if there is some slight change in the implementation that would yield an improvement.  

---

### Answer by username_2 on 2012-05-07. Score: 3

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](http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_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}}$.


---

