Research And Application On Community Detection Algorithms In Complex Networks

As a new emerging discipline, complex networks research has attracted wide attention of many researchers from different subjects. Community structure is an important feature of complex networks, which characterizes the relationship within the local and between the locals. It’s a new focus of complex networks.As the sequencing of human genome project is complete, post genome era which focuses on proteomics research is quietly coming, and its research object is protein-protein interaction network. At present, the protein-protein interaction network research is focused on identification of biological modules, which can be considered as community structure in complex networks. Community structure detection algorithms can be applied on protein-protein interaction network to identify biological modules, which are combined with the gene ontology database for biological analysis. This work has important theoretical research value and practical significance. This thesis mainly includes the following aspects.(1) For standard and protein-protein interaction network data, we analyzed and verified the major characteristics of complex networks, and found that the scale-free feature of standard network is not obvious and protein-protein interaction networks have obvious scale-free feature.(2) Several classic non-overlapping community detection algorithms were studied, including spectral methods, k-means algorithm, GN algorithm, modularity optimization algorithms and MCODE algorithm. We found the two modularity optimization algorithms on the protein-protein interaction network data have high biological support.(3) In the aspect of overlapping community detection, we mainly studied the clique percolation method and the traditional fuzzy clustering algorithm. For relatively sparse standard and protein-protein interaction network, the experimental results showed that the node lost ratio was high for the clique percolation algorithm. The results of fuzzy clustering algorithms for the standard data are good, but little modules can be found in protein-protein interaction networks, and module size scale is large, which reduces the support function in biology.(4) Based on the information entropy concept, a new community structure evaluation function was proposed, i.e. validity function based on entropy. The community detection correctness and time cost of this validity function is better than that of modularity function. We combined this function with fuzzy c-means(FCM) algorithm, and the experimental results showed that the optimal clustering number can be accurately found in standard network.