Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.tcs.2006.08.045 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
node u,node vt,generalized duplication model,J. Theor,duplication model,power law,computational proteomics,Evolving protein interaction network,existing node u,random graph generation,power-law degree distribution,original node u,new node vt,gene duplication | Journal | 369 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 19 |
PageRank | References | Authors |
1.52 | 20 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| G. Bebek | 1 | 19 | 1.52 |
| petra berenbrink | 2 | 102 | 6.53 |
| Colin Cooper | 3 | 287 | 30.73 |
| T. Friedetzky | 4 | 19 | 1.52 |
| Joseph H. Nadeau | 5 | 149 | 21.83 |
| S. C. Sahinalp | 6 | 21 | 1.91 |