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

Abstract

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.

paper

References in corpus (12)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Lethality and centrality in protein networks
• Hierarchical organization of modularity in metabolic networks
• The large-scale organization of metabolic networks
• Pseudofractal Scale-free Web
• Curvature of Co-Links Uncovers Hidden Thematic Layers in the World Wide Web
• Subgraphs in random networks
• Optimization of Robustness of Complex Networks
• Number of loops of size h in growing scale-free networks
• On the Tomography of Networks and Multicast Trees

Cited by in corpus (56)

• Biological network comparison using graphlet degree distribution
• Communicability in complex networks
• Clique percolation in random networks
• Motifs in Temporal Networks
• Topological strata of weighted complex networks
• The Dynamics of a Mobile Phone Network
• Quantifying randomness in real networks
• Clustering in complex networks. I. General formalism
• Tuning clustering in random networks with arbitrary degree distributions
• Evolving Clustered Random Networks
• Emergence of large cliques in random scale-free network
• Loops of any size and Hamilton cycles in random scale-free networks
• Multiscale Topological Properties Of Functional Brain Networks During Motor Imagery After Stroke
• Synchronization Properties of Network Motifs
• Functional architecture of Escherichia coli: new insights provided by a natural decomposition approach
• Number of cliques in random scale-free network ensembles
• Using graph concepts to understand the organization of complex systems
• Partial Synchronization and Partial Amplitude Death in Mesoscale Network Motifs
• The critical point of k-clique percolation in the Erdos-Renyi graph
• Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph Isomorphism
• Effect of degree correlations on the loop structure of scale-free networks
• Meta-validation of bipartite network projections
• The inhomogeneous evolution of subgraphs and cycles in complex networks
• Empirical study on clique-degree distribution of networks
• Dynamics and Processing in Finite Self-Similar Networks
• Interfaces and the edge percolation map of random directed networks
• Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs
• Structure of n-clique networks embedded in a complex network
• Spontaneous Self-Assembly of Transcription Factor Based Gene Regulation Networks
• Large-scale inference and graph theoretical analysis of gene-regulatory networks in B. stubtilis
• Organization of networks with tagged nodes and biased links: a priori distinct communities. The case of Intelligent Design Proponents and Darwinian Evolution Defenders
• Enrichment and aggregation of topological motifs are independent organizational principles of integrated interaction networks
• Time-Varying Networks: Recovering Temporally Rewiring Genetic Networks During the Life Cycle of Drosophila melanogaster
• Graph animals, subgraph sampling and motif search in large networks
• Fluctuations analysis in complex networks modeled by hidden variable models. Necessity of a large cut-off in hidden-variable models
• Percolation and Loop Statistics in Complex Networks
• Weighted hypersoft configuration model
• Optimizing and controlling functions of complex networks by manipulating rich-club connections
• Representing perturbed dynamics in biological network models
• Random graph model with power-law distributed triangle subgraphs
• Topological Complexity of Frictional Interfaces: Friction Networks
• Predicting Multi-actor collaborations using Hypergraphs
• Emergence of Long-Range Correlations in Random Networks
• Content based network model with duplication and divergence
• Analytic solutions for links and triangles distributions in finite Barabási-Albert networks
• Fluctuations of motifs and non self-averaging in complex networks. A self- vs non-self-averaging phase transition scenario
• Information content based model for the topological properties of the gene regulatory network of Escherichia coli
• Evolving complex networks with conserved clique distributions
• The Atlas for the Aspiring Network Scientist
• Impact of observational incompleteness on the structural properties of protein interaction networks
• Complex Network-Based Approach for Feature Extraction and Classification of Musical Genres
• Relaxation dynamics of maximally clustered networks
• Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering
• Efficient Mining of Frequent Subgraphs with Two-Vertex Exploration
• Analysis of Triplet Motifs in Biological Signed Oriented Graphs Suggests a Relationship Between Fine Topology and Function
• Network Subgraphs of the heterogeneous Chinese credit system