Research On Adding A Clique At Each Step Based Overlapping Community Detection Algorithm And Its Application

Recently, the research on complex network has become a hot topic and produces a profound influence on development in various fields, such as computer science, economy and sociology. One of the basic tasks in complex network is the detection of community structure, which plays a crucial role in analyzing the topology structure of the network, mining the potential function of the network and predicting the behavior of the network. Usually nodes in a network may belong to different communities, thus leading to the overlapping problem of community. The overlapping of community is a common phenomenon in the real network. In order to comprehensively understand and analyze the real network, researchers focus on discovering overlapping community structure of the network. Thus, in this paper, we studied the problem of community detection on large overlapping network, and proposed an overlapping community detection algorithm based on the idea of adding a clique at each step. Meanwhile, we studied the problem of recommendation on online social network, and then proposed a novel social networking recommendation algorithm.The main contributions of this thesis are shown as follows:(1) This paper proposed an overlapping community detection algorithm by adding a clique at each step. Overlapping community detection becomes a hot spot in the field of community detection. The mainstream solution to detect overlapping community on complex network is based on the local expansion. Specifically, the expansion of community is first starting from a single node, then constantly adding a new node to get the final community. However, the existing algorithms by adding one node at each time do not fully consider the local information of the added node, leading to lower accuracy of the community detection. Note that clique in network is a completely connected sub-graph, in which links of two different nodes are fully connected. Thus, the nodes in a clique usually belong to one community with high probability. Thus, on the basis of local expansion, we propose an overlapping community detection algorithm based on the idea by adding a clique at each step. The algorithm adopts the strategy of adding a clique at each step for local expansion. In the process of group expansion, if one node is determined to be added to the current community, then all the remaining nodes in its clique will be joined to the community. Compared with the existing algorithms for detecting overlapping community, the proposed algorithm can get more accurate performance for detecting the overlapping community structure in the network on both synthetic and real datasets and still can achieve higher precision value especially when network community structure is not obvious. Meanwhile, compared with most traditional overlapping community detection algorithms, our algorithm also has lower time complexity.(2) This paper proposed a novel social networking recommendation algorithm for friend recommendation by adding a clique at each step in online social network. As a kind of classical information recommendation problem, friend recommendation can help users in online social networking arranging and classifying their friend group and provide their potential interest of information resources. In the friend recommendation algorithm, the performance of automatic grouping friends decides the performance of the recommendation algorithm. Base on overlapping community detection algorithm by adding a clique at each step, in this paper, we proposed a novel social networking friend recommendation algorithm. This algorithm combines friend grouping and friend recommendation. To be specific, this algorithm firstly harnesses the proposed community detection algorithm by adding a clique at each step to accurately discover the community structure. Based on the obtained community structures, we can get friend grouping automatically and then use the similarity calculation method to recommend friends for specified user both efficiently and accurately. The experiments on social networks in the real world show that the proposed social networking recommendation algorithm can accurately classify the group of social network. Meanwhile, our algorithm can provide the best useful information for users to achieve effective friend recommendation.