# Link Prediction Based on the Derivation of Mapping Entropy

Authors: Hefei Hu; Yanan Wang; Zheng Li; Yang Tian; Yuemei Ren
Journal: Complexity
 (2021)

---

## Abstract

The algorithms based on topological similarity play an important role in link prediction. However, most of traditional algorithms based on the influences of nodes only consider the degrees of the endpoints which ignore the differences in contribution of neighbors. Through generous explorations, we propose the DME (derivation of mapping entropy) model concerning the mapping relationship between the node and its neighbors to access the influence of the node appropriately. Abundant experiments on nine real networks suggest that the model can improve precision in link prediction and perform better than traditional algorithms obviously with no increase in time complexity.


---

## Body

## 1. Introduction

A large number of complicated systems in nature can be described by complex networks [1]. The nodes in the network represent the individuals in the real system, and the edges connecting two nodes represent the relationships of the individuals in the real system. The existing networks in the world can be divided into social networks, biological networks [2, 3], and so on. Link prediction evaluates the possibility of the link between two nodes in the network by the known network structure or node attributes. Through link prediction, we can find the links existing but unknown in the network which misses some data. Besides, we can also predict the possible links in the coming evolution of the network [4]. Link prediction plays an important role in practical application. For instance, through link prediction, the unknown interaction between proteins is predicted, which avoids the high experimental cost [5]. Furthermore, it also plays a role in user recommendation [6].In the early period, most researchers engaged in link prediction focused on the similarity of the attributes of nodes such as age, occupation, interest, and so on [2, 7] to judge the possibility of links. This method can achieve high-precision prediction. However, it is difficult to extract the attributes of nodes in complex networks, and the reliability of information is hard to assure [8]. So, researchers turned their attention to the study of network structure [9, 10] which has relatively low computational complexity.Algorithms based on the similarity of the network structure can be divided into three categories: local similarity algorithm, global similarity algorithm, and quasilocal similarity algorithm according to the path length [11]. The core idea of local similarity is common neighbors. On this basis, considering the influence of endpoints from different angles, a variety of local similarity indices is derived. For instance, common neighbor (CN) index [12] considers that if two nodes have more common neighbors, then they are more likely to have connected edges. Adamic-Adar (AA) index [13] holds the idea that the common neighbor with small degree has a greater contribution. Accordingly, each node is given a weight. Because these local similarity indices only consider the local structure of the network which lead to low precision, the third-order and higher-order path similarity indices were proposed such as Katz index [14]. Katz index considers all paths of two unconnected nodes in the case of short path priority. There is no doubt that this greatly increases the computational complexity. Compared with the above two kinds of algorithms, the quasilocal similarity algorithm with moderate complexity and precision is more and more widely applied. Superposed random walk (SRW) index [15] is one of the indices based on the Markov model.In traditional algorithms, only the degree of endpoint is considered when we evaluate the influence of it. This considers the influences of neighbor nodes to the same extent which loses the impacts of indirect neighbors [16, 17]. In fact, due to the different degrees of neighbors, their influence on the endpoint should be different. The larger the degree, the greater the influence. However, taking global nodes into account will increase the complexity of the algorithm, and the result is not necessarily good. Because the influence of endpoint is limited, it only has great influence on nearby neighbors. Therefore, this paper proposes to use the derivation of mapping entropy (DME) of node to represent the influence, which represents the mapping relation between a node and its neighbors. It considers not only the weight of the node but also the weight of its neighbors. Figure 1 shows a clear illustration.Figure 1
Sketch maps of influence based on the derivation of mapping entropy. As is shown, the degree of node A in subgraph (a) is equal to the degree of node B in subgraph (b). In traditional models, they are considered to have the same influence. Nevertheless, in the DME model, the differences in the contribution of their neighbors are taken into account. We think that node B has more influence. By calculation, we quantify the influence of A and B as3.77,4,81.
(a)(b)On the basis of above discussion, we improve the SRW model, taking the influence of indirect neighbors into account. Through extensive experiments on nine complex networks, the results show that DME can achieve higher precision than traditional algorithms in most cases.The rest of paper is organized as follows. In Section2, we propose a new model based on the DME index. In Section 3, we introduce 9 complex networks and experimental approaches. In Section 4, five classic models are introduced as reference. In Section 5, results and analysis are presented. In Section 6, we arrive at a conclusion of our study.


## 2. Model Based on the Derivation of Mapping Entropy

### 2.1. Network Model

GV,E is defined as a network, where V is the node set and E is the edge set. The total number of nodes is N and the total number of edges is E. The universal set U can have N×N−1/2 links. The method of link prediction is to give a score sxy to each pair of unconnected nodes which indicates the likelihood of connecting the two nodes. Then, all unconnected nodes are arrayed in descending order of score. The node pair in the top represents that the two nodes are the most likely to generate a connection. In order to test the precision of the algorithm, the known edge set E is divided into training set ET and testing set EP. Only the testing set can be used to calculate scores. Obviously, E=ET∪EP and ET∩EP=ϕ. We define an edge belonging to U but not to E as an inexistent edge. In this paper, we use precision [18] to measure the accuracy of link prediction algorithm, which describes the proportion of real links in the top-L links with highest scores. If there are m real links in top-L links, the precision of the algorithm can be expressed as(1)precsionL=lL.In order to simplify the model, we use undirected and unweighted networks.


### 2.2. Superposed Random Walk (SRW) Model

The SRW model inspired from the LRW model considers random walk between endpointx and y, making the nodes nearby more likely to connect to the target node [19]. It is defined as(2)sxySRWt=∑l=2tkx2E×πxyl+ky2E×πyxl,where the initial density vector π⟶xy0=e⟶x and it evolves as π⟶xyt+1=PT×π⟶xyt. P represents the probability transition matrix with pxy=axy/kx, and axy=1 when the link exists; if not, axy=0. Besides, t denotes the time steps.


### 2.3. Derivation of Mapping Entropy (DME) Model

Inspired by Shannon entropy, the information entropy [20] of the network can be expressed as(3)E=−∑i=1NDCilogDCi,where DCi is the degree centrality of node i. A node and its neighbors construct a subnetwork. The local entropy (LE) [21] of the subnetwork originated from endpoint vi is shown in the following formula:(4)LEi=−∑j=1MDCjlogDCj,where DCj is the degree centrality of node vj, which belongs to the neighbor set M of node vi. Taking the mapping relation between a node and its neighbors into account, we can obtain the mapping entropy (ME):(5)MEi=−DCi∑j=1MlogDCj,where DCi is the degree centrality of node vi and DCj is the degree centrality of one of the neighbors of node vi.Inspired by ME index, we introduce the derivation of mapping entropy: DME, which is defined by interleaving the degrees of nodevi and vj.(6)DMEi=ki∑j=1Mlgkj.The definition considers both the degrees of the node and the degrees of its neighbors which takes the influence of indirect neighbors into account. This may be useful for distinguishing the importance of neighbors. Based on the SRW model, we consider using the DME index to replace the influence of the endpoint, which can perform better than the ME model introduced later through experiments based on the superposed random walk. The model is defined as(7)sxyDMEt=∑l=2tkx∑j=1Mlgkj2E×πxyl+ky∑i=1Nlgkj2E×πyxl.As mentioned above, for better comparison, we also apply the ME index into the SRW model and theME model as shown below.(8)sxyMEt=∑l=2t−DCx∑j=1MlogDCj2E×πxyl+−DCy∑i=1NlogDCi2E×πyxl.


## 2.1. Network Model

GV,E is defined as a network, where V is the node set and E is the edge set. The total number of nodes is N and the total number of edges is E. The universal set U can have N×N−1/2 links. The method of link prediction is to give a score sxy to each pair of unconnected nodes which indicates the likelihood of connecting the two nodes. Then, all unconnected nodes are arrayed in descending order of score. The node pair in the top represents that the two nodes are the most likely to generate a connection. In order to test the precision of the algorithm, the known edge set E is divided into training set ET and testing set EP. Only the testing set can be used to calculate scores. Obviously, E=ET∪EP and ET∩EP=ϕ. We define an edge belonging to U but not to E as an inexistent edge. In this paper, we use precision [18] to measure the accuracy of link prediction algorithm, which describes the proportion of real links in the top-L links with highest scores. If there are m real links in top-L links, the precision of the algorithm can be expressed as(1)precsionL=lL.In order to simplify the model, we use undirected and unweighted networks.


## 2.2. Superposed Random Walk (SRW) Model

The SRW model inspired from the LRW model considers random walk between endpointx and y, making the nodes nearby more likely to connect to the target node [19]. It is defined as(2)sxySRWt=∑l=2tkx2E×πxyl+ky2E×πyxl,where the initial density vector π⟶xy0=e⟶x and it evolves as π⟶xyt+1=PT×π⟶xyt. P represents the probability transition matrix with pxy=axy/kx, and axy=1 when the link exists; if not, axy=0. Besides, t denotes the time steps.


## 2.3. Derivation of Mapping Entropy (DME) Model

Inspired by Shannon entropy, the information entropy [20] of the network can be expressed as(3)E=−∑i=1NDCilogDCi,where DCi is the degree centrality of node i. A node and its neighbors construct a subnetwork. The local entropy (LE) [21] of the subnetwork originated from endpoint vi is shown in the following formula:(4)LEi=−∑j=1MDCjlogDCj,where DCj is the degree centrality of node vj, which belongs to the neighbor set M of node vi. Taking the mapping relation between a node and its neighbors into account, we can obtain the mapping entropy (ME):(5)MEi=−DCi∑j=1MlogDCj,where DCi is the degree centrality of node vi and DCj is the degree centrality of one of the neighbors of node vi.Inspired by ME index, we introduce the derivation of mapping entropy: DME, which is defined by interleaving the degrees of nodevi and vj.(6)DMEi=ki∑j=1Mlgkj.The definition considers both the degrees of the node and the degrees of its neighbors which takes the influence of indirect neighbors into account. This may be useful for distinguishing the importance of neighbors. Based on the SRW model, we consider using the DME index to replace the influence of the endpoint, which can perform better than the ME model introduced later through experiments based on the superposed random walk. The model is defined as(7)sxyDMEt=∑l=2tkx∑j=1Mlgkj2E×πxyl+ky∑i=1Nlgkj2E×πyxl.As mentioned above, for better comparison, we also apply the ME index into the SRW model and theME model as shown below.(8)sxyMEt=∑l=2t−DCx∑j=1MlogDCj2E×πxyl+−DCy∑i=1NlogDCi2E×πyxl.


## 3. Experimental Data

In order to confirm the validity of the DME model, we conduct abundant experiments on nine real networks. They are listed as follows:(1) US Air (USAir), describing the network of the US air transportation system [22]; (2) Yeast PPI (Yeast), expressing the protein-protein relationship network of yeast [23]; (3) Food Web (Food), describing the association of carbon exchanges in the cypress wetlands of Florida ecosystem [24]; (4) Power Grid (Power), expressing the electrical power transportation network in the west of the US [25]; (5) UC Irvine, representing social network (Ucsocial), describing an online social network composed of students of the University of California, Irvine [26]; (6) Jazz, indicating the collaborative relationships among jazz musicians [27]; (7) EuroSiS Web (EuroSiS), showing the interactions between Science in Society actors from 12 European countries [28]; (8) Router, referring to the transmission of data packets between the routers in Internet [4]; and (9) King James, coming from the datasets Lü et al. collected. The fundamental topological features of the mentioned networks are listed in Table 1.Table 1
The basic statistical features of the 9 benchmark networks.
NetsVEkdCrHUSAir332212612.812.740.749−0.2083.36Yeast2364108989.25.160.3780.4703.35Food128207532.421.780.335−0.1121.24Power494165942.66915.870.1070.0031.45Ucsocial18931383514.623.060.138−0.1883.81Jazz198274227.76.450.6180.021.4EuroSiS1272645410.153.860.382−0.0122.46Router502162572.496.450.033−0.1385.50King James1707905910.613.380.710−0.0523.92V denotes the number of nodes in the network, E represents the total number of links, k is the average degree of all nodes, d indicates the average distance among nodes, C represents the clustering coefficient, r is the associativity coefficient, and H denotes the degree heterogeneity defined as H=k2/k2.Our model is applied to the undirected and unweighted connected networks. Accordingly, we make arcs turn into undirected links. Besides, we delete the loops and multiple connections. Subsequently, the maximal edge-connected graph is extracted from each raw dataset to guarantee the connectivity of the whole.Before the experiment, the edge setE of the nine networks is divided into two parts ET and EP randomly. The training set ET contains 90% of the whole edge set. The testing set EP contains 10%. The connectivity of the ET is guaranteed by the means of adding edges randomly to the minimum spanning tree until the training set contains 90% links. Next, 30 groups of separate experimental data for each network are divided in the same size. Then, they are applied for the averaged precision by statistical methods to avoid the randomness of results.


## 4. Reference Standard

In order to highlight the superiority of our algorithm, five classic methods are listed as follows.(1)
In common neighbor (CN) [12], the similarity is judged by the number of neighbors shared by node x and node y, which is defined as(9)sxyCN=Γx∩Γy,whereΓx represents the set of neighbors of node x. Besides, Γx∩Γy refers to the amount of common neighbors of nodes x and y.(2)
Preferential attachment (PA) [29] considers that the probability of a new link linked to the node x is proportional to kx, so the probability between node x and y is proportional to kx×ky. The index is defined as(10)sxyPA=kx×ky.This index does not require the information of the neighborhood of each endpoint. Therefore, it has low computational complexity.(3)
In Adamic-Adar (AA) [13], the idea is that the contribution of the node with small degree is greater. So, each node is given a weight value equaling to 1/logkz where kz is the degree of a node from common neighbor set. The similarity is defined as(11)sxyAA=∑z∈Γx∩Γy1logkz,wherekz represents the degree of common neighbor z.(4)
Resource allocation (RA) [30], derived from AA, considers the resource allocation of network. Each node is given a weight value which is equal to 1/kz, and the similarity is defined as(12)sxyRA=∑z∈Γx∩Γy1kz.(5)
Superposed random walk (SRW) has been discussed in Section2 in detail.


## 5. Results and Analysis

In order to prove the effectiveness of the DME model, abundant experiments have been carried out in nine real networks. The results are shown as follows.In Figure2, we plot the variation of the average precision with random walk steps obtained by SRW, ME, and DME in nine networks in the case of L = 100. We can see that DME performs better obviously in 8 of the 9 networks than SRW. Furthermore, compared to both SRW and ME models, the DME model achieves the maximum precision in 6 of the 9 networks. Because the ME index reflects the robustness of local network, it is more suitable for applying in network attacks to represent the importance of nodes. Therefore, we arrive at a conclusion that DME can achieve the highest accuracy in most cases when the random walk step t is optimal. Besides, it can reach the maximum precision in the minimum number of steps so that it can reduce the computation with the same precision.Figure 2
Precision of SRW (green circles), ME (blue rectangles), and DME (red triangles) versus number of random walk stepst with L = 100 in 9 real datasets. The highest precision in each network is marked by a black five-angled star. As is shown, DME performs better obviously in 8 of the 9 networks than SRW. Furthermore, compared to SRW and ME models, the DME model achieves the maximum precision in 6 of the 9 networks. (a) USAir. (b) Yeast. (c) Food. (d) Power. (e) Ucsocial. (f) Jazz. (g) EuroSiS. (h) Router. (i) King James.
(a)(b)(c)(d)(e)(f)(g)(h)(i)Table2 contains the detailed description of Figure 2. Furthermore, it also compares our model with other five classical models. The maximum precision is emphasized in bold and the corresponding step is in the parentheses. As is shown, the DME model reaches the highest precision in 6 of the 9 networks under the condition of L = 100 compared with other five traditional models.Table 2
Precision on the nine benchmark networks in the case ofL = 100.
PrecisionCNPAAARASRWDMEUSAir0.6350.4796670.6543330.640.670583 (4)0.670667 (2)Yeast0.7280.5550.7226670.5150.682242 (12)0.699333 (3)Food0.0860.2113330.0896670.0886670.184810 (15)0.209952 (15)Power0.1243330.0173330.0813330.0573330.087810 (15)0.136500 (7)Ucsocial0.0393330.0573330.0373330.0313330.054738 (15)0.058048 (15)Jazz0.8160.1686670.8356670.8063330.806333 (2)0.62 (2)EuroSiS0.4563330.0493330.466670.3940.412833 (3)0.415 (2)Router0.1326670.0160.1023330.0750.229278 (15)0.288690 (15)King James0.4043330.1906670.5543330.828670.225667 (2)0.254667 (2)Each data point is an average over 30 independently divided datasets. The number in bold means the highest precision. The value enclosed in the parentheses represents the step corresponding to optimal precision.For ensuring the integrity of the experiment, we also conduct experiments in the case ofL = 50. The results are shown in Table 3. We italicize the values when the DME model is more exact than SRW. There are still 6 networks. Nevertheless, the advantage is not obvious when compared with other five models comprehensively. This means the DME model performs better in the top 100 links than 50 links. Actually, L is often defined as a large number to avoid random error.Table 3
Precision on the nine benchmark networks withL = 50.
PrecisionCNPAAARASRWDMEUSAir0.8213330.6466670.825330.7533330.8016 (6)0.806889 (4)Yeast0.7793330.5946670.7633330.4706670.813429 (15)0.817333 (15)Food0.1186670.2740.1206670.1166670.268 (15)0.275762 (15)Power0.2120.0086670.0593330.0453330.119333 (15)0.187778 (7)Ucsocial0.0506670.0776670.0433330.0413330.070667 (15)0.064667 (15)Jazz0.8953330.2226670.9066670.8766670.0.876667 (2)0.716667 (2)EuroSiS0.5933330.0740.5606670.4373330.466667 (5)0.507333 (2)Router0.170.0146670.1213330.0653330.134 (15)0.196810 (15)King James0.5526670.2693330.690.8986670.898667 (2)0.502 (2)Each data point is an average over 30 independent datasets, each of which is randomly divided into training set and test set with 90% and 10% probability. The value enclosed in the parentheses represents the step corresponding to optimal precision. Besides, the italicized values illustrate that theDME model performs better than the SRW model.The reason why the DME model can have an excellent performance is that it takes the mapping relationship between a node and its neighbors into comprehensive consideration. In this way, the differences in contribution of neighbors (i.e., the influences of indirect neighbors) are included, so that the model can assess the importance of endpoint better.Though the DME model can achieve preferable performance in most datasets experimented by us, it also has no superiority in a few networks such as Jazz. By analyzing the topological characteristics of these networks, we find that they usually have the same features. The model we propose may be not suitable for the networks with good associativity coefficient and high clustering coefficient. We infer the reason is that the differences in contribution of neighbor nodes in such networks cannot be well reflected.Furthermore, time complexity is also a significant factor to evaluate an index. For instance, CN index hasON3 computational complexity while the complexity of RA is 2×ON3. The complexity of SRW which considers local path is M×ON3, and M is far less than N3. The model we introduce has the same time complexity of M×ON3 as SRW but can realize higher precision.


## 6. Conclusions

Existing link prediction algorithms on the basis of structural similarity mostly focus on the paths or the influences of nodes with only their degrees considered. Because the differences in contribution of neighbors are not considered, the precision of algorithm is limited. Through analysis, we propose the derivation of mapping entropy (DME) model, which interleaves the degrees of node and its neighbors. We investigate our model in comparison of CN, PA, AA, RA, SRW, and ME models on nine real datasets. The results indicate that the DME model prominently performs better than other six models and can achieve maximum precision in the minimum number of steps which reduces the computation with the same precision. Furthermore, the DME model does not increase time complexity.The DME model proposed in our study reveals the effectiveness of distinguishing the differences in neighbors’ contribution. This finding can provide a reference for future research. However, we only take the influence of indirect neighbors into account and ignore other factors such as coreness and H-index which can describe the maximal connected subgraph. Besides, we do not know the performance of the DME model in weighted and directed networks.The results of our research are meaningful, and they are of great significance to the practical application of academic research. We can apply it in recommendation system, social cooperation network, information and communication technology, potential interactions in biological networks, and so on. Significantly, this work can inspire further work to add other factors such as H-index on the basis of our model and optimize the DME model in weighted and directed networks.



---

*Source: 4156832-2021-08-02.xml*