Subgraphs and network motifs in geometric networks
- 22 February 2005
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 71 (2) , 026117
- https://doi.org/10.1103/physreve.71.026117
Abstract
Many real-world networks describe systems in which interactions decay with the distance between nodes. Examples include systems constrained in real space such as transportation and communication networks, as well as systems constrained in abstract spaces such as multivariate biological or economic data sets and models of social networks. These networks often display network motifs: subgraphs that recur in the network much more often than in randomized networks. To understand the origin of the network motifs in these networks, it is important to study the subgraphs and network motifs that arise solely from geometric constraints. To address this, we analyze geometric network models, in which nodes are arranged on a lattice and edges are formed with a probability that decays with the distance between nodes. We present analytical solutions for the numbers of all three- and four-node subgraphs, in both directed and nondirected geometric networks. We also analyze geometric networks with arbitrary degree sequences and models with a bias for directed edges in one direction. Scaling rules for scaling of subgraph numbers with system size, lattice dimension, and interaction range are given. Several invariant measures are found, such as the ratio of feedback and feed-forward loops, which do not depend on system size, dimension, or connectivity function. We find that network motifs in many real-world networks, including social networks and neuronal networks, are not captured solely by these geometric models. This is in line with recent evidence that biological network motifs were selected as basic circuit elements with defined information-processing functions.Keywords
All Related Versions
This publication has 57 references indexed in Scilit:
- Topological generalizations of network motifsPhysical Review E, 2004
- Statistical mechanics of topological phase transitions in networksPhysical Review E, 2004
- Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifsBioinformatics, 2004
- Correlated Random NetworksPhysical Review Letters, 2002
- Negative Autoregulation Speeds the Response Times of Transcription NetworksJournal of Molecular Biology, 2002
- Network motifs in the transcriptional regulation network of Escherichia coliNature Genetics, 2002
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Resilience of the Internet to Random BreakdownsPhysical Review Letters, 2000
- The structure of the nervous system of the nematodeCaenorhabditis elegansPhilosophical Transactions of the Royal Society of London. B, Biological Sciences, 1986
- Structural balance: a generalization of Heider's theory.Psychological Review, 1956