The degree distribution of the generalized duplication model

We study and generalize the duplication model of Pastor-Satorras et al. [Evolving protein interaction networks through gene duplication, J. Theor. Biol. 222 (2003) 199–210]. This model generates a graph by iteratively “duplicating” a randomly chosen node as follows: we start at t0 with a fixed graph G(t0) of size t0. At each step t>t0 a new node vt is added. The node vt selects an existing node u from V(G(t-1))={v1,…,vt-1} uniformly at random (uar). The node vt then connects to each neighbor of the node u in G(t-1) independently with probability p. Additionally, vt connects uar to every node of V(G(t-1)) independently with probability r/t, and parallel edges are merged. Unlike other copy-based models, the degree of the node vt in this model is not fixed in advance; rather it depends strongly on the degree of the original node u it selected.Our main contributions are as follows: we show that (1) the duplication model of Pastor-Satorras et al. does not generate a truncated power-law degree distribution as stated in Pastor-Satorras et al. [Evolving protein interaction networks through gene duplication, J. Theor. Biol. 222 (2003) 199–210]. (2) The special case where r=0 does not give a power-law degree distribution as stated in Chung et al. [Duplication models for biological networks, J. Comput. Biol. 10 (2003) 677–687]. (3) We generalize the Pastor-Satorras et al. duplication process to ensure (if required) that the minimum degree of all vertices is positive. We prove that this generalized model has a power-law degree distribution.