Comparison Of A Few Communities Detection Algorithms For Finding The Functional Modules Of Protein-protein Interaction Networks

In recent years, the complex theory and technology of science, such as complex network theory and system biology, have been developing rapidly. Many scientific researchers in various fields applied the methods in complex networks to study the function modules of large scale biological molecular networks,especially protein-protein interaction networks. A large number of research results confirmed that there exists functional modules in protein-protein interaction networks. Many scientists proposed some kinds of community detection algorithms based on complex network theory to discover functional modules in protein-protein interaction networks.In this paper, we compare the performance of some communities detection algorithms on protein-protein interaction network. First, we construct the proteinprotein interaction network of S. Cerevisiae based on MIPS database and some literatures, then analyse the properties of scale-free and average cluster coefficient of this complex network. The results show that this network is scale-free with degree distribution P(k) ? k-1.536, and the average cluster coefficient is much larger than that of random network with the same size. All of these suggest that the yeast protein-protein interaction network contains community structures. Second,we introduce six kinds of community detection algorithms based on merging or splitting clustering, modularity optimization, information flow or spectral clustering. Combined with the application to yeast protein-protein interaction network,we find that there is an over-learning problem, i.e. more communities have been detected than the real functional modules of the network and many tiny communities are matched to the same of functional module. Finally,we compare the pros and cons of these algorithms from the perspective of modularity, purity and entropy. We find that the information entropy is more reasonable to evaluate those algorithms to find community structures comparing with modularity and purity,and FUA is the most efficacious of these communities detection algorithms.