Current proteomic techniques allow researchers to analyze chosen biological pathways or an ensemble of related protein complexes at a global level via the measure of physical protein-protein interactions by affinity purification mass spectrometry (AP-MS). Such experiments yield information-rich but complex interaction maps whose unbiased interpretation is challenging. Guided by current knowledge on the modular structure of protein complexes, we propose a novel statistical approach, named BI-MAP, complemented by software tools and a visual grammar to present the inferred modules. We show that the BI-MAP tools can be applied from small and very detailed maps to large, sparse, and much noisier data sets. The BI-MAP tool implementation and test data are made freely available.