Node Similarity Study Of Complex Networks Based On The Relative Entropy Of Multi-order Path Distribution

Complex network is an important modeling method for complex systems,which has been widely studied and applied.The similarity of nodes in complex networks can reflect the connection mode and structural characteristics of the network to a large extent and plays a very important role in understanding the attributes of the network.It helps researchers to deeply analyze the complex network topology and understand the network functions,and then discover and expose the potential laws within the network.Therefore,the similarity of nodes in complex networks has become an important research topic.At present,researchers have proposed some models to measure the similarity of nodes in complex networks: For example,based on the similarity model of common neighbors,this type of method only considers the information of common neighbors of nodes,and many similar nodes in many real networks do not have common neighbors,so this measurement method has certain limitations;The similarity model based on path and the similarity model based on random walk,although the measurement effect is good,has also been recognized by the researchers,but there are problems of large degree nodes dependence or computational complexity.How to reduce the dependence of similar nodes on large degree nodes and enhance the computational feasibility is a problem that researchers need to consider;The node similarity measurement model based on structural relative entropy is a method that has attracted much attention in recent years.At present,there are few studies on this kind of methods,and the information considered by the existing methods in constructing the probability set of structural characteristics is not sufficient.Although the current research on the similarity of complex network nodes has achieved some good results,these existing nodes similarity measurement methods have different degrees of deficiencies.In this thesis,the similarity algorithm of nodes is studied.In view of these shortcomings,the following two methods are proposed.(1)Considering that the traditional nodes similarity measurement model has the problems of excessive dependence on large degree nodes and high algorithm complexity,this thesis proposes a similarity measurement model based on the relative entropy of the mixed k-order path distribution.The model combines information entropy and network k-order structural features to analyze the similarity of network nodes.Firstly,the k-step walking path of the node is traversed according to the distribution of the nodes,and the k-order path matrix is constructed;Then,according to the k-order path number matrix,the probability set is constructed to define the relative entropy to compare the similarity of the two nodes;Finally,the mutual similarity ratio,average aggregation coefficient evaluation index and propagation influence model are used to verify the measurement effect of the model.Experiments show that the proposed model has obvious effect on the measurement of nodes similarity,the time complexity of the algorithm is low,and the problem of dependence on large nodes is effectively avoided.(2)The similarity measurement model based on local information only considers the shallow neighborhood information of nodes,which leads to the insufficient similarity of nodes.The similarity method based on global information is too complex and difficult to calculate for large networks.This thesis proposes a similarity measurement model based on pure k-order path distribution relative entropy.Firstly,the matrix iteration idea and the shortest path are used to judge the path;Then,the pure k-order path matrix with non-repeatable edges and points is calculated,and the k-order path distribution is obtained;Finally,combined with information entropy,using the k-order path probability distribution matrix between nodes and nodes,and the location information of nodes in the network,the relative entropy of multi-order path distribution of nodes is calculated,and the similarity matrix is obtained,and then the similarity between nodes is evaluated.Compared with the existing measurement model experiments,the proposed algorithm shows obvious advantages in each index evaluation.