Research On Community Structure Detection Algorithms In Complex Networks

In recent years,with the rapid development of mobile Internet technology,more and more data has been presented in the form of complex networks,and people's lives are also in various complex networks.Therefore,how to analyze and study the characteristic laws hidden behind complex networks has become a hot issue of general concern in academia and industry.With the advancement of complex network analysis techniques,the ‘small world' features,scale-free features and community structure features of complex networks have been discovered.Among them,community structure characteristics are the most important feature structure in complex networks.In general,a community structure means that the connections between its internal nodes are relatively close,while the connections between nodes in different communities are relatively sparse.Discovering the community structure in a complex network helps people understand the functional organization and topology within a complex network,and then find out the underlying evolutionary laws,providing a basis for explaining some natural phenomena.In addition,community detection results can be applied to areas such as personalized recommendations,link predictions,and hotspot mining.Therefore,community detection has important theoretical and practical significance for the research and application of complex networks.Community detection and local community detection are the main methods for mining and analyzing the rules and characteristics of complex networks.Community detection refers to dividing all nodes into different communities according to the topology or node attribute information of complex networks,and requires global information of complex networks.The essence of community detection is the process of clustering nodes in a complex network.The local community detection starts from a given one or more query nodes,and only needs to use the local information of the complex network to quickly discover the community structure to which the query node belongs.As local community detection can effectively abandon the high space-time expenses brought by community detection and is more in line with real needs,it has received more and more attention.This thesis mainly focuses on community detection and local community detection in complex networks.The main work and innovations are as follows:Firstly,in the aspect of robustness of community detection algorithm,in order to solve the problem that the parameter selection is sensitive,easy to generate outlier nodes and unable to identify hub nodes of the traditional dynamic distance model,a robust dynamic distance model based on membership degree and corresponding community detection algorithm called Attractor++ has been proposed.The Attractor++ algorithm uses dynamic membership degree to determine the influence of exclusive neighbors on distance,without setting parameters manually,which greatly improves the robustness of traditional dynamic distance model.Furthermore,the Attractor++ algorithm uses the optimization rules of the outlier nodes and the discovery rules of the hub nodes based on the important characteristics of the triangular structure in the complex network,according to the adjacency and connection characteristics of the triangle structure,which greatly reduces the number of outliers nodes and also achieves the ability to detect hub nodes.Through the trial and error on the real network dataset and the artificial test network,the effectiveness of the Attractor++ algorithm is not only more effective in discovering the community,but also more accurate identification of abnormal nodes and hub nodes.Extensive experiments on both real-world and synthetic networks demonstrate that our algorithm more accurately identifies nodes that have special roles(hubs and outliers)and more effectively identifies community structures.Secondly,in the aspect of dynamics of local community detection algorithm,in order to solve the “free rider” problem that leads to the final local community easily falling into local optimal trap and easy to associate with a large number of multi-hop far nodes of the commonly used local community detection methods,a novel local community detection algorithm K-Hop based on the local distance dynamics model has been proposed.The K-Hop algorithm does not depend on any objective function and considers local community detection from a new perspective: local dynamic distance.The basic idea K-Hop algorithm is to envision the nodes which k-hop away from the query node as an adaptive local dynamical system,where each node only interacts its local topological structure.In order to simulate this interaction,a local dynamic distance model is designed.Relying on a proposed local distance dynamics model,the distances among node will change over time,where the nodes sharing the same community with the query node tend to gradually move together while other nodes will keep far away from each other.Such interplay eventually leads to a steady distribution of distances and a meaningful community is naturally found.Extensive experiments on both synthetic networks and a variety of large real-world networks demonstrate the effectiveness and efficiency of our community search algorithm and has good performance compared to state-of-the-art algorithm.Thirdly,in the aspect of high-order structure of local community detection algorithm,in order to solve the problem that the traditional local community detection algorithms are simply focused single nodes or edges and did not account for the higher-order structures crucial to the complex networks,a high-order local community detection algorithm FuzLhocd based on dynamic fuzzy membership function has been proposed.Firstly,for the global search problem caused by traditional high-order structural conductance,a local high-order structural modularity has been proposed.Then,based on the local high-order structural modularity,a high-order local community detection algorithm GloLhocd with global fuzzy membership function is proposed.In order to further improve the performance of GloLhocd algorithm,we systematically studied the formation of the local community,divided the process of local community detection into three stages and employed various fuzzy membership functions at different stages.Finally,a fuzzy agglomerative algorithm FuzLhocd for local higher-order community detection based on different fuzzy membership functions has been proposed.Our extensive experiments based on both real-world and synthetic networks demonstrated that FuzLhocd not only runs efficiently locally but also effectively solves the seed-dependent problem and achieves a high accuracy as well.We concluded that our local motif modularity metric and FuzLhocd algorithm is highly effective for local higher-order community detection.Fourthly,in the aspect of efficiency of local community detection algorithm,in order to solve the problem that can not efficiently detect local communities of the global clustering algorithm,a local community detection algorithm LSync based on local synchronization model has been proposed.In order to enable local community discovery on low dimensional vector datasets,a local synchronization model has been proposed.Then,based on the local synchronization model,a local clustering algorithm LSync is proposed.The LSync algorithm first determines the local oscillation range according to the neighborhood where the query data object is located.Then,based on the local oscillation synchronization model,the data objects in the neighborhood will gradually become synchronous under the influence of the coupling force,and finally gather with the query data object and a meaningful community is naturally found.In addition,in order to reduce the synchronization time step of the LSync algorithm,a neighborhood closure has been proposed to instead of the traditional clustering order parameter,which can predict the formation of local clustering before the data objects are fully synchronized.The performance of LSync algorithm is evaluated on several real-world and synthetic networks and the experimental results show that the proposed local synchronization model is not only correct and effective in finding the local community of data objects,but also greatly reduces the time steps required for synchronization.