Graph from motif distribution


I am quite new to the graph theory field. I studied the Newman 2010 book and I am now trying to deepen my understanding on motifs.

I would like to create a graph given a (3vertices) motif distribution to then perform statistical comparisons with real networks.
How can I do it with igraph-python?

More in detail, I have a distribution of the ratios between actual motifs count and those found in (100) Erdös-Rényi surrogates networks having the same degree sequence of the actual network. I would like to use such ratio distribution to create a graph.

I know how to generate a network with given edge distribution
(Generating graphs for given degree sequence in Python or R - Stack Overflow).

And I found how to generate an edge distribution such that it yields a given motif distribution
(Generating networks with a desired second order motif frequency - Math Insight).
But this description is for 2 edges motifs distributions.

Thanks for any help!

Welcome to the igraph forum! Would you mind changing your username (or at least your display name) to something more memorable? I think it creates a friendlier atmosphere if forum users can easily recognize each other and remember each others’ names.

As for the question: Generating unbiased random graphs with a given motif distribution is far from an easy problem. In fact, it is a research-level problem. The paper referenced by the blog post you linked does not appear to do it: it merely constraints “convergent” and “divergent” patterns, but this is a far cry from controlling the relative frequencies of all 16 possible directed 3-motifs. Another paper you may be interested in is this:

But this one will also not allow for unbiased sampling along with a full control of the motif distribution.

I have once formulated a workable exponential random graph model with all three-motifs constrained, but the fitting turned out to be extremely hard even for small graphs (which is why this is not published yet).

Thanks @szhorvat!
I believe that for the sake of the forum I will just choose your reply.
I imagined that the solution was both theoretically and computationally hard :frowning:

However, if I may, I would like to articulate a bit more…

If I understand correctly your comments on constraining patterns, you mean that even if one manages to control convergent and divergent patterns, the resulting network might not match a desired 3-motifs distribution, due to the way in which these ‘constrained’ patterns then are joined.

However, I am not sure I need unbiased random graphs.
I probably need to give more details that I left out previously to convey the question.

In fact, I work with networks where the nodes are placed on a grid. And my goal is to compare the statistics of networks generated using distance-dependent constrained edges against completely random.
We know that the cortex of rats displays a certain 3-motif distribution (Highly Nonrandom Features of Synaptic Connectivity in Local Cortical Circuits).
I am currently exploring the implications of the hypothesis that it is the distance-dependent connectivity that globally gives 3-motif distribution as the one observed in that paper.
In particular, I am now looking into ways to control the 3-motif distribution by changing the parameters of the distance-connectivity rule, which is an exponentially decaying function of the distance from each considered node: radius and amplitude.

I was discussing with a colleague the possibility of workarounds, maybe starting from an adjacency matrix that I know contains the desired 3-motif distribution and then altering it in order to come to a different adjacency matrix which still respect the same motif distribution. But I am not sure how…

If you want to test whether some property A (motif distribution) is a consequence of a property B (“distance dependence”), then you do not need to figure out how to generate random graphs with property A. What you need is random graphs with property B (a null model), then check if they also have property A. If yes, you can conclude that B leads to A.

If you have not seen it yet, take a look at:

It describes a specific exponential distance rule in the macaque cortex, and constructs a random graph model incorporating this distance rule. See how motif distributions are reproduced by this model in Fig 3BC. You can also look at my paper which does similar analyses in the mouse, as well as compares the macaque and mouse in the context of this distance rule:

See Figs 5-6 and S5.

In summary, if you are looking to see if motifs can be explained from the distance-dependence, then it is the distance-dependence that you need to incorporate into your null model, not the motifs distribution. Let me know if I misunderstood what you are trying to do.

I already assumed (without knowing these papers) that an EDR (I was actually using it based on data from Allen and Markram) governs the motif distribution.

To partially rectify your interpretation of my question (sorry, my bad), my goal is now to study how different lambda generate different motifs distributions.
And, if I understand correctly your reply, I just need to create different networks by systematically varying lambda and see. Basically it’s a way to add points in the middle between your EDR and CDR. My expectation is that different lambdas will result in different motifs distributions.

1 Like