Research On Community Discovery Algorithms In Complex Networks

Complex network exists widely in all aspects of social life,characterized by the high density of the link between nodes in the module,while the nodes between modules show the low density of the link.The model of complex network system has gradually evolved from the original form of data statistics into a scientific research method,which has become one of the research hotspots in many interdisciplinary disciplines and fields,and has attracted the great attention of many experts and scholars at home and abroad.Community,as an important index to describe complex networks from a medium perspective,is gradually becoming one of the fundamental problems in the frontier of complex network research.Community structure is a common phenomenon in complex networks.For example,the community of friends based on the strong relationship network Facebook can effectively improve and promote the intimacy between individuals;the information dissemination community formed by the weak relation network Twitter is beneficial to the delivery and promotion of commercial advertisements.Community discovery can find the potential structure of the network,deeply explore the hidden information inside the network,detect the change of the network topology,but also reveal the inherent law of the network,track the dynamic evolution of the network structure,predict the development trend of the network,and be of great significance for understanding and mastering the basic characteristics of complex network structure.Based on the analysis of related work,this dissertation focuses on the time neighborhood characteristics of complex networks,the properties of nodes themselves,the dynamic diffusion process and the overlapping phenomenon,and the main research contents and contributions are as follows:(1)A dynamic discovery algorithm for community structure is proposed based on the time locality principle of nodes.Many traditional complex network community discovery algorithms regard the global attributes of the network as fixed,but with the development of time,various predictable or unpredictable factors from inside or outside the network will lead to different degrees of changes in the structure and nature of the network.Inspired by the local theory of space-time of executing programs in computer operating system,this dissertation innovatively introduces the time local access principle into the community discovery of complex networks for the first time to solve the problem of dynamic expansion of network structure.That is,if a community accepts a node as its member at some time,more subsequent nodes in the adjacent time intervals will visit the community first,rather than other communities.Through the benchmark network test and analysis,the proposed community discovery algorithm can detect the community structure with changing characteristics more efficiently and accurately.(2)A parallel heuristic community discovery algorithm based on the weight influence factors of different neighbor nodes is proposed.The topological properties of complex networks usually determine the internal structure of communities,and the intrinsic properties of nodes themselves play an important role in the local fine-tuning of community division,but most community discovery algorithms do not fully consider this important feature.Therefore,a secondary decision rule is designed to detect the similarity of nodes,that is,when calculating the interaction between neighbors,according to the different node neighbor types,the calculation criteria for determining the similarity of nodes is redefined to change the network weight of different types of neighbors with common neighbor nodes.On this basis,a hash table strategy with minimal probability of collision is introduced to store and retrieve the triple information of nodes.Through the performance comparison test between different algorithms,the problem of community prediction accuracy in large networks is solved,and the time complexity of calculation is greatly reduced.(3)A multi-scale community discovery algorithm is proposed based on the temporary local balance strategy in the process of network dynamic diffusion.In view of the intrinsic dynamic characteristics of the network,the structure of the network will exhibit different local or global characteristics under different time detection scales.Through research,it is found that there is a short-term local stable state in the dynamic diffusion process of the network,it may not immediately attenuate to the next local state,but will appear intermittent stagnation.This phenomenon is closely related to the community structure in the network,i.e.,the change of the structure determines the community division under different time scales.It is proved by experiments that the temporary local balance strategy proposed in this dissertation can obtain a relatively stable local non-attenuation region in the process of dynamic evolution,which can be used to detect the community structure in the network.Furtherly,because the strategy is based on multi-scale community state detection of dynamic diffusion process,it can effectively avoid the problem of resolution limit in the process of modularity maximization.(4)A heterogeneous overlapping community discovery algorithm based on node influence in network is proposed.In the complex network with the structure of heterogeneous characteristics(i.e.,the degree distribution of network nodes presents the power-law characteristic),most nodes have relatively few edge connections,while only a very small number of nodes have a large number of node-degree distributions.A relatively small number of nodes in the network have the characteristics of priority connectivity,which inevitably exists some network nodes belonging to multiple communities at the same time,resulting in the occurrence of overlapping phenomenon.Therefore,this dissertation proposed a network probabilistic prediction model to capture the influence of such nodes,which deduces the community division in line with objective facts by constructing a posteriori community strength and node influence probability model.In addition,a new non-conjugate stochastic variational inference rule based on the mean-field family variable is introduced to strictly deduce and demonstrate the proposed link probability prediction model from a mathematical point of view,and solve the transformation of the proposed algorithm model to application practice in the process of community discovery.With the help of flexible sub-sampling of the network data involved in the calculation,the computational complexity needed in processing large-scale networks is further reduced.