Research And Implementation Of Community Detection And Evolution Analysis Approaches For Dynamic Networks

Complex networks have attracted more and more attention from people due to their ubiquity and generality of modeling. In real world, the structures of complex networks usually change over time and dynamic networks are formed. It is of great significance to study dynamic networks owing to their high potential in capturing natural and social phenomena over time.Traditional clustering methods for dynamic networks usually clustering at each timestamp,and analyze the evolution of communities belong to adjacent timestamps. However, clustering with this strategy does not take the temporal character of dynamic networks into consideration. Therefore, it can hardly trace the evolution of communities. Motivated by this observation, in this paper, a local-first evolutionary clustering approach LEOD and a label-propagation based evolutionary clustering approach DLPAE are proposed. According to LEOD, for each vertex of a network, its Ego communities are firstly detected by a label propagation approach. Then these local Ego communities are merged and form the final community structure of the network. In the merging process, two concepts of community similarity and community association rate are introduced. By taking advantage of the framework of evolutionary clustering, an algorithm for detecting overlapping communities in dynamic networks is proposed. As for DLPAE, community labels of nodes are determined by their neighbors, and a confidence(i.e., the importance of its neighbor to the node) is attached to each neighbor. During clustering, the confidences of nodes are calculated in terms of the structures of the current network and the network at last timestamp.We compute confidences' variance of each node and update nodes' labels in a descending order according to the values, which leads to a high stability and accuracy of the result. In our setting, each node can keep one or more labels with belonging coefficients no less than a threshold, which renders DLPAE suitable for detecting overlapping and non-overlapping communities in dynamic networks simultaneously.We perform extensive experimental studies, on both synthetic datasets and real datasets, to evaluate the performance of the proposed algorithms. Experimental results demonstrate that LEOD can effectively detect overlapping communities in dynamic networks and discovery the potential information in networks; DLPAE has the ability to reveal the overlapping communities and non-overlapping communities in dynamic networks simultaneously; Our algorithms show higher performance compared to other related methods.