Compression-based inference of network motif sets

Abstract

Physical and functional constraints on biological networks lead to complex topological patterns across multiple scales in their organization. A particular type of higher-order network feature that has received considerable interest is network motifs, defined as statistically regular subgraphs. These may implement fundamental logical and computational circuits and are referred as "building blocks of complex networks". Their well-defined structures and small sizes also enables the testing of their functions in synthetic and natural biological experiments. The statistical inference of network motifs is however fraught with difficulties, from defining and sampling the right null model to accounting for the large number of possible motifs and their potential correlations in statistical testing. Here we develop a framework for motif mining based on lossless network compression using subgraph contractions. The minimum description length principle allows us to select the most significant set of motifs as well as other prominent network features in terms of their combined compression of the network. The approach inherently accounts for multiple testing and correlations between subgraphs and does not rely on a priori specification of an appropriate null model. This provides an alternative definition of motif significance which guarantees more robust statistical inference. Our approach overcomes the common problems in classic testing-based motif analysis. We apply our methodology to perform comparative connectomics by evaluating the compressibility and the circuit motifs of a range of synaptic-resolution neural connectomes.

Published in PLoS Computational Biology: Methods

References in corpus (30)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Modularity and community structure in networks
• Epidemic spreading in scale-free networks
• Epidemic processes in complex networks
• Resilience of the Internet to random breakdowns
• Networks beyond pairwise interactions: structure and dynamics
• Intensity and coherence of motifs in weighted complex networks
• Biological network comparison using graphlet degree distribution
• Motifs in Temporal Networks
• The Statistical Physics of Real-World Networks
• Temporal motifs in time-dependent networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Network Geometry
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Multilayer motif analysis of brain networks
• Quantifying randomness in real networks
• Higher-order motif analysis in hypergraphs
• Reciprocity of weighted networks
• Scale-free networks with an exponent less than two
• Hypergraph Motifs: Concepts, Algorithms, and Discoveries
• Graph Summarization Methods and Applications: A Survey
• Compensating for population sampling in simulations of epidemic spread on temporal contact networks
• Randomized reference models for temporal networks
• Minimum Description Length Revisited
• Symmetry group factorization reveals the structure-function relation in the neural connectome of Caenorhabditis elegans
• Large-scale network motif analysis using compression
• Network motifs come in sets: correlations in the randomization process
• Subgraph covers -- An information theoretic approach to motif analysis in networks
• Atomic subgraphs and the statistical mechanics of networks