The topological relationship between the large-scale attributes and local interaction patterns of complex networks

By A. Vázquez, Radu Dobrin, Danilo Sergi, Jean-Pierre Eckmann, Zoltn Oltvai, Albert-László Barabási. Proceedings of the National Academy of Sciences of the United States of America, 2004

315 citations recorded by the source corpus.

Recent evidence indicates that the abundance of recurring elementary interaction patterns in complex networks, often called subgraphs or motifs, carry significant information about their function and overall organization. Yet, the underlying reasons for the variable quantity of different subgraph types, their propensity to form clusters, and their relationship with the networks' global organization remain poorly understood. Here we show that a network's large-scale topological organization and its local subgraph structure mutually define and predict each other, as confirmed by direct measurements in five well studied cellular networks. We also demonstrate the inherent existence of two distinct classes of subgraphs, and show that, in contrast to the low-density type II subgraphs, the highly abundant type I subgraphs cannot exist in isolation but must naturally aggregate into subgraph clusters. The identified topological framework may have important implications for our understanding of the origin and function of subgraphs in all complex networks.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/c7d71a02b3d3f042f4e1fc7575e0f56bd5e5612c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Biological network comparison using graphlet degree distribution (2007, unknown): “Statistical and theoretical properties of these networks have been extensively studied (15; 20; 30; 22; 36; 41; 27; 34) due to their important biological implications (14; 17).”
Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking (2007, background): “Although motif clustering has previously been observed [3] and demonstrated analytically [24], previous motifs studied do not have enough nodes to exhibit the extreme combinatorial clustering we observed for large subgraphs (at least 15 nodes).”
Graph theory and networks in Biology. (2006, background): “However, the validity of the null model described here needs to be considered carefully in the light of the findings presented in [152].”
Evidence for the existence of a robust pattern of prey selection in food webs (2007, background): “Past studies of network motifs have uncovered relevant subgraphs within a variety of empirical networks (Milo et al. 2002, 2004), be they biological, technological, and social, or model networks (Artzy-Randrup et al. 2004; Vázquez et al. 2004; Middendorf et al. 2005).”
Superfamily phenomena and motifs of networks induced from time series (2008, background): “Actually, mounting evidence suggests that there might be strong ties between the global topological properties and key local patterns of networks (9).”