In this paper the idea of a network motif is used to capture common patterns in a network. The authors note that metrics in the network theory literature, such as betweenness centrality take an aggregate look at the network and do not capture the dynamic nature of some networks, ie a network created by looking at the passes in a soccer game.

What the authors do is extract sequences of interactions of length 4, for example, if there is a link that goes: from node 1 to node 2 to node 3 and back to node 1, we have a motif defined as ABCA. Similarly for other interactions.

This is quite intuitive but what I am stuck on is when the authors note:

After having the motifs that are present in the network, we quantify the prevalence of the motifs by comparing the pass network of the team to random pass networks having the same properties (number of vertices and degree distribution). Specifically, we perturb the labels of the motifs prevalent in the original network randomly and as such we create pseudo motif distributions.

Now, I am not quite sure what the authors have done to generate the random pseudo networks. What I think they mean is that based on an empirical network, we have the degree distribution and the number of times each motif is achieved.

We then generate a random graph where the nodes have the same degrees, and compare how often these motifs pop up. However, in the literature there really isn't a way to generate random graphs in which the order of interactions is preserved. The authors say they 'perturb' the labels of the motifs but I'm not quite sure /what this means

I am just looking for a quick suggestion as to how to generate the pseudo distributions.


Although I haven't read the paper, it sounds like they are 'relabelling' existing graphs. That's probably what they mean by 'perturb' the labels. So, given a graph like:


where a bracket means a branch in the graph we could relabel it to:


and it would have the same connectivity and degree distribution.

That said, you can generate graphs at random with particular degree distributions. I'll try to put a reference to a method to do this in a little while.

  • $\begingroup$ I'm not quite sure how that would work in this case since the path ABCD describes A ->B, B ->C, C ->D, what does it mean to have (D) ? Also, I have tried to generate graphs using the igraph package in R, however, the order of interactions is not preserved and so it wasn't useful. $\endgroup$ – dimebucker Sep 27 '16 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.