Discriminative topological features reveal biological network mechanisms

Because pairs of network models can reproduce a few key features such as degree distributions, geodesic lengths, and clustering coefficients with indistinguishable fidelity despite arising from vastly different mechanisms, those coarse features cannot determine which model best describes real-world networks. The authors introduce a method that maps the set of all graphs into a high-dimensional (in principle infinite-dimensional) word space, defining an input space for classification schemes that can state unambiguously which model is most descriptive of a network of interest.

Using training sets built from 17 models drawn from the literature or newly introduced, the discriminative classifiers show that different duplication-mutation schemes best describe the E. coli genetic network, the S. cerevisiae protein interaction network, and the C. elegans neuronal network, outperforming alternatives such as linear preferential attachment and small-world models. The approach is a first step toward systematizing network models and assessing their predictability across communities.