The Structure Identification For Complex Networks Based On Structural Entropy And Its Applications

In real life,many complex network systems such as social networks,information networks,biological networks,and technological networks can be represented by large-scale graphs.Lots of study has shown that such a complex network can be partitioned into many node groups,which is what we call network partition.Nodes in the same group are more closely related and tend to be connected by edges.Network structure with this topology characteristic is called community structure,and each node group is called a network community.The network structure partition finds many applications in real life.For example,it can be used in recommendation algorithms and railway network analysis for railway design.This thesis first analyzes the research status of community detection at home and abroad,introduces several classic algorithms for complex networks,including GN algorithm,CNM algorithm and Louvain’s algorithm,and points out their advantages and disadvantages.Subsequently,the thesis introduces the concept of structural entropy,and the community partition algorithm based on structural entropy.The main idea of the algorithm is to minimize the two-dimensional structural entropy of the network.This algorithm has high efficiency when dealing with large and complex networks.However,this algorithm has a drawback,that is,the algorithm may easily fall into the situation of local optimal solution,since it is a greedy algorithm.The first main work of this thesis is to propose an improved community partitioning algorithm based on structural entropy.In order to solve the problem of trapping into local optimal solution,this thesis adopts the strategy of simulated annealing.Let p be a probability of taking value in[0,0.5).We split the complex network with probability p,and merge the complex network with probability 1-p.Among them,the merging algorithm plays a dominant role.The merging algorithm adopts bottom-up strategy based on structural entropy.The merging algorithm stop when reaches the optimal solution for a certain number of times.The splitting algorithm is an auxiliary algorithm in the entire simulated annealing process.A simple and efficient splitting algorithm is designed as follows.First,find the node with the least number of connections with other nodes in the community to be split and take it as a peripheral node.Then the algorithm performs breadth-first search starting from this node.The farthest node in this process is selected as another peripheral node.And then all nodes in the community are partitioned according to which peripheral node is closer.The improved community partitioning algorithm based on structure entropy,the original community partitioning algorithm based on structure entropy,and Louvain’s algorithm are compared in terms of two-dimensional structure entropy,modularity and running time.The value of probability p is estimated.The second main work of this thesis is to design a network structure analysis system using the improved structure entropy-based community partitioning algorithm.The system is implemented using the separation technique of front and back-end in Python Flask+ Vue.The asynchronous mechanism of the system is realized using Celery.The system displays the analysis results on the front-end interface.The system mainly consists of the user login registration module,task management module,data analysis module and analysis display module.This thesis tests the network structure analysis system on the paper citation network which is derived from CNKI.The analysis results clearly show the structure of the paper citation network,reveal the research hot spots and research cutting-edge of CNKI papers.The results are of great significance to recognize and understand the research direction and development of papers in CNKI.