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 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](https://git.skewed.de/count0/graph-tool/issues/366).
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.
### 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](https://arxiv.org/pdf/1508.03533v3.pdf).
### 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.
1. Barabasi, Albert-Laszlo. "Motifs." Network Science course lecture slide (Fall 2016), [link](http://barabasilab.neu.edu/courses/phys5116/content/Motifs_2016.pdf).
### 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.