Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication

Abstract

We present exact analytical results for the distribution of shortest path lengths (DSPL) in a directed network model that grows by node duplication. 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, referred to as 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. Thus, the model is referred to as the corded directed-node-duplication (DND) model. In this network not all pairs of nodes are connected by directed paths, in spite of the fact that the corresponding undirected network consists of a single connected component. More specifically, in the large network limit only a diminishing fraction of pairs of nodes are connected by directed paths. To calculate the DSPL between those pairs of nodes that are connected by directed paths we derive a master equation for the time evolution of the probability $P_t(L=\ell )$, $\ell =1,2,\dots$, where $\ell$ is the length of the shortest directed path. Solving the master equation, we obtain a closed form expression for $P_t(L=\ell )$. It is found that the DSPL at time $t$ consists of a convolution of the initial DSPL $P_0(L=\ell )$, with a Poisson distribution and a sum of Poisson distributions. The mean distance ${\mathbb{E}}_t[L|L<\infty ]$ between pairs of nodes which are connected by directed paths is found to depend logarithmically on the network size $N_t$. However, since in the large network limit the fraction of pairs of nodes that are connected by directed paths is diminishingly small, the corded DND network is not a small-world network, unlike the corresponding undirected network.

arXiv comment16 pages, 9 figures. arXiv admin note: substantial text overlap with arXiv:1807.01591, arXiv:1708.07177

References in corpus (34)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure of scientific collaboration networks
• The large-scale organization of metabolic networks
• Epidemic processes in complex 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
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
• Duplication-divergence model of protein interaction network
• Log-Networks
• Structure of shells in complex networks
• Nonuniversal power law scaling in the probability distribution of scientific citations
• Structural Transitions in Dense Networks
• Metric structure of random 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
• Distance distribution in random graphs and application to networks exploration
• Fractal Boundaries of Complex Networks
• Distribution of diameters for Erdös-Rényi random graphs
• Analytical results for the distribution of shortest path lengths in random networks
• Cliques and duplication-divergence network growth
• Distance distribution in configuration model networks
• Power-law citation distributions are not scale-free
• The distribution of shortest path lengths in a class of node duplication network models
• Simple and accurate analytical calculation of shortest path lengths

Cited by in corpus (8)

• Big Networks: A Survey
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Power Laws, the Price Model, and the Pareto type-2 Distribution
• Statistical analysis of edges and bredges in configuration model networks
• Random Recursive Hypergraphs
• Phases of Small Worlds: A Mean Field Formulation
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Nonreciprocal random networks and their percolation properties