Superfamilies of Evolved and Designed Networks

TLDR

Complex biological, technological, and sociological networks vary widely in size and connectivity, complicating structural comparisons. The study aims to systematically assess local structural similarity among networks using the significance profile of small subgraphs relative to randomized counterparts. The authors compare each network’s subgraph significance profile to that of randomized networks, thereby quantifying similarity in local structure. They discover several superfamilies of previously unrelated networks sharing similar significance profiles, including transcription networks of microorganisms, protein signaling, developmental genetic networks, and neuronal wiring, as well as power grids, protein‑structure networks, geometric networks, World Wide Web links, social networks, and word‑adjacency networks across languages.

Abstract

Complex biological, technological, and sociological networks can be of very different sizes and connectivities, making it difficult to compare their structures. Here we present an approach to systematically study similarity in the local structure of networks, based on the significance profile (SP) of small subgraphs in the network compared to randomized networks. We find several superfamilies of previously unrelated networks with very similar SPs. One superfamily, including transcription networks of microorganisms, represents “rate-limited” information-processing networks strongly constrained by the response time of their components. A distinct superfamily includes protein signaling, developmental genetic networks, and neuronal wiring. Additional superfamilies include power grids, protein-structure networks and geometric networks, World Wide Web links and social networks, and word-adjacency networks from different languages.