Topological Generalizations of network motifs

Abstract

Biological and technological networks contain patterns, termed network motifs, which occur far more often than in randomized networks. Network motifs were suggested to be elementary building blocks that carry out key functions in the network. It is of interest to understand how network motifs combine to form larger structures. To address this, we present a systematic approach to define 'motif generalizations': families of motifs of different sizes that share a common architectural theme. To define motif generalizations, we first define 'roles' in a subgraph according to structural equivalence. For example, the feedforward loop triad, a motif in transcription, neuronal and some electronic networks, has three roles, an input node, an output node and an internal node. The roles are used to define possible generalizations of the motif. The feedforward loop can have three simple generalizations, based on replicating each of the three roles and their connections. We present algorithms for efficiently detecting motif generalizations. We find that the transcription networks of bacteria and yeast display only one of the three generalizations, the multi-output feedforward generalization. In contrast, the neuronal network of \emph{C. elegans} mainly displays the multi-input generalization. Forward-logic electronic circuits display a multi-input, multi-output hybrid. Thus, networks which share a common motif can have very different generalizations of that motif. Using mathematical modelling, we describe the information processing functions of the different motif generalizations in transcription, neuronal and electronic networks.

References in corpus (2)

• The structure and function of complex networks
• Subgraphs in random networks

Cited by in corpus (22)

• Complex Networks as Hypergraphs
• The multilayer connectome of Caenorhabditis elegans
• Coarse-Graining and Self-Dissimilarity of Complex Networks
• Subgraphs and network motifs in geometric networks
• Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph Isomorphism
• Emergence of dynamic properties in network hyper-motifs
• Structure of n-clique networks embedded in a complex network
• Large-scale inference and graph theoretical analysis of gene-regulatory networks in B. stubtilis
• Cycle and flow trusses in directed networks
• Enrichment and aggregation of topological motifs are independent organizational principles of integrated interaction networks
• Authorship attribution via network motifs identification
• Graph animals, subgraph sampling and motif search in large networks
• Labelled network subgraphs reveal stylistic subtleties in written texts
• Subgraphs and motifs in a dynamic airline network
• Motif based hierarchical random graphs: structural properties and critical points of an Ising model
• Edge Balance Ratio: Power Law from Vertices to Edges in Directed Complex Network
• Generating random networks that consist of a single connected component with a given degree distribution
• Dynamical Properties of Interaction Data
• Fundamental Dynamic Units: Feedforward Networks and Adjustable Gates
• Effects of feedback and feedforward loops on dynamics of transcriptional regulatory model networks
• Analysing Motifs in Multilayer Networks
• Hoeffding-type decomposition for $U$-statistics on bipartite networks