The structure and evolution of the protein interaction network of the yeast Saccharomyces cerevisiae is analyzed. The network is viewed as a graph whose nodes correspond to proteins. Two proteins are connected by an edge if they interact. The network resembles a random graph, in that it consists of many small subnets, groups of proteins that interact with each other but do not interact with any other protein, and one large connected subnet comprising more than half of all interacting proteins. The number of interactions per protein appears to follow a power-law distribution. Within approximately 200 million years after a duplication, the products of duplicate genes become almost equally likely to (i) have common protein interaction partners, and (ii) be part of the same sub-network, as two proteins chosen at random from within the network. This indicates that the persistence of redundant interaction partners is the exception rather than the rule. After gene duplication, the likelihood that an interaction gets lost exceeds 2.2x10-3 per million years. New interactions are estimated to evolve at rate that is approximately three orders of magnitude smaller. Every 300 million years, as many as half of all interactions may become replaced by new interactions.