The distribution of shortest path lengths in a class of node duplication network models

Abstract

We present analytical results for the distribution of shortest path lengths (DSPL) in a network growth model which evolves by node duplication (ND). The model captures essential properties of the structure and growth dynamics of social networks, acquaintance networks and scientific citation networks, where duplication mechanisms play a major role. 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, forming a link to the mother node, and with probability $p$ to each one of its neighbors. The degree distribution of the resulting network turns out to follow a power-law distribution, thus the ND network is a scale-free network. To calculate the DSPL we derive a master equation for the time evolution of the probability $P_t(L=\ell )$, $\ell =1,2,\dots$, where $L$ is the distance between a pair of nodes and $t$ is the time. Finding an exact analytical solution of the master equation, we obtain a closed form expression for $P_t(L=\ell )$. The mean distance, $⟨L{⟩}_t$, and the diameter, ${\Delta }_t$, are found to scale like $\ln t$, namely the ND network is a small world network. The variance of the DSPL is also found to scale like $\ln t$. Interestingly, the mean distance and the diameter exhibit properties of a small world network, rather than the ultrasmall world network behavior observed in other scale-free networks, in which $⟨L{⟩}_t\sim \ln \ln t$.

arXiv comment36 pages, 9 figures

References in corpus (29)

• 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
• The phase transition in inhomogeneous random graphs
• 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
• 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
• Analytical results for the distribution of shortest path lengths in random networks
• Cliques and duplication-divergence network growth
• Distance distribution in configuration model networks

Cited by in corpus (13)

• Effect of shortest path multiplicity on congestion of multiplex networks
• Distribution of shortest cycle lengths in random networks
• Statistical analysis of articulation points in configuration model 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
• 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
• Analytical results for the in-degree and out-degree distributions of directed random networks that grow by node duplication
• 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
• Structural and temporal heterogeneities on networks
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment