  Are biological networks different from other large complex networks? Both
large biological and non-biological networks exhibit power-law graphs (number
of nodes with degree k, N(k) ~ k-b) yet the exponents, b, fall into different
ranges. This may be because duplication of the information in the genome is a
dominant evolutionary force in shaping biological networks (like gene
regulatory networks and protein-protein interaction networks), and is
fundamentally different from the mechanisms thought to dominate the growth of
most non-biological networks (such as the internet [1-4]). The preferential
choice models non-biological networks like web graphs can only produce
power-law graphs with exponents greater than 2 [1-4,8]. We use combinatorial
probabilistic methods to examine the evolution of graphs by duplication
processes and derive exact analytical relationships between the exponent of the
power law and the parameters of the model. Both full duplication of nodes (with
all their connections) as well as partial duplication (with only some
connections) are analyzed. We demonstrate that partial duplication can produce
power-law graphs with exponents less than 2, consistent with current data on
biological networks. The power-law exponent for large graphs depends only on
the growth process, not on the starting graph.
