Research On Detecting Algorithms For Community Structures In Complex Networks Based On Modularity

Along with further study on the physical significance and functional characteristics of complex networks, community structures are a common property of many complex networks. In recent years, researching on community structures detecting algorithms has become one of hot researching problem in complex networks. However, the rearchers found that complex networks have the overlapping communities and the type of the vertices in complex networks has binary characteristics. But current community structures detection algorithms in one-mode networks have high complexity, low accuracy or do not detect overlapping community structures. And bi-community structures detection algorithms in bipartite networks begin in projecting bipartite networks into one-mode networks. But the process of projection can lead to some problems, such as loss of information. Consequently, in order to detect the overlapping community structures in one-mode networks and bipartite networks, the main work and innovation points of this dissertation are as follows:(1) An overlapping community structures detection algorithm based on the core-vertex and intimate degree is proposed.There is only one vertex type in one-mode networks and some vertices have the maximum degree of vertices, so the core-vertex is proposed firstly. After extracting all the core-vertices from one-mode networks, compute the intimate degree between the core-vertices and the neighboring vertices. Then these core-vertices are expanded using intimate degree function. Lastly, this algorithm successfully detects the overlapping community structures in one-mode networks. The experimental results show that the algorithm can accomplish the overlapping community structures detection during a lower running time. And community structures detection results are high accuracy through the modularity function, which conform to the actual community structure characteristics of complex networks.(2) An overlapping community structures detection algorithm based on the extended modularity is proposed.Due to traditional hierarchical clustering algorithms and division algorithms have high time complexity, the seed community based on the vertex degree in weighted complex networks is proposed firstly according to the structure characteristics of weighted networks. And the characteristics of the seed community are given based on vertex degree. Then absorbing degree function is proposed to determining connecting degree between the seed communities and the neighboring vertices. The main steps of the algorithm are extracted the seed communities from one-mode networks, then according to the absorbing degree function gradually expand the seed communities. And the overlapping community structures are obtained based on the vertex degree. The algorithm was carried out in computer generated network and several real-world networks. The experimental results show that this algorithm can accurately detect the overlapping community structures in one-mode networks. Comparing with some existing algorithms, results show that this algorithm can detect the accurate overlapping community structures in large complex networks.(3) An overlapping community structures detection algorithm based on the maximal complete sub-graphs is proposed.According to the real complex networks contain a large number of the maximal complete sub-graphs and have local star networks characteristics, this algorithm is proposed. This algorithm firstly extracts the maximal complete sub-graphs through the depth and width searching from one-mode networks. Then two maximal cliques can be merged into a larger sub-graph by some given rules. Detecting results of community structures are judged by the extending modularity function. The experimental results show that this algorithm can ensure the accuracy of overlapping community structures detection during a low running time. This algorithm also can detect the overlapping vertices, bridge vertices and isolated vertices with special structural characteristics and functional characteristics in complex networks.(4) An overlapping bi-community structures detection algorithm based on the maximal complete bi-subgraphs and the bipartite clustering coefficient is proposed.A bipartite network is a network with the two non-overlapping types of vertices and the edges only connecting a pair of vertices which belong to different types. Some traditional approaches are adopted to project bipartite networks into one-mode networks. But the process of projection can lose some information of the original bipartite networks, bring an inflation of the number of edges and add some information which does not belong to the original bipartite networks. So an overlapping bi-communities detection algorithm in the original bipartite networks is proposed. This algorithm firstly give concepts of the maximal complete bi-subgraphs and bipartite clustering coefficient. This algorithm consists of two main steps. One is that some maximal complete bi-subgraphs are extracted from the original bipartite networks. The other is that two neighboring maximal bi-subgraphs can be merged into a larger bi-subgraphs by the bipartite clustering coefficient. The experimental results show that this algorithm can detect the bi-communities accurately when the bi-modularity function is in a point of maximum value.Three algorithms of overlapping community structures detection are proposed in this dissertation for adapting to different networks. The overlapping community structures detection algorithm based on the core-vertex and intimate degree can be used in the one-mode networks with larger degree of vertices. And the overlapping community structures detection algorithm based on the extended modularity can be used in the one-mode networks with weight. And the overlapping community structures detection algorithm based on the maximal complete sub-graphs can be used in the one-mode networks containing a large number of the maximal complete sub-graphs and having local star networks characteristics.The research is jointly supported by the National Natural Science Foundation of China (Nos:61370145,61173183, and60973152), the Doctoral Program Foundation of Institution of Higher Education of China (No:20070141014), Program for Liaoning Excellent Talents in University (No:LR2012003), the National Natural Science Foundation of Liaoning province (No:20082165) and the Fundamental Research Funds for the Central Universities (No: DUT12JB06).