Research On Community Detection Algorithm Based On Node Importance

Community structure represents a group of nodes with same attributes in the complex network,which can reveal the hidden attributes and interaction rules in networks.It is significant in theory and practice to identify and analyze the community structure of the network,which is conducive to a deeper understanding of the network,and a further exploring the evolutionary rules of individuals and predicting the behaviors in a more accurate way of networks.Modularity optimization algorithm and label propagation algorithm are two typical community detection algorithms.In the two algorithms,each node is regarded as an independent community,which leads the calculation of modular optimization algorithm time-consuming.Meanwhile,the random selection of the target label results in the poor stability of the label propagation algorithm.Aiming to improve the existing problems of the above two algorithms,this thesis proposes two improved algorithms based on the node importance in the network,respectively.(1)Improved community detection algorithm based on node importance and modularity optimization algorithm.Firstly,preprocessing is implemented on the network to combine the nodes with degree valued one.Then we rank the nodes according to node importance,where a certain number of nodes with the highest degree value are utilized as the center of expansion.At last,the initial community structures are regarded as nodes and a new graph is formed.Nodes are iteratively merged in the new graph until final community structure is obtained.Seven node importance ranking algorithms are adopted to sort the nodes.Empirical experiments are carried out based on 4 real networks and 1 synthetic network.Simulated results show that the improved algorithm can effectively find the community structure in the network.(2)Improved label propagation algorithm based on node importance and modularity.Firstly,labels are no more allocated to the nodes at the initial time,and an initial partition is carried out quickly and accurately to reduce the number of labels.Then labels are updated according to node importance to avoid the influence of unimportance nodes in the label updating processes.If there are more than one candidate labels,the node importance is considered to select the accurate node.Empirical experiments are carried out based on 4 real networks and 1 synthetic network.Simulated results show that the improved algorithm can detect the community structure stably and accurately,and the modularity value and NMI value out perform better than other comparable algorithms.