Coarse-graining and self-dissimilarity of complex networks

• Published in: Physical review. E, Statistical, nonlinear, and soft matter physics Statistical, nonlinear, and soft matter physics, 2005-01, Vol.71 (1 Pt 2), p.016127-016127, Article 016127
• Main Authors: Itzkovitz, Shalev, Levitt, Reuven, Kashtan, Nadav, Milo, Ron, Itzkovitz, Michael, Alon, Uri
• Format: Article
• Language: English
• Subjects: Algorithms; Animals; Computational Biology; Humans; Models, Biological; Neural Networks (Computer); Proteins - metabolism; Signal Transduction
• ISSN: 1539-3755; 1550-2376
• DOI: 10.1103/physreve.71.016127

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 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 many gates. We apply our approach also to a mammalian protein signal-transduction network, to find a simplified coarse-grained network with three main signaling channels that resemble multi-layered perceptrons made of cross-interacting MAP-kinase cascades. We find that both biological and electronic networks are "self-dissimilar," with different network motifs at each level. The present approach may be used to simplify a variety of directed and nondirected, natural and designed networks.