Title: Exact results for directed random networks that grow by node duplication,
Abstract: We present exact analytical results for the degree distribution and 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 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, with probability p, each one of the
outgoing links of the mother node. 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. We obtain analytical results for
the in-degree distribution, $P_t(K_{in})$, and for the out-degree distribution,
$P_t(K_{out})$, of the network at time t. It is found that the in-degrees
follow a shifted power-law distribution, so the network is asymptotically scale
free. In contrast, the out-degree distribution is a narrow distribution, that
converges to a Poisson distribution in the sparse limit and to a Gaussian
distribution in the dense limit. Using these distributions we calculate the
mean degree, $\langle K_{in} \rangle_t = \langle K_{out} \rangle_t$. To
calculate the DSPL we derive a master equation for the time evolution of the
probability $P_t(L=\ell)$, $\ell=1,2,\dots$, that for two nodes, i and j,
selected randomly at time t, the shortest path from i to j is of length $\ell$.
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, $<L>_t$, is found to depend
logarithmically on the network size, $N_t$, namely the corded DND network is a
small-world network.