Analytical results for the in-degree and out-degree distributions of directed random networks that grow by node duplication

Abstract

We present exact results for the degree distribution in a directed network model that grows by node duplication (ND). Such models are useful in the study of the structure and growth dynamics of gene regulatory networks and scientific citation networks. Starting from an initial seed network, at each time step a random node, a mother node, is selected for duplication. Its daughter node is added to the network and duplicates each outgoing link of the mother node with probability p. In addition, the daughter node forms a directed link to the mother node itself. We obtain analytical results for the in-degree distribution $P_t(K_{in}=k)$, and for the out-degree distribution $P_t(K_{out}=k)$ at time t. The in-degrees follow a shifted power-law, so the network is asymptotically scale free. In contrast, the out-degree distribution is narrow, and converges to a Poisson distribution in the sparse network limit and to a Gaussian distribution in the dense network limit. Such distinction between a broad in-degree distribution and a narrow out-degree distribution is common in empirical networks such as scientific citation networks. Using this we calculate the mean degree $⟨K_{in}{⟩}_t=⟨K_{out}{⟩}_t$, which converges to $1/(1-p)$ in the large network limit, for the whole range of $0<p<1$. This is in contrast to the corresponding undirected network, which exhibits a phase transition at $p=1/2$ such that for $p>1/2$ the mean degree diverges in the large network limit. We also present analytical results for the distribution of the number of upstream and downstream nodes from a random node. The mean values $⟨N_{up}{⟩}_t=⟨N_{down}{⟩}_t$ scale logarithmically with the network size, implying that only a small fraction of pairs of nodes are connected by directed paths, unlike the undirected ND case that consists of a single component, hence not a small-world network.

arXiv comment33 pages, 4 figures. arXiv admin note: substantial text overlap with arXiv:1708.07177

References in corpus (24)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure of scientific collaboration networks
• The large-scale organization of metabolic networks
• Random graphs with arbitrary degree distributions and their applications
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• Connectivity of Growing Random Networks
• Organization of Growing Random Networks
• Universality of citation distributions: towards an objective measure of scientific impact
• Scale-Free Networks are Ultrasmall
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Citation Statistics from 110 Years of Physical Review
• Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
• Duplication-divergence model of protein interaction network
• Log-Networks
• Nonuniversal power law scaling in the probability distribution of scientific citations
• Structural Transitions in Dense Networks
• Growing complex network of citations of scientific papers -- measurements and modeling
• Stochastic dynamical model of a growing network based on self-exciting point process
• Densification and Structural Transitions in Networks that Grow by Node Copying
• Cliques and duplication-divergence network growth
• Power-law citation distributions are not scale-free
• The distribution of shortest path lengths in a class of node duplication network models
• Preferential attachment mechanism of complex network growth: "rich-gets-richer" or "fit-gets-richer"?

Cited by in corpus (5)

• Power Laws, the Price Model, and the Pareto type-2 Distribution
• Statistical analysis of edges and bredges in configuration model networks
• Random Recursive Hypergraphs
• Nonreciprocal random networks and their percolation properties
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment