Detecting local network motifs. (English) Zbl 1281.05124

Summary: Studying the structure of so-called real networks, that is networks obtained from sociological or biological data for instance, has become a major field of interest in the last decade. One way to deal with it is to consider that networks are partially built from small functional units called motifs, which can be found by looking for small subgraphs whose numbers of occurrences in the whole network are surprisingly high. In this article, we propose to define motifs through a local over-representation in the network and develop a statistic to detect them without relying on simulations. We then illustrate the performance of our procedure on simulated and real data, recovering already known biologically relevant motifs. Moreover, we explain how our method gives some information about the respective roles of the vertices in a motif.


05C82 Small world graphs, complex networks (graph-theoretic aspects)
62P10 Applications of statistics to biology and medical sciences; meta analysis
05C90 Applications of graph theory
Full Text: DOI arXiv Euclid


[1] Airoldi, E., Blei, D., Fienberg, S. and Xing, E. (2008). Mixed membership stochastic blockmodels., Journal of Machine Learning Research 9 1981-2014. · Zbl 1225.68143
[2] Alon, U. (2007). Network motifs: theory and experimental approaches., Nature Reviews Genetics 8 450-461.
[3] Artzy-Randrup, Y., Fleishman, S. J., Ben-Tal, N. and Stone, L. (2004). Comment on “Network Motifs: Simple Building Blocks of Complex Networks” and “Superfamilies of Evolved and Designed Networks”., Science 305 .
[4] Banks, E., Nabieva, E., Chazelle, B. and Singh, M. (2008). Organization of Physical Interactomes as Uncovered by Network Schemas., PLoS Comput. Biol. 4 e1000203.
[5] Barbour, A. D., Holst, L. and Janson, S. (1992)., Poisson approximation . Oxford University Press. · Zbl 0746.60002
[6] Berg, J. and Lässig, M. (2004). Local graph alignment and motif search in biological networks., Proc. Nat. Acad. Sci. 101 14689-14694.
[7] Boucheron, S., Lugosi, G. and Massart, P. (2003). Concentration inequalities using the entropy method., Ann. Probab. 31 1583-1614. · Zbl 1051.60020
[8] Chen, L. H. Y. (1975). Poisson approximation for dependant trials., Ann. Probab. 3 534-545. · Zbl 0335.60016
[9] Chung, F. and Lu, L. (2006)., Complex Graphs and Networks (CBMS Regional Conference Series in Mathematics) . AMS. · Zbl 1114.90071
[10] Daudin, J. J., Picard, F. and Robin, S. (2008). Mixture model for random graphs., Stat. Comput. 18 173-183.
[11] Dobrin, R., Beg, Q. K., Barabási, A. L. and Oltvai, Z. N. (2004). Aggregation of topological motifs in, Escherischia Coli transcriptional regulatory network. BMC Bioinformatics 5 10.
[12] Erdős, P. and Rényi, A. (1959). On random graphs I., Publ. Math. Debrecen 6 290-297. · Zbl 0092.15705
[13] Hofman, J. and Wiggins, C. (2008). Bayesian approach to network modularity., Phys. Rev. Lett. 100 .
[14] Holland, P. W. and Leinhardt, S. (1970). A method for detecting structure in sociometric data., American Journal of Sociology 76 492-513.
[15] Hunter, D. and Handcock, M. (2006). Inference of curved exponential family models for networks., Journal of Computational and Graphical Statistics 15 565-583.
[16] Janson, S. (1990). A functional limit theorem for random graphs with applications to subgraph count statistics., Random structures & Algorithms 1 15-37. · Zbl 0708.05052
[17] Janson, S., Oleskiewicz, K. and Rucinski, A. (2004). Upper tails for subgraph counts in random graphs., Israel Journal of Mathematics 142 61-92. · Zbl 1055.05136
[18] Kashani, Z. R. M., Ahrabian, H., Elahi, E., Nowzari-Dalini, A., Ansari, E. S., Asadi, S., Mohammadi, S., Schreiber, F. and Masoudi-Nejad, A. (2009). Kavosh: a new algorithm for finding network motifs., BMC Bioinformatics 10 .
[19] Kashtan, N., Itzkovitz, S., Milo, R. and Alon, U. (2004). Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs., Bioinformatics 20-11 1746.
[20] Latouche, P., Birmelé, E. and Ambroise, C. (2008). Bayesian methods for graph clustering., SSB preprint 17.
[21] Latouche, P., Birmelé, E. and Ambroise, C. (2011). Overlapping Stochastic Block Models with Application to the French Political Blogosphere., Ann. Appl. Stat. 5 309-336. · Zbl 1220.62083
[22] Matias, C., Schbath, S., Birmelé, E., Daudin, J. J. and Robin, S. (2006). Network motifs: mean and variance for the count., REVSTAT 4 31-51. · Zbl 1158.62346
[23] McDiarmid, C. (1998). Concentration. In, Probabilistic Methods for Algorithmic Discrete Mathematics (J. R.-A. M. Habib C. McDiarmid and B. Reed, eds.) 195-248. Springer. · Zbl 0927.60027
[24] Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D. and Alon, U. (2002). Network Motifs: Simple Building Blocks of Complex Networks., Science 298 824-827.
[25] Nowicki, K. and Snijders, T. A. B. (2001). Estimation and prediction for stochastic block-structures., JASA 96 1077-87. · Zbl 1072.62542
[26] Picard, F., Daudin, J. J., Koskas, M., Schbath, S. and Robin, S. (2008). Assessing the exceptionality of network motifs., J. Comput. Biol. 15 1-20.
[27] Picard, F., Miele, V., Daudin, J. J., Cottret, L. and Robin, S. (2009). Deciphering the connectivity structure of biological networks using MixNet., BMC Bioinformatics 10 1-11.
[28] Schreiber, F. and Schwöbermeyer, H. (2005). MAVisto: a tool for the exploration of network motifs., Bioinformatics 21 3572-3574.
[29] Wasserman, S. and Faust, K. (1994)., Social network analysis: methods and applications . Cambridge University Press. · Zbl 0926.91066
[30] Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of small-world networks., Nature 393 440-442. · Zbl 1368.05139
[31] Wernicke, S. (2005). Efficient detection of network motifs., IEEE/ACM Transactions on Computational Biology and Bioinformatics 3(4) 347-359.
[32] Wernicke, S. and Rasche, F. (2006). FANMOD: a tool for fast network motif detection., Bioinformatics 22 1152-1153.
[33] White, H. C., Boorman, S. A. and Breiger, R. L. (1976). Social structure from multiple networks I: Blockmodels of roles and positions., American Journal of Sociology 81 730-779.
[34] Zanghi, H., Ambroise, C. and Miele, V. (2008). Fast online graph clustering via Erdős-Rényi mixture., Pattern Recognition 41 3592-3599. · Zbl 1151.68623
[35] Zhang, L. V., King, O. D., Wong, S. L., Goldberg, D. S., Tong, A. H., Lesage, G., Andrews, B., Bussey, H., Boone, C. and Roth, F. P. (2005). Motifs, themes and thematic maps of an integrated Saccharomyces Cerevisiae interaction network., J. Biol. 4 .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.