Research Community Detection Algorithm Based On Cooperative Game

With the rapid development of Internet technology, a variety of social applications has changed people’s lifestyle. People communicate and cooperate with others in virtual Internet, which forming a large-scale social networks. Prevalently, there are community structure characteristics in social networks, which can help people understand the internal structure and relationship of networks through mining the community structure from these large-scale social networks. Therefore, community detection has important practical significance.Currently, researchers have proposed many community detection algorithms, but it is still difficult to carry on the community detection in face of thousands of nodes of these large-scale social networks. Therefore, By enhancing the efficiency of community detection, we can find the community structures of these large-scale social networks within the valid time, which is meaningful for a better applications of networks.Our early research achievements-Cooperative Game hierarchical clustering community detection algorithm (GAMEHC algorithm) can reveal the hierarchy structures of network community. However, this algorithm is difficult to apply into large-scale social networks because of its high time complexity and the inherent disadvantage of hierarchical clustering. In this paper, we study how to automatically determine the final division number of community through a certain algorithm on the basis of previous research, and how to apply this algorithm to large-scale social networks.In this paper, we change the strategy of cooperation among the Union Leagues according to the incremental of Shapley value to use a single node as a participant to conduct cooperative game with the alliance. This algorithm can automatically determine the final division number of community and will be ended up if the Shapley values of all nodes are no longer increasing. What’s more, we design the community adjustment strategy because of the disadvantage of the improved algorithm will produce meaningless small communities. The ultimate improved algorithm can greatly improve the efficiency of community detection.In order to improve the efficiency of the algorithm, this paper defines No Contribution Nodes and Vested Nodes according to the cooperative game model and the execution strategy of the algorithm. The No Contribution Nodes cannot generate any contributions because they are not connected with any edges of the current alliance, while all the degrees of the Vested Nodes have fully contribute to a league during the execution of the algorithm, which have confirmed as alliance belonging and do not need to attend the next game. We design the pruning algorithms of these No Contribution Nodes and Vested Nodes based on definition, which effectively reduce the redundant calculation steps and improve the efficiency of community detection.In this paper, I verify the effectiveness of the improved algorithm with the small-scale real benchmark network datasets and the small-scale simulate benchmark network datasets of certain community network, and then verify its better time efficiency with a large-scale real datasets of social networks and LFR benchmark random networks.