Study On Synchronization-Inspired Community Detection And Its Application

Many complex systems in the real world can be represented or analyzed by the complex network.Community detection is becoming one hotspot with important research value and significance in the field of complex network.It can help us to analyze the organizational structure,relationship between individuals and individuals,evolution dynamics,and functional behavior of complex network.Many studies indicate that multiple dynamic group cooperative phenomena have hidden in the evolution process of complex systems,such as the spin phenomena of the particles,the random walk phenomena in the spread of smell,the synchronization phenomena of the firefly flashing,etc.Therefore,dynamic community detection algorithm based on the group cooperative phenomena or related theory has become a hot research topic.With the development of real-world systems,community detection is facing some new challenges,such as "the overlapping feature of multiple communities","the large-scale even very-large-scale feature of complex network",and so on.Thus,this paper starts with the synchronization phenomena and the related theory,further compares with two different synchronization-Inspired dynamic models,and finally carries out our research based on latest distance dynamic model which was proposed in 2015.The main research work is as follows:(1)The traditional community detection algorithms based on the distance dynamics model can only detect the disjoint community structure of complex network.To identify the overlapping structure of the network using the distance dynamics model,an overlapping community detection algorithm based on the Link Graph is proposed.Firstly,our algorithm transforms the original graph to the Link Graph(a new edge graph),where each edge of original network will become a new node of Link Graph.The purpose of this transformation is to assure the existing of multiple distances between two nodes of original network.Secondly,"indirect neighbor" and"neighbor attraction" are introduced to improve the distance dynamic model.The purpose is to enhance the interaction speed and robustness of the model.Thirdly,based on the improved model,a dynamic interaction process is introduced to detect the disjoint community structure of Link Graph.Finally,the disjoint community structure of Link Graph is converted to the overlapping community structure of original network,the overlapping nodes in the network can be naturally detected.Extensive experiments are conducted on the multiple synthetic networks as well as real-world networks.The results show the effectiveness and rationality of our algorithm.Moreover,the case study on a high school friendship network further proves that our algorithm can accurately find the overlapping community of the network and detect the overlapping nodes.(2)To further enhance the robustness of the distance dynamic model,replace the sensitive parameter ?,we design an enhanced distance dynamics model based on the Ego-Leader,and propose the corresponding community detection algorithm.Firstly,inspired by the natural synchronization process,our algorithm introduces the definition of Ego-Leader,and thinks that there are some Leaders in the neighbors of one node that determine the movement direction of this node in the synchronization process.Secondly,we design an enhanced distance dynamics model,where Ego-Leader is used to replace the sensitive parameter ? for improving the robustness of the model.In the enhanced model,if two non-directly linked nodes share the common Ego-Leader,we believe that these two nodes will be close to each other in the synchronization process,and vice versa.Finally,to improve the accuracy of finding outlier,two outlier optimization rules based on the Ego-Leader and structure connectivity are developed.Based on two optimization rules,an outlier post-processing is introduced to improve the accuracy of the finding outlier,and reduce the number of the outlier.Experimental results on multiple synthetic networks as well as real-world networks demonstrate the effectiveness and robustness of our algorithm.(3)To detect the community structure of a large-scale network with high speed and high quality,a fast community detection algorithm based on the distance dynamics model is proposed.Firstly,we analyze the high time complexity of distance dynamics model in the large-scale network.Secondly,we develop two prejudgment rules and the strategy of internal edge prejudgment to quickly predict the internal edges of the network.The purpose is to reduce the number of edges that participate in the dynamic interaction process for increasing the speed of community detection in the large-scale network.Thirdly,based on the strategy of internal edge prejudgment,we further reduce the neighbors that need to interact with each edge in the dynamic interaction process.The purpose is to accelerate the speed of dynamic interaction process.Finally,we give the definition of triangle distance,use the known distances of two real edges to measure the distance of the virtual edge between two non-directly linked nodes without any extra computation.The purpose is to reduce the extra computation for the initial distance of all exclusive neighbors,overcome the problem whereby "the distance of exclusive neighbors is unchanged forever",and further enhance the speed of the dynamic interaction process.Experimental results on multiple synthetic networks as well as real-world networks show that our algorithm can detect the community structure of the large-scale network with high speed and high quality.(4)Extensive experimental results indicate that our fast community detection algorithm is not applicable for the very-large-scale network where the number of edge is reaching to 100 million.For that,we propose a parallel community detection algorithm based on the distance dynamics model,and use the strategy of"divide-and-conquer" to identify the community structure of very-large-scale network.Firstly,based the idea of "dividing",we parallel divide a very-large-scale network into thousands of sub networks.Secondly,the convergence threshold and pre-judgment coefficient are adopted to improve the distance dynamics model.The purpose is to reduce the time steps of dynamic interaction process,and overcome the slow-convergence problem.Thirdly,based on the idea of "conquering",we parallel perform the dynamic interaction process independently in each sub network,to calculate the final distance of each edge in each sub-network.Finally,based on the idea of "combining",we collect the edges with long distance from all sub networks to form the set of external edges of the original very-large-scale network,and thus detect the community structure of the network.Experimental results on multiple real-world networks as well as synthetic networks demonstrate the effectiveness and accuracy of our algorithm.