  We model the evolution of eukaryotic protein-protein interaction (PPI)
networks. In our model, PPI networks evolve by two known biological mechanisms:
(1) Gene duplication, which is followed by rapid diversification of duplicate
interactions. (2) Neofunctionalization, in which a mutation leads to a new
interaction with some other protein. Since many interactions are due to simple
surface compatibility, we hypothesize there is an increased likelihood of
interacting with other proteins in the target protein's neighborhood. We find
good agreement of the model on 10 different network properties compared to
high-confidence experimental PPI networks in yeast, fruit flies, and humans.
Key findings are: (1) PPI networks evolve modular structures, with no need to
invoke particular selection pressures. (2) Proteins in cells have on average
about 6 degrees of separation, similar to some social networks, such as
human-communication and actor networks. (3) Unlike social networks, which have
a shrinking diameter (degree of maximum separation) over time, PPI networks are
predicted to grow in diameter. (4) The model indicates that evolutionarily old
proteins should have higher connectivities and be more centrally embedded in
their networks. This suggests a way in which present-day proteomics data could
provide insights into biological evolution.
