Cliques and duplication-divergence network growth

Abstract

A population of complete subgraphs or cliques in a network evolving via duplication-divergence is considered. We find that a number of cliques of each size scales linearly with the size of the network. We also derive a clique population distribution that is in perfect agreement with both the simulation results and the clique statistic of the protein-protein binding network of the fruit fly. In addition, we show that such features as fat-tail degree distribution, various rates of average degree growth and non-averaging, revealed recently for only the particular case of a completely asymmetric divergence, are present in a general case of arbitrary divergence.

7 pages, 6 figures

References in corpus (1)

• Inferring Network Mechanisms: The Drosophila melanogaster Protein Interaction Network

Cited by in corpus (11)

• Structural Transitions in Dense Networks
• Densification and Structural Transitions in Networks that Grow by Node Copying
• Network growth models and genetic regulatory networks
• Evolving networks through deletion and duplication
• The distribution of shortest path lengths in a class of node duplication network models
• Graph animals, subgraph sampling and motif search in large networks
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
• Analytical results for the in-degree and out-degree distributions of directed random networks that grow by node duplication
• Impact of observational incompleteness on the structural properties of protein interaction networks
• Influence of homology and node-age on the growth of protein-protein interaction networks