To understand living cells one must study them as systems rather than as a collection of individual molecules. The abstract representation of intracellular systems as ‘networks’ is fruitful, because it provides the ability to study these systems as a whole by ignoring details of individual components, but retaining the complexity of the interactions. This chapter will review the discoveries made through application of approaches from ‘the science of complex networks’ to Protein Interaction Networks, i.e. undirected networks in which the nodes represent proteins, and pairs are connected by edges if the proteins physically interact. Over the last decade the experimental techniques for measuring protein interactions has been highly improved and large numbers of new protein interactions have been elucidated. Therefore, along with the reviewed concepts and discoveries, we provide a re-evaluation of several previous conclusions by analyzing a set of high quality networks from the organism S. cerevisiae (baker's yeast), based on recent experimental data. These interaction networks are obtained from three distinct experimental methodologies: 1) literature curation (LC; by combining low-throughput experiments), 2) affinity-purification followed by mass spectrometry (AP-MS), and 3) the yeast two-hybrid system (Y2H). Through the analysis of these new quality networks we wish to demonstrate which of the previous conclusions (some dating back from almost a decade ago) still hold anno 2010, and to highlight the differences in Protein Interaction Networks obtained by different experimental techniques. Indeed, we find very distinct topological properties in these different networks, in accordance with other papers who have reported contradictory results when analyzing different datasets. Previous conclusions mainly hold for the new high quality data from Y2H experiments. We end with a discussion on which experimental technique provides the most relevant interaction data for the purpose of constructing wiring diagrams of the proteome, i.e. Protein Interaction Networks.