Coarse-Graining and Self-Dissimilarity of Complex Networks

Abstract

Can complex engineered and biological networks be coarse-grained into smaller and more understandable versions in which each node represents an entire pattern in the original network? To address this, we define coarse-graining units (CGU) as connectivity patterns which can serve as the nodes of a coarse-grained network, and present algorithms to detect them. We use this approach to systematically reverse-engineer electronic circuits, forming understandable high-level maps from incomprehensible transistor wiring: first, a coarse-grained version in which each node is a gate made of several transistors is established. Then, the coarse-grained network is itself coarse-grained, resulting in a high-level blueprint in which each node is a circuit-module made of multiple gates. We apply our approach also to a mammalian protein-signaling network, to find a simplified coarse-grained network with three main signaling channels that correspond to cross-interacting MAP-kinase cascades. We find that both biological and electronic networks are 'self-dissimilar', with different network motifs found at each level. The present approach can be used to simplify a wide variety of directed and nondirected, natural and designed networks.

11 pages, 11 figures

References in corpus (8)

• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Hierarchical organization of modularity in metabolic networks
• Specificity and stability in topology of protein networks
• Distance, dissimilarity index, and network community structure
• Local graph alignment and motif search in biological networks
• Subgraphs in random networks
• Topological Generalizations of network motifs

Cited by in corpus (22)

• Community detection in graphs
• Extracting the multiscale backbone of complex weighted networks
• Extracting the hierarchical organization of complex systems
• Self-similar scaling of density in complex real-world networks
• Information filtering in complex weighted networks
• Functions of Bifans in Context of Multiple Regulatory Motifs in Signaling Networks
• Emergence of dynamic properties in network hyper-motifs
• Large deviations theory for noisy non-linear electronics: CMOS inverter as a case study
• Dynamics and Processing in Finite Self-Similar Networks
• Multiscale Network Generation
• Network Motifs in Object-Oriented Software Systems
• Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts
• Optimal high-level descriptions of dynamical systems
• Moss: A Scalable Tool for Efficiently Sampling and Counting 4- and 5-Node Graphlets
• Network Renormalization
• Multiscale network renormalization: scale-invariance without geometry
• Minfer: Inferring Motif Statistics From Sampled Edges
• Detecting the optimal number of communities in complex networks
• Subgraphs and motifs in a dynamic airline network
• Functional brain networks: great expectations, hard times, and the big leap forward
• Global decomposition of networks into multiple cores formed by local hubs
• Efficiently Estimating Motif Statistics of Large Networks