Research And Design On Community Detection

In complex network analysis, community detection is getting more and more attention. In recent years, because of the problems exists in the global community detection, such as the difficult to obtain the complete information of the network, and then the local community detection has been proposed by researchers. The local community detection is extracting one community from a certain start vertex with limited knowledge of an entire graph.In this paper, we do an in-depth research on local community detection algorithms. Its main work and contributions are as follows:1) We found that the previous methods of local community detection now are more or less inadequate. For example, R method requires a pre-defined parameter K which may affect the good or bad of the final outcome; although the recall of M method is good but its precision is low. So, in this paper, we have proposed a new local modularity metric G, and based on it, a two-phase algorithm is proposed. The method we have taken is a greedy addition algorithm which means adding vertices into the community until G does not increase. Compared with the previous methods, use our method to calculate the modularity metric, the range of vertices what we considered may affect the quality of the community detection is wider. The results of experiments show that whether in computer-generated random graph or in the real networks, the method in this paper can effectively solve the problem of the local community detection.2) Because each algorithm has its advantages and disadvantages, it is very important to choose the suitable algorithm in different situations. For example, if the position of starting node is boundary, R method is better than LS method. If the position of the starting node is center, LS is better. So, in this paper, we propose a local community detection model based on the notion of game theory, which can combine advantages of previous algorithms(R and LS) effectively to get a better community detection results. By making some experiments, it verifies that the local community detection model based on game theory and the new algorithms are valid.3) The overlapping communities are also getting more and more attention. In this paper,we applied the local community detection to detecting the overlapping communities. Based on an existing algorithm, we make an improvement to let the source node selected in each time is fixed, our improvement makes the algorithm has a certain stability. Experimental results show that our improvement is very good.