Advanced technologies are producing large-scale protein-protein interaction data at an ever increasing pace. A fundamental challenge in analyzing these data is the inference of protein machineries. Previous methods for detecting protein complexes have been mainly based on analyzing binary protein-protein interaction data, ignoring the more involved co-complex relations obtained from co-immunoprecipitation experiments.