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

Chanania Steinbock, Ofer Biham () and Eytan Katzav
Additional contact information
Chanania Steinbock: Racah Institute of Physics, The Hebrew University
Ofer Biham: Racah Institute of Physics, The Hebrew University
Eytan Katzav: Racah Institute of Physics, The Hebrew University

The European Physical Journal B: Condensed Matter and Complex Systems, 2019, vol. 92, issue 6, 1-16

Abstract: 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 Pt(L = ℓ), ℓ = 1, 2, … , where ℓ is the length of the shortest directed path. Solving the master equation, we obtain a closed form expression for Pt(L = ℓ). It is found that the DSPL at time t consists of a convolution of the initial DSPL P0(L = ℓ), with a Poisson distribution and a sum of Poisson distributions. The mean distance 𝔼t[L|L

Keywords: Statistical; and; Nonlinear; Physics (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1140/epjb/e2019-100139-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurphb:v:92:y:2019:i:6:d:10.1140_epjb_e2019-100139-5

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/10051

DOI: 10.1140/epjb/e2019-100139-5

Access Statistics for this article

The European Physical Journal B: Condensed Matter and Complex Systems is currently edited by P. Hänggi and Angel Rubio

More articles in The European Physical Journal B: Condensed Matter and Complex Systems from Springer, EDP Sciences
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().