Efficient modularization of weighted protein interaction networks using k-hop graph reduction

Recent computational analyses of protein interaction networks have attempted to understand cellular organizations, processes and functions. Several topology-based clustering methods have been applied to the protein interaction networks for detecting functional modules. However, most of the previous algorithms do not perform well on small-world, scale-free networks. In this paper, we present an efficient approach to identify hierarchical modules in the protein interaction networks. Our algorithm selects a small number of informative proteins from a large network, and transforms the intricate small-world, scale-free network into a simple graph with high modularity. Our results show that this approach remarkably enhances the efficiency. We also demonstrate that it outperforms other previous methods in terms of accuracy.