Subgraphs and network motifs in geometric networks

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 datasets 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 3 and 4-node subgraphs, in both directed and non-directed geometric networks. We also analyze geometric networks with arbitrary degree sequences, and models with a field that biases 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.

9 pages, 6 figures

References in corpus (5)

• The statistical mechanics of networks
• Spatial Growth of Real-world Networks
• Topological Generalizations of network motifs
• Network Transitivity and Matrix Models
• Statistical mechanics of topological phase transitions in networks

Cited by in corpus (18)

• Community detection algorithms: a comparative analysis
• Structural Properties of the Caenorhabditis elegans Neuronal Network
• Complex Networks as Hypergraphs
• Network Analysis of Particles and Grains
• Analytical framework for recurrence-network analysis of time series
• Earthquake Phase Association with Graph Neural Networks
• Homogeneous complex networks
• Emergence of dynamic properties in network hyper-motifs
• Motif analysis in directed ordered networks and applications to food webs
• Generating random networks with given degree-degree correlations and degree-dependent clustering
• Network-based model of the growth of termite nests
• Subgraphs and motifs in a dynamic airline network
• Motif based hierarchical random graphs: structural properties and critical points of an Ising model
• Graph Theory and Networks in Biology
• Analysing Motifs in Multilayer Networks
• Hierarchical Random Graphs Based on Motifs
• A comparative study of ecological networks using spectral projections of normalized graph Laplacian
• Socioeconomic development and stability: A complex network blueprint