Research And Application Of Community Detection Algorithm Based On Node Gravity

The complex network is a network structure composed of nodes and complex relationships between nodes,which is an abstraction of various complex systems in the real world.Community structure is a distinctive feature of complex networks and the community detection algorithm finds the stucture to reveal the topology of the network and mine the potential information in the complex network.Consequently,the algorithm can be widely used in personalized recommendation,public safety,social science and other fields and has important research significance.In this thesis,two improved algorithms are proposed to overcome the shortcomings of common seed expansion algorithm and label propagation algorithm.The main research contents and achievements of this thesis are as follows:(1)Aiming at the problems of poor seed nodes selection and improper community expansion method of seeds expansion algorithm,this thesis proposes a seed expansion algorithm based on CRITIC method and node gravity which called SECNG.Firstly,the CRITIC method is used to objectively enable the weights of the Betweenness Centrality,Closeness Centrality and Degree Centrality of nodes,which defines a node importance index called NCI and select seed nodes according to the decreasing order of the importance index.Then,the concepts of node gravity and community gravity based on node comprehensive importance are proposed.And in the community expansion stage,the nodes that are not divided into communities are extended to the community with the greatest gravity according to the decreasing order of NCI.Finally,this thesis proposes a community optimization method based on modularity increment,which merges the two communities with the largest modularity increment in each iteration to further improves the accuracy of the algorithm.(2)Aiming at the high randomness problem of label propagation algorithm,this thesis proposes a label propagation algorithm based on node influence and node gravitation which called LPANING.At first,the algorithm defines the indicator of node influence NI based on Page Rank and degree centrality,and sorts the nodes in decreasing order to determine the order of label initialization and label update.Then,a node gravitational NGNI based on node influence is defined,thus when a node has multiple candidate labels,the label of the node with the largest node gravity is selected.Finally,the algorithm merges small communities according to community similarity,which improves the stability and accuracy of the algorithm.The experimental results show that SECNG algorithm and LPANING algorithm proposed in this thesis have good performance on multiple groups of artificial networks and real networks.(3)This thesis applies the above two algorithms to a science and technology plan project.The complex network of users is built according to the behavior of reading and personalized recommendation is made to users via the community detection algorithms,so as to promote the spread of mainstream values on the basis of paying attention to user preferences.