Research On Community Detection Algorithms And Applications In Complex Networks

Complex networks can express complex systems widely existing in the real world in the form of networks,such as social networks,biological networks,traffic networks,etc.The research in this field has not only attracted a large number of researchers from the fields of management science,computer science and physics,but also aroused great interest of scholars in sociology and biology.Complex network research has become an important interdisciplinary research hotspot.With the rapid development of big data and technology,it is possible to obtain and deeply mine network data.Many studies have shown that there is community structure in complex networks,which has the characteristics of tight connections among nodes within communities and sparse connections between nodes among communities.The purpose of community detection is to discover the real community structure in the network,which helps to understand the relationship between individuals within the community and between different communities.It also provides a basis for the study of other properties and functions in the network,such as disease transmission,message dissemination,recommendation system,etc.In recent years,many different types of community detection algorithms have been proposed,mainly based on modular optimization,stochastic probability model,spectrum theory and Markov chains to detect community.With the increasing scale of network size and the wide application of community structures,the higher requirements for the accuracy and efficiency of community discovery algorithms are put forward.Moreover,due to the diversity of node roles,non overlapping community detection can not meet some specific needs.How to design a quick and accurate algorithm to discover overlapping community structure is also one of the problems to be solved.Therefore,starting from the local topology of the network,this paper deeply studies the network topology,and the main researches are as follows.At first,the local topology characteristics of the network are deeply analyzed,and the index to measure the node similarity is proposed.By using the principle of node similarity,the closely connected node sets are quickly mined,which provides a scientific and reasonable pre partition method for obtaining accurate community detection results.According to the different requirements of node similarity degree,it can detect the node sets with different degree of connection tightness,and based on these results can help us get optimal solution.In the optimization stage of network pre partition results,the local topology fusion optimization and the global multi-objective function optimization are studied respectively.A two-stage community detection algorithm based on divide and agglomerate(DA)stages and an algorithm based on multi-objective evolutionary algorithm under network precompression(Com-MOEA/D)are proposed.In the aggregation stage of DA algorithm,after analyzing local network topology,community attractiveness index is designed,and modularity function is integrated for optimization.A large amout of experimental results on real networks and computer-generated networks show that DA algorithm has high accuracy,especially when the community structure is fuzzy.In addition,DA algorithm can show advantages in ego-network.According to the different requirements of node similarity,Com-MOEA/D algorithm proposes a threshold parameter of node similarity,and compresses the closely connected node set into a super node,thus reducing the scale of the original network and forming a compression network with self-loop structure.In the process of community detection for compressed networks,multiobjective evolutionary algorithm based on decomposition is used to solve the problem.The comprehensive consideration of multiple objective functions can bring a group of community detection results.An optimal solution can be selected according to different objective functions.The experimental results also verify the effectiveness of the algorithm.In the second,due to the diversity of roles of nodes in the network,each node may belong to multiple communities.An overlapping community detection algorithm based on expanding and adjusting the cores of communities is proposed.The basic idea of the algorithm is to first find the core group structure in the network to replace most of the seed nodes in the algorithm.Then,on the basis of the core group structure,according to the local topology information of each node,a node is designed to join the willingness index,and the nodes are selected according to the size of the index value for the rapid expansion of the local community;then,the social solidarity obtained in the local expansion stage is analyzed According to the contribution of the node in the corresponding community,the membership coefficient of the node is designed,and the node is adjusted according to the membership.This algorithm does not use the traditional adaptive function in the local expansion,so it has high efficiency.In the adjustment stage,the results are fine tuned according to the contribution of nodes,which increases the accuracy of the results.Through many experiments in real network and artificial network,compared with other similar classical algorithms,coreocd algorithm has a strong advantage in overlapping community discovery.Finally,based on the community structure,a target immune strategy using genetic algoirhtm(Com＿GIM)is proposed.Community is widely used in disease transmission,information dissemination and recommendation system,especially in the process of disease transmission,the virus within the community spreads faster,and the propagation speed between communities is slightly slower,which needs the help of bridge nodes.Therefore,this paper uses the DA algorithm to divide the community of the network.On the basis of obtaining the community structure,based on the nonlinear dynamic model of disease transmission,the immune problem of the target node is transformed into the optimization problem of the maximum eigenvalue of the network adjacency matrix.In fact,this problem is similar to the problem of maximizing the influence of node set in the network.Therefore,this algorithm is compared with other related node influence maximization algorithms and important node selection algorithms in the experiment.The results show that the algorithm has high accuracy and can find the node set with the strongest propagation force to immune.