Network Motifs

What are network motifs?

Network motif can be seen as a subgraph pattern of a complex network (Milo 2002). For example, in a citation network, if we consider three adjacent nodes, we can find the patterns where two nodes point to the other one or one nodes points to the other two quite frequently. In biology system studies, researchers care about such statistically significant motifs. Systems such as gene transcription network or ecological food web exhibits a significant motifs count (for some motifs) compared to a random network with the same number nodes and links (Milo 2002). The correlation (and whether it is causation) of a statistical significant motif and the fucntionality of the network is an active area of research. It’s worth to mention that a motif usually contains 3 to 5 nodes in most studies.

Being extensively studied in biology, network motif is assumed to be the result of a biological system’s functionality (ref Milo, Alon). Recently, network motifs are also considered into social network and graph-structured data analysis (ref Leskovec). With the same assumption as in previous researches, the community structure of a complex network (or graph-structured data) is assumed to be the result of some underlying mesoscopic scale interaction between nodes. Personally, I am very excited about this approach. As mentioned in (Milo 2002), the motifs can be the building blocks for complex systems and understanding network motifs may show us insightful information about the complex systems.

mesoscopic? While microscopic analysis considers node properties and pair-wise interations and macroscopic gives us the overall quantitative view, mesoscopic analysis studies the network structures on an intermediate scale (subgraphs, motifs interactions). (Barabasi 2016)

Motif metrics

With the motif scheme in mind, the very first thing we want to know is given a motif (one of the figure below), how can we tell this motif is significant?. One approach to this problem is to compare the motif count between the given network and a random network of the same order (same number of nodes). I wonder which type of motif statistic or random network is the best for comparision…

z-score

z-score measures the different between the number of a motif type found in the network we need to analyse and the mean number of that motif in random networks of the same order (i.e. number of nodes and edges). The tool I used for graph motif analysis is a Python package called graph-tool. Since motif analysis is a demanding task, running undirected-size-4 motif z-score on Blogcatalog3 (~300k edges) takes almost 2 weeks on my lab machine (single thread). However, there is a trick to force graph-tool to use multiple-cores processing mentioned here.

The selection of the graph random-rewire algorithm is also an open question in complex network research. In my work, I settle with the configuration model for random graph generation. However, other random graph models such as block model could be better for a certain type of motif. Professor Barabasi also mentioned about this matter in his slide (Barabasi 2016). graph-tool also provides the implementations of some popular random graph rewiring functions.

References

Network motifs in biological systems

1. Milo, Ron, et al. “Network motifs: simple building blocks of complex networks.” Science 298.5594 (2002): 824-827.
2. Milo, Ron, et al. “Superfamilies of evolved and designed networks.” Science 303.5663 (2004): 1538-1542.
3. Alon, Uri. “Network motifs: theory and experimental approaches.” Nature Reviews Genetics 8.6 (2007): 450-461.
4. Mangan, Shmoolik, et al. “The incoherent feed-forward loop accelerates the response-time of the gal system of Escherichia coli.” Journal of molecular biology 356.5 (2006): 1073-1081,
5. Lee, Tong Ihn, et al. “Transcriptional regulatory networks in Saccharomyces cerevisiae.” Science 298.5594 (2002): 799-804.
6. Wuchty, Stephan, Zoltán N. Oltvai, and Albert-László Barabási. “Evolutionary conservation of motif constituents in the yeast protein interaction network.” Nature genetics 35.2 (2003): 176-179,
7. Conant, Gavin C., and Andreas Wagner. “Convergent evolution of gene circuits.” Nature genetics 34.3 (2003): 264-266.
8. Sporns, Olaf, and Rolf Kötter. “Motifs in brain networks.” PLoS Biol 2.11 (2004): e369,
9. Alon, Uri. An introduction to systems biology: design principles of biological circuits. CRC press, 2006.
10. van den Heuvel, Martijn P., et al. “High-cost, high-capacity backbone for global brain communication.” Proceedings of the National Academy of Sciences 109.28 (2012): 11372-11377.

Network motifs in sociological systems

1. Saracco, Fabio, et al. “Detecting early signs of the 2007-2008 crisis in the world trade.”. arXix (2015), link.

Network motifs in computational graph theory

1. Wong, Elisabeth, et al. “Biological network motif detection: principles and practice.” Briefings in bioinformatics (2011): bbr033.
2. Benson, Austin R., David F. Gleich, and Jure Leskovec. “Higher-order organization of complex networks.” Science 353.6295 (2016): 163-166.

Lectures

1. Barabasi, Albert-Laszlo. “Motifs.” Network Science course lecture slide (Fall 2016), link.

Software and datasets

1. Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX”, in Proceedings of the 7th Python in Science Conference (SciPy2008), Gäel Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008.
2. Shannon, Paul, et al. “Cytoscape: a software environment for integrated models of biomolecular interaction networks.” Genome Research 13.11 (2003): 2498-2504.