Research On The Fast Community Mining Algorithm Based On Distance Dynamics

Most complex systems in the real world can be abstracted as networks.Complex networks and network science can provide us with important theoretical basis and diverse research methods for studying these systems.In real complex systems,the community structure is a ubiquitous network structure characteristic.It is closely related to the functional units of networks and the dynamic process on networks,and is one of the hotspots of network scientific research.To this end,scholars have proposed a large number of community detection algorithms to mine the community structures in networks,trying to better understand complex systems.As the scale of the system continues to increase and the interaction between individuals in the system gradually becomes more complex,being able to accurately and quickly mine the community structures in complex systems is still the purpose of many community detection algorithms.Here we focus on the fast detection algorithm of community structures in large-scale social networks.Based on the distance dynamics model with synchronized viewpoints on social networks,this thesis makes two improvements to the Attractor algorithm based on the distance dynamics model by studying the distance trend among nodes.The content of this thesis mainly includes the following two aspects:1)A fast community detection algorithm based on the trend of the change in the distance between connected nodes is proposed.According to the phenomenon that the distance change trend of most nodes in the distance dynamics model always remains unchanged,with "distance change trend determining the final value of distance" as an improvement idea,a fast Attractor community detection algorithm based on the trend of the change in the distance between connected nodes is proposed.Specifically,the algorithm sets a sliding time window and uses the distance trend displayed in the window as the basis for determining the final stable value of the distance.Through experiments on the synthetic networks and real-world networks,it is verified that the algorithm proposed in this thesis can not only maintain the accuracy of communities obtained by Attractor,but also significantly reduce the number of iterations required for the distance convergence,thereby improving the computational efficiency of Attractor.2)A fast community detection algorithm for mining community structure based on the heterogeneity of convergence speed in the distance between connected nodes is proposed.Based on the different convergence speed of node pairs,this thesis proposes a new distance dynamics improvement algorithm by combining the distance change trend and the distance convergence status around the point pair.The algorithm can not only accelerate the Attractor algorithm,but also solve the problem that the accuracy of the using the trend to determine the final value of the distance on a network with complex community structure is not high.Our algorithm proposes three kinds of judgment rules.First,find the node pairs whose distance changes slowly,and then judge the final distance value in advance according to the surrounding distance convergence state.At the same time,for a community that contains only one node,an optimization rule is proposed according to the different distance convergence rates of the nodes in the single-node community and the surrounding neighbors to reduce the number of communities with only one node.Through comparing experimental results with other five classic algorithms on synthetic networks and real-world networks,it is found that the improved algorithm can accelerate the speed of the Attractor algorithm while maintain high community detection accuracy.It is also effective in networks with complex community structures.