Label propagation based evolutionary clustering for detecting overlapping and non-overlapping communities in dynamic networks

摘要

Since real-world networks evolve over time, detecting communities in dynamic networks is a challenging research problem with wide applications. In this paper, we first improve our previous method and propose a more stable algorithm which is label-propagation-based for the discovery of communities in complex networks. Then, we present a novel evolutionary clustering approach DLPAE for dynamic networks based on the stable algorithm. According to 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. 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. Experimental results on both real and synthetic datasets show the ability of DLPAE to detect overlapping and non-overlapping communities in dynamic networks, and demonstrate its higher accuracy compared to other related methods.