A Parallel Edge Betweenness Clustering Tool for Protein Interaction Networks
The increasing availability of protein-protein interaction graphs (PPI) requires new efficient tools capable of extracting valuable biological knowledge from these networks. Among the wide range of clustering algorithms, Girvan and Newman's edge betweenness algorithm showed remarkable performances in discovering clustering structures in several real-world networks (including some PPI networks). Unfortunately, their algorithm suffers from high computational cost and it is impractical for input graphs of large size as most PPI networks are. In this paper we report on a parallel implementation of Girvan and Newman's clustering algorithm that allows users to run the algorithm on clusters of computers. Our parallel implementation achieves almost linear speed-up up to 32 processors. Preliminary experiments show that the algorithm is capable of identifying clusters corresponding to functionally related protein modules.
Parallel Edge Betweenness Clustering (PEBC)