<p>High-throughput screens have begun to reveal the protein interaction networkthat underpins most cellular functions in the yeast Saccharomyces cerevisiae. How the organization ofthis network affects the evolution of the proteins that compose it is a fundamental question in molecularevolution. We show that the connectivity of well-conserved proteins in the network is negatively correlatedwith their rate of evolution. Proteins with more interactors evolve more slowly not because they aremore important to the organism, but because a greater proportion of the protein is directly involvedin its function. At sites important for interaction between proteins, evolutionary changes may occurlargely by coevolution, in which substitutions in one protein result in selection pressure for reciprocalchanges in interacting partners. We confirm one predicted outcome of this process-namely, that interactingproteins evolve at similar rates.</p>