Summary: Subgraphs and network motifs in geometric networks
Shalev Itzkovitz and Uri Alon
Departments of Molecular Cell Biology and Physics of Complex Systems, Weizmann Institute of Science, Rehovot, Israel 76100
Received 7 September 2004; published 22 February 2005
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.