Research Of Community Detection Algorithms

The research of complex network involves many fields,such as social network,academic network,world wide web,protein interaction network and so on.Mining community structure is a key tool to study complex system.The discovery of complex network community structure is of great significance to analyze the topological structure of complex network,understand the function of complex network,discover the hidden law in complex network and predict the behavior of complex network,especially for community detection and search algorithms in the large-scale complex network.In this thesis,the community detection method is studied.The following is a description of the main work and contributions:(1)To give solutions to the problems of initial node dependency and candidate node detection in local community detection algorithm,a two-stage breadth-first traversal algorithm(TSB)based on node transfer similarity and existed local clustering is proposed.The algorithm process is divided into two stages,including core community detection stage and community expansion stage.The algorithm adds the neighbor of the given node with the largest clustering degree to the initial community;it combines the node similarity,traversal order to put forward the node transfer similarity measure,which is used to measure the connection tightness between the candidate neighbor and the given node,the current core community;it sets the candidate node detection functions and the dynamic thresholds by combing the node transfer similarity,traversal depth and clustering degree,so that it can adapt to different parts of different networks.The experimental results show that TSB algorithm can effectively improve the accuracy of community detection.(2)In order to solve the problem of setting objective function and slow convergence in genetic evolution algorithm,a two-level edge-knowledge learning genetic algorithm for community detection(TELGA)is proposed.In this algorithm,node-level edge-knowledge learning is used to increase the proportion of important edges in the initial individual coding;two kinds of populations are used to strengthen the inner community connection and weaken the connection among communities;according to the coding characteristics of the elite individuals in the population,partition-level edge-knowledge learning can increase the proportion of the internal edge in the population coding,by adjusting the proportion of the edge weight and influencing the population variation process,thus reducing the proportion of the internal edge in the population coding and improving the speed of finding the detection solution.Experimental results show the effectiveness and availability of TELGA.(3)A global community detection algorithm based on incremental non-negative matrix decomposition(CK-INMF)is proposed to solve the problems of non-negative matrix decomposition,such as the large dimension of feature matrix and the difficulty of adding nodes.The algorithm improves the node core weight function,and uses the selected community core nodes to construct the low-dimensional feature matrix;uses the incremental non-negative matrix decomposition to find the community for the newly added nodes,avoiding a large number of repeated calculations,and realizing the dynamic addition of nodes;through the initial community obtained by the decomposition of the combination matrix,the final community detection result is obtained.Experimental results show that CK-INMF can effectively improve the performance of the algorithm.