Yang Qiaofeng, Lonardi Stefano
Department of Computer Science and Engineering, University of California, Riverside, CA 92521, USA.
Int J Data Min Bioinform. 2007;1(3):241-7. doi: 10.1504/ijdmb.2007.011611.
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. Unfortunately, their algorithm suffers from high computational cost and it is impractical for inputs of the size of large PPI networks. Here we report on a novel parallel implementation of Girvan and Newman's clustering algorithm that achieves almost linear speed-up for up to 32 processors. The tool is available in the public domain from the authors' website.
蛋白质-蛋白质相互作用图（PPI）的可用性不断提高，这就需要新的高效工具，能够从这些网络中提取有价值的生物学知识。在众多聚类算法中，Girvan和Newman的边介数算法在发现多个真实网络中的聚类结构方面表现出色。不幸的是，他们的算法计算成本很高，对于大型PPI网络规模的输入来说不切实际。在此，我们报告一种Girvan和Newman聚类算法的新型并行实现，该实现对于多达32个处理器可实现几乎线性的加速。该工具可从作者网站在公共领域获取。
