Research On Several Community Detection Algorithms

With the rapid development and mature application of the Internet technique, a variety of application platforms of the open network provide different electronic tools and virtual interactive environments for communication and information exchange between people. In the context of those applications, social network analysis has gradually become a hot issue both in industry and academic. People think the social network could be analyzed and mined quantitatively. And some hidden information and knowledge can be revealed from the analysis and mining. Community mining is one of the basic research problems in social network analysis. In the past decade, it has attracted more and more attention in the research community. Community detection technique has been developed rapidly and many research findings have been proposed. However, most studies are based on the global information that is got from the whole network, which is difficult to meet in practice. By utilizing the features of network including locality, power-law distribution, Pareto effects and others features, this thesis studies the community detection problem in micro and middle level of the network.The primary contributions of the thesis are as follow:1) We take advantage of the universal power-law distribution of social networks and propose a leader based local community detection algorithm LLCDA (Leader based Local Community Detecting Algorithm). Thus, it avoids the drawback of traditional algorithms that they must obtain the global network information. It uses local structural information in the network to optimize a local objective function. A local community can be detected through continuous optimization of the function by expanding from an initial core member computed by a modified PageRank sorting algorithm. The advantage of this algorithm is that it only uses some local information of the network to detect communities by utilizing high importance nodes. The efficiency is higher than traditional algorithms.2) Most community detection algorithms can not control community-scale and suffer the resolution limit. We propose a multi-resolution community detection algorithm named MRCDA (Multi-Resoltion based Community Detection Algorithm) based on our LLCDA algorithm by using core members of the network. It use modified PageRank to sort and extract influential core nodes that can be used as the seed to expand local community structure. Then we use Potts spin-glass model to optimize a local community structure for scale controllable local community detection. The advantage of MRCDA is that it can control the scale of communities of different networks in different applications, and the efficiency is higher than traditional methods.3) Most research methods focus on the nodes of networks, while ignore the importance of the link networks. We convert the idea of the proposed LLCDA to the link community detection and propose a novel algorithm LLCM (Local Link Community Mining algorithm) for discovering link communities in networks. This algorithm uses links rather than nodes to analyze and the discovered link communities represent the natural overlapping structure of the network. A local link community can be detected by maximizing a local link fitness function from a seed link, which was ranked previously. The advantage of MRCDA is that it has a better performance in detecting highly overlapping communities. And the algorithm covers links communities and overlapping communities well.4) Aiming at the problem of most traditional community detection researches do not distinguish different importance and influence of nodes in the network. Here, we divide the nodes into leader node, central member node and ordinary member node. And based on these three roles of nodes, we also define a concept of "central sub-group" to identify core area of the network. Secondly, a measure of connective strength is proposed for computing direct similarities of any two nodes in the network. Then we also propose an algorithm CCDM (Central Clique based Community Detection Method). By discover and adjust the central cliques, the community structure of the whole network can be detached. The advantage of CCDM is that it is suit for weighted networks and also massive networks and it has a low time complexity and high operating efficiency.5) Traditional clustering-based community detection algorithms can only find some communities that have similar scale and the density of community is uncontrolable. Here, we propose the concept of density community, we also devise two density-based community detection algorithms based on our CCDM, of which DCCS algorithm is simple, efficient, and easy to be implemented, but ONDCS algorithm has much higher stability and efficiency. And it has a good performance on communities that have very different community density.