| Effective node similarity measures are helpful to understand and analyze network topology and behavior characteristics,discover propagation law of information,epidemic and rumor in the network.The global node similarity measures use path related information between nodes to compute similarity,which has high computation cost and is easy to make nodes with large degree become the general similar nodes.The local node similarity measures utilize neighborhood related information to measure node similarity,which reduces computational dimension and helps to analyze the topology structures of large scale networks.However,there are currently some local method problems,for example,the node similarity measures based on common neighbors only compute local information for nodes at distances no greater than two,so that the structural differences between nodes is not distinguishable.In this paper,we research the problems of local node similarity measures and propose two node similarity measures based on relative entropy.The main works are as follows:(1)When measuring nodes similarity based on the traditional random walk similarity metrics,nodes tend to be similar to nodes with large degrees.In order to solve the problem,a random walk similarity measure model based on relative entropy is proposed from the perspective of information theory,abbreviated as RE-model.Firstly,we generate a transition probability set for each node based on random walk measures and calculate the relative entropy between the probability sets of each pair of nodes,then we construct the transition probability distribution for each node based on the transition probability of reaching nodes with large degree after a few steps in random walk,and calculate relative entropy between probability distribution of each pair of node to measure nodes similarity.RE-model method reduces their sensitive dependence to nodes with large degree.We compare traditional random walk measures over 22 real network datasets,and show the proposed RE-model measure outperforms the other measures in terms of symmetry,network spreading and community detection on most networks.(2)In order to solve the problem that is difficult to distinguish the structural differences between highly similar node pairs for existing node similarity measures,we propose a node similarity measure in networks based on local connectivity relative entropy,abbreviated as LCRE.Firstly,we construct the local network for each node using subgraph derived by the closed neighborhood of nodes with finite steps,and define a probability set for each node based on the connected components in its local neighborhood.Then we calculate the relative entropy between the probability sets of each node pair and obtain the node similarity from the resulted relative entropy.The proposed LCRE measure quantifies node similarity from the viewpoint of taking consideration of connectivity information of the local structure of a node.There may be break the "degeneracy of the states" and solve the problem that nodes tend to be similar to nodes with large degrees,which makes the similarity scores more distinguishable.We compare our LCRE method with some node similarity measures in terms of symmetry,network spreading and node influence on most networks.Experiments show that the proposed LCRE measure would measure node structural similarity more accurately. |
