Research And Application Of Community Division Algorithm In Complex Networks

Things in the real world can be represented by complex network models,such as social relationships between people,biological relationships between cells,and the link structure between the World Wide Web.Many networks have the communities with close inner associations.Some communities in the network are relatively independent,while some communities are overlapped.Community division is of great significance for understanding complex network structure,analyzing network characteristics and potential relationships.How to quickly,accurately,and efficiently find the community structure in complex network has become one of the hot topics in computer,sociology,and biology.This thesis has conducted research on several classic community division algorithms.In view of the shortcomings of these algorithms,three improved community division algorithms have been proposed.The first proposed algorithm is IJ-CD which is a community division algorithm based on the improved Jaccard similarity coefficient matrix.This algorithm is aimed at non-overlapping community division scenarios with a specified number of communities.The goal is to improve the accuracy and efficiency of community division.First,it calculates the Jaccard similarity coefficient matrix of the network,and expresses some zero elements in the matrix with more reasonable values and does standardization.Then it calculates the eigenvalues and eigenvectors of the matrix,selects the eigenvectors corresponding to the m-1 eigenvalues closest to 1 in turn,and uses these eigenvectors as cluster samples to perform clustering using the K-means algorithm to obtain the community division result.The second proposed algorithm is S-LPA which is a stable label propagation community partitioning algorithm.This algorithm is aimed at non-overlapping community division scenarios with a large amount of data.The goal is to improve accuracy and stability.It uses the improved KShell algorithm to calculate the global influence of the node,and combines the global influence with the degree value which can reflect the local influence of nodes and the information of neighbor nodes to calculate the comprehensive influence of nodes.During the propagation of the label,the label is updated according to the influence of the label.When the labels of all nodes in the network no longer change or the number of iterations reaches the maximum,nodes with the same label are divided into the same community.The third proposed algorithm is LP-OCD which is an overlapping community division algorithm based on label propagation.This algorithm is aimed at large network scale with overlapping community,and the goal is to improve accuracy and stability and reduce resource consumption.During the pretreatment stage,the K-Shell decomposition algorithm is used to remove the edge layer nodes in the network;during the label update phase,the algorithm randomness is reduced by improving the Speaking and Listening strategies;during the post-processing phase,the label of edge layer nodes is determined by its neighbor node information.In this thesis,three proposed algorithms are applied to real network datasets and LFR artificial synthetic networks for performance testing.Experimental results show that each algorithm can achieve the expected results for different use scenarios and effectively divide communities in complex networks.