Fast Community Detection Based on Distance Dynamics

摘要

The distance dynamics model is excellent tool for uncovering the community structure of a complex network.However,one issue that must be addressed by this model is its very long computation time in large-scale networks.To identify the community structure of a large-scale network with high speed and high quality,in this paper,we propose a fast community detection algorithm,the F-Attractor,which is based on the distance dynamics model.The main contributions of the F-Attractor are as follows.First,we propose the use of two prejudgment rules from two different perspectives:node and edge.Based on these two rules,we develop a strategy of internal edge prejudgment for predicting the internal edges of the network.Internal edge prejudgment can reduce the number of edges and their neighbors that participate in the distance dynamics model.Second,we introduce a triangle distance to further enhance the speed of the interaction process in the distance dynamics model.This triangle distance uses two known distances to measure a third distance without any extra computation.We combine the above techniques to improve the distance dynamics model and then describe the community detection process of the F-Attractor.The results of an extensive series of experiments demonstrate that the F-Attractor offers high-speed community detection and high partition quality.