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 to with a fixed graph G(t(0)) of size t(0). At each step t > t(0) a new node upsilon(t) is added. The node upsilon(t) selects an existing node it from V(G(t - 1)) = {upsilon(1), ..., upsilon(t-1)} uniformly at random (uar). The node upsilon(t) then connects to each neighbor of the node it in G(t - 1) independently with probability p. Additionally, upsilon(t) 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 upsilon(t) 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. (c) 2006 Elsevier B.V. All rights reserved.
random graph generation power law computational proteomics