A Syudy Of Web Community Detection Algorithm

Community Detection is a very important technology in network research. Because, in some extent, Community structure could reflect the topology relationship of real system, and there is great significance to find the potential communities in network. Particularly, with the rapid development of the Internet, it has become an indispensable part of human’s social life, so discovery and analyze the potential communities in the Internet has a further significance. We know that, in reality, the variety of social circles, in some levels, could reflect the relationship among people. The peoples in the same social circle usually also have some contacts in the Internet, Doing community structure analysis of the online social networks such as FaceBook, Twitter, Sina, Tianya, Mop could find the potential relationship exists among people, then we not only can quickly understand and predict people’s activities, but also can carry out a more effective monitoring of the development of public opinion. At the same time, it can provide some basis when we compare the activities of people between reality communities and virtual network community. On the other hand, nowadays, commodity recommended function is a function which most online malls provided, the realization of this function is actually based on community detection technology. The key of commodity recommended system is identifying the customers with similar buying interest from the relationship network of customers and commodities, this process is actually the process to do community detection among customers. Moreover, there are variety of information filled with the Internet, so getting the information we wanted is not an easy thing. If we do community detection among these information of the Internet, then, not only can this problem be solved and also can achieve the personal information recommended function, as well as the intelligent search function, which lead the user to find the information they interested more accurately and quickly.In this paper, we first introduced the theoretical knowledge of community detection, and then give a brief review of some traditional algorithms, such as Kernighan-Lin algorithm(a segmentation algorithm), GN algorithm(a hierarchical clustering algorithm), Newman-fast algorithm(a algorithm based on module optimization), CPM algorithm(a algorithm to find overlapping communities). To each algorithm, we also analyzed its advantages and disadvantages, as well as its complexity. In addition, we also introduced the objective quality evaluation criteria of community.After making deep analysis and understanding of the existing community detection algorithms, we proposed two new community detection algorithms. The two new algorithms are both designed for micro-blog, which is a bidirectional social network. The first algorithm is community detection algorithm based on the community attractive; and the second one is overlapping community detection algorithm based on community attractive. The reason why algorithm one is proposed, is to solve the problem that the existing community detection algorithms are of high complexity when used to analyze the large-scale network like micro-blog. Algorithm one not only performs better than the existing community detection algorithms in time complexity, also performs well in accuracy. In real world, a people may belong to multiple communities at the same time, but most existing algorithms and algorithm one just simply divide each individual into a single community, so the results of these algorithms are not quite consistent with the fact, that is why algorithm two is proposed; the existing overlapping community detection algorithms are of poor performance for large-scale network is also the reason. Finally, the simulation results give a strong proof to the effectiveness and efficiency of the two algorithms.