While protein-protein interactions have been studied largely as a network graph without physicality, here we analyze two protein complex data sets of Saccharomyces cerevisiae to relate physical and functional modularity to the network topology. We study for the first time the number of different protein complexes as a function of the protein complex size and find that it follows an exponential decay with a characteristic number of about 7. This reflects the dynamics of complex formation and dissociation in the cell. The analysis of the protein usage by complexes shows an extensive sharing of subunits that is due to the particular organization of the proteome into physical complexes and functional modules. This promiscuity accounts for the high clustering in the protein network graph. Our results underscore the need to include the information contained in observed protein complexes into protein network analyses.