Dynamic community detection method based on an improved evolutionary matrix

摘要

Most of networks in real world obviously present dynamic characteristics over time, and the community structure of adjacent snapshots has a certain degree of instability and temporal smoothing. Traditional Temporal Trade-off algorithms consider that communities found at time t depend both on past evolutions. Because this kind of algorithms are based on the hypothesis of short-term smoothness, they can barely find abnormal evolution and group emergence in time. In this paper, a Dynamic Community Detection method based on an improved Evolutionary Matrix (DCDEM) is proposed, and the improved evolutionary matrix combines the community structure detected at the previous time with current network structure to track the evolution. Firstly, the evolutionary matrix transforms original unweighted network into weighted network by incorporating community structure detected at the previous time with current network topology. Secondly, the Overlapping Community Detection based on Edge Density Clustering with New edge Similarity (OCDEDC_NS) algorithm is applied to the evolutionary matrix in order to get edge communities. Thirdly, some small communities are merged to optimize the community structure. Finally, the edge communities are restored to the node overlapping communities. Experiments on both synthetic and real-world networks demonstrate that the proposed algorithm can detect evolutionary community structure in dynamic networks effectively.