title: 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 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.
authors.affiliation: Departments of Molecular Cell Biology and Physics of Complex Systems, Weizmann Institute of Science, Rehovot, Israel.
authors.forename: Shalev
authors.initials: S
authors.lastname: Itzkovitz
authors.forename: Reuven
authors.initials: R
authors.lastname: Levitt
authors.forename: Nadav
authors.initials: N
authors.lastname: Kashtan
authors.forename: Ron
authors.initials: R
authors.lastname: Milo
authors.forename: Michael
authors.initials: M
authors.lastname: Itzkovitz
authors.forename: Uri
authors.initials: U
authors.lastname: Alon
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D006801:Humans; D008954:Models, Biological; D016571:Neural Networks, Computer; D011506:Proteins / Q000378:metabolism*; D015398:Signal Transduction
chemical_list: D011506:Proteins