Research On Community Detection Based On Community Characteristic And Community Evolution Tracking Based On Local View

Networks are simple and visual representations of many systems in real world, and the research on networks is helpful for us to understand the world. Many networks such as social networks, co-authorship networks, protein interaction networks, World Wide Web have a fundamental mesoscopic structure, i.e., community structure, which is the division of network nodes into groups within which the network connections are dense, but between which they are sparser. Community detection can reveal the structure as well as the information underlying network, which is important to recognize and understand the network; community evolution tracking can detect the change of community and reveal the intrinsic movement of network, which is significant to capture and lead the development of network. Therefore, the research of community detection and community evolution tracking is very significant.In this paper, we firstly study the problems of social circle detection in personal social networks and community detection in large real networks in community detection, and propose related algorithms of community detection; then we study the problems of discovering communities at each time in dynamic networks and matching community structures at two consecutive times in community evolution tracking, and propose related algorithm of community evolution tracking. The main work is as follows:1. To solve the problem of social circle detection, we propose an algorithm named as enhanced link clustering. Social circle detection falls into the field of community detection, and based on the observation over the ground-truth circles, we integrate the node attributes and network structure into edges and propose the algorithm of enhanced link clustering. The experimental results show that compared with the sate-of-the-arts, the proposed algorithm performs better in terms of both efficiency and accuracy.2. To discover the communities better in large real networks, we propose two algorithms based on weighting strategy. We firstly study the ground-truth communities in large real networks and observe a characteristic of community structure; motivated by the observed characteristic, we then design a weighting strategy and propose two algorithms with this weighting strategy. Experiments on large real networks show that the proposed algorithms can improve the similarity of detected communities to ground-truth communities.3. We propose a weighted local view algorithm. This algorithm explores the local views of nodes to the community structure based on the observed characteristic, and then combines these local views to form the global communities. The experimental results show that the proposed algorithm can not only scale to large networks with good computational efficiency, but can also improve the similarity of detected communities to the ground truth.4. In community evolution tracking, we propose an incremental and local dynamic algorithm, named as local dynamic method for community evolution tracking. This algorithm has two steps: 1) to efficiently obtain the community structure of a dynamic network at each time, this algorithm only focuses on the nodes of change, and updates the community structure by exploring the local views of these nodes of change; 2) to efficiently match the community structures at two consecutive times for tracking the evolutionary behaviors of communities, this algorithm constructs a partial community evolution graph based on the node-community memberships of nodes of change before and after the network change, and tracks the evolutionary behaviors of communities by searching the partial community evolution graph. The experiments show that, when the network changes smoothly, the proposed algorithm is capable of tracking community evolution with less running time than the algorithms compared; when the network changes dramtically, the proposed algorithm also has some advantages.