Key Nodes Identification And Community Detection In Complex Networks

Recently,with the construction of smart city,the application of complex network is more and more popular.Complex networks can be seen everywhere,such as traffic network,power network,etc.These networks provide great convenience for our life.Key nodes and community detection in complex networks play a very important role in information diffusion,disease control and disaster relief.With the continuous expansion of the network size,some traditional key node and community detection algorithms are difficult to apply on large-scale complex networks due to high time complexity and the difficulty of obtaining global network information.Although the classic key node identification method can identify key nodes to a certain extent,it also has some limitations.In addition,there is potential space for combining community detection with cluster analysis.Therefore,how to more accurately and efficiently identify key nodes and discover community structure is still an important research topic.Based on the complex network theory,this thesis comprehensively considers the local information and location attributes of the network,proposes the concept of node entropy,and proposes two improved key node identification methods based on classic algorithms.Given that the community discovery algorithm is related to the clustering algorithm,this thesis uses clustering as a supplementary method for community detection,and improves the community detection algorithm.The main research contents of this thesis include the following three parts:(1)We propose a structural hole node detection algorithm named ESH based on local attributes.Although the original structural hole constraint coefficient can find the bridge nodes,the importance of nodes with the same constraint coefficient cannot be distinguished.After considering the local information,the local and location attributes of the nodes are reflected in the calculation of the new coefficients.This method avoids the situation where the nodes of the original structure have the same constraint coefficient and the importance cannot be distinguished,and the computation cost is small,which is suitable for large networks.(2)We propose an improved K-shell algorithm named IKS based on node entropy.K-shell assigns the same importance to nodes in the same layer.Studies have shown that the node with the largest core may not be a super spreader.The position of the node in the network is also a crucial factor,and the core nodes obtained by K-shell mining present a typical "rich-clubs" phenomenon.Based on the idea of avoiding the "rich-clubs",IKS iteratively selects the nodes of each core layer according to the node entropy of the network nodes,so as to avoid the overlap of propagation effects and achieve better propagation effects.(3)We analyze the association between community detection and clustering algorithm.After using network representation learning to transform the network into numerical space,the initial central node is selected by the node ranking algorithm in(2),and a community detection algorithm named K-clustering is proposed based on network representation learning.It can be seen from the simulation results of real networks that the K-clustering algorithm is not inferior to other benchmark community detection algorithms.