In recent years high-throughput assays have provided a wealth of data on the interactions among proteins of entire organisms. Network research has enabled the study of an organism's entire ensemble of protein interactions—the protein interaction network. Biological network analyses provide a new paradigm for understanding the development, function, and evolution of protein interactions. This dissertation expands the research on protein interaction network evolution.

The initial focus of the dissertation is on link dynamics, the evolutionary gain and loss of an organism's protein interactions. Previous research has established that de novo interaction gain in protein interaction networks is pervasive. This research is critically reviewed, exposing methodological errors and flawed assumptions which have led to this finding. Alternative link dynamics are proposed to explain the exposed discrepancies. From these results a framework for modeling the evolution of an organism's protein interaction network is developed and applied to Saccharomyces cerevisiae. This evolutionary re-creation suggests how key topological properties evolve in protein interaction networks, and the inability of current theoretical models to reproduce them. The evolution of interactions among biological processes is also analyzed.

Next, a theoretical model of protein interaction network evolution is presented which incorporates biological evolutionary phenomena that are absent from previous models. The new evolutionary model more closely approximates the empirical network's clustering topology than earlier models.

Finally, an alternative methodology for assessing theoretical models against empirical network data is developed. Currently, a theoretical network is compared against an empirical network after growing the theoretical network from a small "seed graph" according to the rules of the theoretical model. The resulting grown network is sensitive to the seed graph used and therefore biases empirical network comparisons. To avoid this bias, criteria are identified which are required to non-deterministically devolve a theoretical network backward and reconstitute it by rolling it forward. The network model is then assessed by applying the model's backward/forward criteria to an empirical network.