Evolving networks through deletion and duplication

Abstract

We introduce a minimalistic model based on dynamic node deletion and node duplication with heterodimerisation. The model is intended to capture the essential features of the evolution of protein interaction networks. We derive an exact two-step rate equation to describe the evolution of the degree distribution. We present results for the case of a fixed-size network. The results are based on the exact numerical solution to the rate equation which are consistent with Monte Carlo simulations of the model's dynamics. Power-law degree distributions with apparent exponents $<1$ were observed for generic parameter choices. However, a proper finite-size scaling analysis revealed that the actual critical exponent in such cases is equal to 1. We present a mean-field argument to determine the asymptotic value of the average degree, illustrating the existence of an attractive fixed point, and corroborate this result with numerical simulations of the first moment of the degree distribution as described by the two-step rate equation. Using the above results, we show that the apparent exponent is determined by the heterodimerisation probability. Our preliminary results are consistent with empirical data for a wide range of organisms, and we believe that through implementing some of the suggested modifications, the model could be well-suited to other types of biological and non-biological networks.

12 pages, 7 figures, to be published in New J. Phys. (2006)

References in corpus (16)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Lethality and centrality in protein networks
• Evolution of networks
• Hierarchical Organization in Complex Networks
• Organization of Growing Random Networks
• Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
• Duplication-divergence model of protein interaction network
• Dynamics of directed graphs: the world-wide Web
• Cliques and duplication-divergence network growth
• Multifractal properties of growing networks
• Some asymptotic properties of duplication graphs
• Random networks created by biological evolution
• Extremal dynamics model on evolving networks
• Self-organization of structures and networks from merging and small-scale fluctuations
• Dynamic scaling and universality in evolution of fluctuating random networks

Cited by in corpus (10)

• Simple and efficient self-healing strategy for damaged complex networks
• Addition-Deletion Networks
• On the scaling of probability density functions with apparent power-law exponents less than unity
• Random Birth-and-Death Networks
• Link-space formalism for network analysis
• Fragmentation of Random Trees
• Dissipative stochastic sandpile model on small world network : properties of non-dissipative and dissipative avalanches
• Link-Space and Network Analysis
• Reconstruction of Network Evolutionary History from Extant Network Topology and Duplication History
• Emergence of Network Structure in Models of Collective Evolution and Evolutionary Dynamics