Inferring Network Mechanisms: The Drosophila melanogaster Protein Interaction Network

Abstract

Naturally occurring networks exhibit quantitative features revealing underlying growth mechanisms. Numerous network mechanisms have recently been proposed to reproduce specific properties such as degree distributions or clustering coefficients. We present a method for inferring the mechanism most accurately capturing a given network topology, exploiting discriminative tools from machine learning. The Drosophila melanogaster protein network is confidently and robustly (to noise and training data subsampling) classified as a duplication-mutation-complementation network over preferential attachment, small-world, and other duplication-mutation mechanisms. Systematic classification, rather than statistical study of specific properties, provides a discriminative approach to understand the design of complex networks.

19 pages, 5 figures

References in corpus (2)

• Systematic identification of statistically significant network measures
• Structure and evolution of protein interaction networks: A statistical model for link dynamics and gene duplications

Cited by in corpus (30)

• Characterization of complex networks: A survey of measurements
• Scale-free networks are rare
• Generative models of the human connectome
• Model of Genetic Variation in Human Social Networks
• On the Convexity of Latent Social Network Inference
• A simple physical model for scaling in protein-protein interaction networks
• Network Archaeology: Uncovering Ancient Networks from Present-day Interactions
• Subsampling bootstrap of count features of networks
• Yeast Protein Interactome Topology Provides Framework for Coordinated-Functionality
• Cliques and duplication-divergence network growth
• Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph Isomorphism
• What are the Best Hierarchical Descriptors for Complex Networks?
• BioCode: A Data-Driven Procedure to Learn the Growth of Biological Networks
• Random Spatial Network Models with Core-Periphery Structure
• Graph animals, subgraph sampling and motif search in large networks
• Generative Model Selection Using a Scalable and Size-Independent Complex Network Classifier
• Automatic Network Fingerprinting through Single-Node Motifs
• Testing biological network motif significance with exponential random graph models
• Subgraph Counting: Color Coding Beyond Trees
• Generalized Devil's staircase and RG flows
• Self-Organization and Complex Networks
• What do we learn from correlations of local and global network properties?
• Neuromodulation Influences Synchronization and Intrinsic Read-out
• Flexible model selection for mechanistic network models
• Number-theoretic aspects of 1D localization: "popcorn function" with Lifshitz tails and its continuous approximation by the Dedekind $\eta$
• Detecting highly cyclic structure with complex eigenpairs
• Empirically Classifying Network Mechanisms
• Maximum likelihood estimation for mechanistic network models
• Optimization over a class of tree shape statistics
• Reconstruction of Network Evolutionary History from Extant Network Topology and Duplication History