The densely connected structure of protein-protein interaction (PPI) networks reflects the functional need of proteins to cooperate in cellular processes. However, PPI networks do not adequately capture the competition in protein binding. By contrast, the interface interaction network (IIN) studied here resolves the modular character of protein-protein binding and distinguishes between simultaneous and exclusive interactions that underlie both cooperation and competition. We show that the topology of the IIN is under evolutionary pressure, and we connect topological features of the IIN to specific biological functions. To reveal the forces shaping the network topology, we use a sequence-based computational model of interface binding along with network analysis. We find that the more fragmented structure of IINs, in contrast to the dense PPI networks, arises in large part from the competition between specific and nonspecific binding. The need to minimize nonspecific binding favors specific network motifs, including a minimal number of cliques (i.e., fully connected subgraphs) and many disconnected fragments. Validating the model, we find that these network characteristics are closely mirrored in the IIN of clathrin-mediated endocytosis. Features unexpected on the basis of our motif analysis are found to indicate either exceptional binding selectivity or important regulatory functions.