# Finding Missing Links in Complex Networks: A Multiple-Attribute Decision-Making Method

Authors: Longjie Li; Shenshen Bai; Mingwei Leng; Lu Wang; Xiaoyun Chen
Journal: Complexity
 (2018)

---

## Abstract

Link prediction, which aims to forecast potential or missing links in a complex network based on currently observed information, has drawn growing attention from researchers. To date, a host of similarity-based methods have been put forward. Usually, one method harbors the idea that one similarity measure is applicable to various networks, and thus has performance fluctuation on different networks. In this paper, we propose a novel method to solve this issue by regarding link prediction as a multiple-attribute decision-making (MADM) problem. In the proposed method, we considerRA, LP, and CAR indices as the multiattribute for node pairs. The technique for order performance by similarity to ideal solution (TOPSIS) is adopted to aggregate the multiattribute and rank node pairs. The proposed method is not limited to only one similarity measure, but takes separate measures into account, since different networks may have different topological structures. Experimental results on 10 real-world networks manifest that the proposed method is superior in comparison to state-of-the-art methods.


---

## Body

## 1. Introduction

In recent years, the research of link prediction in complex networks has captured much attention of researchers from various disciplines [1] not only because many available real-world networks are incomplete [2, 3] but also because link prediction is closely related to many other problems [4, 5]. It offers one possible way to understand the evolution of networks [6–8] and gives help to find potential interactions between proteins in biological networks [9, 10]. Link prediction has also been applied to friendship suggestions in social networks [11, 12], products recommendation in e-commerce systems [13, 14], collaboration prediction in coauthorship networks [15, 16] and so on.As a fundamental research hotspot in complex network analysis, link prediction can uncover missing or latent existent links and point out spurious links in a network based on the observed information [9, 17, 18]. In this paper, we center on finding missing links. Generally speaking, two unconnected nodes with a high similarity score are deemed to be likely to have a missing link [5, 17]. That is the basic hypothesis of the so-called similarity-based approaches. In a similarity-based approach, similarity scores of nonexisting links are estimated first, and then links at the top of the sorted score list with descending order are predicted as missing ones [17]. To date, great efforts have been devoted to link prediction based on observed network structure information [1, 4, 17], such as common neighbors [19–21], local paths [22, 23], and triangle structures [24, 25]. Along this line, a plethora of similarity-based indices and methods have been proposed. These approaches usually focus on only one similarity measure and assume that it is applicable to all networks. However, different networks always have separate inner structural features [26, 27]. Thus, the prediction performances of these approaches are not stable on different networks.On the other hand, likelihood-based algorithms aim at identifying the most likely generative model for a network and then estimate the connection likelihood of any two nodes according to the considered model [28, 29]. These algorithms usually assume that a network has a known structure and build a model, such as hierarchical structure model [29] and stochastic block model [9], to fit the structure and evaluate model parameters using statistical methods [4]. However, the structure of a network is not always known, and a model cannot be suitable for all networks.In this paper, we regard link prediction as a multiple-attribute decision-making (MADM) (also called multicriteria decision-making (MCDM)) problem. MADM is an approach that has been designed to select a preferred alternative, classify alternatives in a small number of categories, and/or rank alternatives in a subjective preference order [30, 31]. It is a widely used tool in various fields [32, 33]. Among numerous MADM methods put forward to solve real-world decision problems, the technique for order preference by similarity to ideal solution (TOPSIS) continues to work satisfactorily across diverse application areas [31, 34]. TOPSIS was originally proposed to give help to determine the best alternative with a finite number of criteria [35]. TOPSIS makes full use of attribute information, affords a cardinal ranking of alternatives, and does not require attribute preferences to be independent [36]. As a well-known classical MADM method, TOPSIS has received considerable interest from researchers and practitioners [31]. In a complex network analysis, TOPSIS was used to identify influential nodes [34, 37, 38]. In this paper, we apply TOPSIS to reveal missing links. The similarity scores based on different similarity indices are considered as multiattribute to make the decision for ranking nonexisting links.The work in [39] also adopted TOPSIS in link prediction; however, it is totally different from our work. In [39], TOPSIS is only used to evaluate the local centralities of common neighbors. The similarity score between two nodes is computed based on the local centralities of their common neighbors. In our method, TOPSIS is employed to evaluate the degrees of similarity of node pairs and determine the missing links. Three famous similarity indices, that is, RA [21], LP [21, 23], and CAR [24] are chosen as the multiattribute of TOPSIS. The reason for selecting these indices is that they are designed based on different but prominent structural features. Since each attribute is associated with a weight in TOPSIS, we present a new algorithm based on the known information about micro nodes to determine the weights. To verify the performance of the proposed method, we conduct experiments on 10 real-world networks from various fields. The experimental results demonstrate the stability and robustness of our method.The rest of the paper is structured as follows. In Section2, we give the description of the link prediction problem and the metrics for evaluating the accuracy of link prediction algorithms. Section 3 lists the baselines, and Section 4 introduces the proposed method. In Section 5, the experimental results and performance analysis of the proposed method are presented. Finally, Section 6 concludes this work.


## 2. Problem Description and Metric

Consider an undirected and unweighted networkGV,E, in which V and E are the node set and link set, respectively. Multilinks and self-loops are not allowed in this study. For a network containing N nodes, the set that contains NN−1/2 possible links is denoted by U, and then the set of unconnected node pairs is U−E. Each node pair in U−E is assigned a similarity score according to a given similarity method. All unconnected node pairs are sorted in descending order according to their scores, and the node pairs at the top are most likely to have missing links [17].Actually, we do not have the ground truth, that is, the missing links are not known. Therefore, to test the accuracy of a link prediction method, the link setE is randomly divided into two parts: training set Etr and testing set Ets, such that E=Etr∪Ets and Etr∩Ets=∅. Two standard metrics are employed to quantify the accuracy of link prediction algorithms: AUC [17] and Precision [40]. In this situation, the AUC value can be interpreted as the probability that a randomly selected missing link (i.e., a link in Ets) is assigned a higher similarity score than a randomly selected nonexistent link (i.e., a link in U−E). In implementation, we perform n times of independent comparisons. If there are n1 times that the missing link has a higher score and n2 times that they have the same score, the AUC value is computed as
(1)AUC=n1+0.5n2n.Precision characterizes the ratio of correctly predicted links within a given prediction list. If we take the top-L as the prediction list, among which m links are correctly predicted, then Precision is
(2)Precision=mL.


## 3. Baseline Prediction Methods

Up to date, many link prediction methods have been proposed [1, 4, 17]. Here, we list some state-of-the-art approaches used in this paper.
(1)
Resource allocation (RA) index [21]. This index models the resource allocation between two nodes through their shared neighbors. The amount of resource that one node received from another through their common neighbors is defined as their similarity, which is
(3)RAx,y=∑z∈Γx∩Γy1kz,where Γx denotes the neighbor set of node x, and kz is the degree of node z.
(2)
Adaptive degree penalization (ADP) index [27]. This method is proposed to automatically adapt to the network structure. It tries to estimate the best-performing degree penalization by the network clustering coefficient. The formal definition is
(4)ADPx,y=∑z∈Γx∩Γykz−βC,where β is a constant, C is the average clustering coefficient of the network. β is set to 2.5 in this paper according to the authors’ suggestion.
(3)
CAR index [24]. This index stems from both node-based and link-based perspectives, which suggests that two nodes are more likely to link together if their common neighbors are members of a local community. The similarity function defined by this index can be computed as
(5)CARx,y=CNx,y·∑z∈Γx∩ΓyΓx∩Γy∩Γz2,where CNx,y is the number of common neighbors between x and y, which is
(6)CNx,y=Γx∩Γy.
(4)
Clustering coefficient for link prediction (CCLP) index [25]. This index is inspired by the idea that triangle information is very useful in estimating similarities of nodes. It computes the similarity between two nodes by employing the clustering coefficient of shared neighbors:
(7)CCLPx,y=∑z∈Γx∩ΓyCCz,where CCz denotes the clustering coefficient of node z, which is
(8)CCz=2tzkzkz−1,in which tz is the number of triangles passing through node z.
(5)
Local path (LP) index [21, 23]. This metric extends the horizon of common neighbors to three hops paths, which estimates the similarity of two nodes as
(9)LPx,y=∑i=12λi−1Pix,y,where Pix,y is the number of paths between x and y with length i; λ is an adjustable parameter. Generally, λ is a very small number, and we set λ=0.001 in this paper.
(6)
Mutual information (MI) index [41]. This method defines nodes’ similarities from the perspective of information theory by computing the conditional self-information of the existence of a link between two unconnected nodes given their common neighbors. The similarity between two nodes is estimated as
(10)MIx,y=−ILxy1∣Γx∩Γy=∑z∈Γx∩ΓyILxy1;z−ILxy1,where ILxy1 is the self-information of x and y being connected, and ILxy1;z is the mutual information of the existence of a link between x and y and the shared neighbor z. ILxy1 and ILxy1;z are, respectively, calculated as
(11)ILxy1=−log21−∏i=1kyE−kx−i+1E−i+1,ILxy1;z=1kzkz−1∑u,v∈Γz,u≠vILuv1−ILxy1∣z=1kzkz−1∑u,v∈Γz,u≠vILuv1+log2CCz.
(7)
Adaptive fusion model base on logistic regression (LR index) [26]. The method was proposed based on the observation that: (i) the roles of different structural features in a network are utterly different, and (ii) the role of a structural feature in different modules is also different [26]. LR index defines the connection probability of node pair x,y as
(12)Px,y=maxPM1x,y,…,PMkx,y,where PMkx,y is the connection probability of x,y in module Mk, which is
(13)PMkx,y=11+exp−β0+∑l=1LβlSMkFlx,y,where SMkFlx,y denotes the similarity score induced by feature Fl for x,y in module Mk. Three scenarios of modules were considered in [26]; correspondingly, the index based on these scenarios was denoted as LR1, LR2, and LRm. LRm is a tradeoff between LR1 and LR2; hence, we use LRm in our experiments. As in [26], three features, that is, CN (see (6)), PA (see (14)), and DD (see (15)), are incorporated for LRm in this paper.
(14)PAx,y=kx·ky,(15)DDx,y=kx−ky.
(8)
Local nave Bayes (LNB) method [42]. This method calculates the connection likelihood between two nodes based on the LNB model. The likelihood score of node pair x,y is defined as
(16)rx,y=s−1∏z∈Γx∩ΓysRz,where s=U/Etr−1, which is a constant for a network, and Rz=NΔz+1/N∧z+1, in which NΔz and N∧z are, respectively, the number of connected and unconnected node pairs whose common neighbors include z.
In [42], an exponent function fkz, which is a function of the degree of node z, is added to the item sRz in (16). Using a logarithmic function on both sides and neglecting the constant s−1, a linear formula of connection likelihood is obtained, which is
(17)r′x,y=∑z∈Γx∩ΓyfkzlogsRz.
In this paper, we usefkz=1; the corresponding method is named LNB_CN [42], which is
(18)LNB_CNx,y=∑z∈Γx∩Γylogs+logRz.
(9)
Maximization entropy (MaxE) method [28]. This method is a likelihood-based algorithm based on a series of results concerning constrained entropy maximization [43]. MaxE uses the observed portion of a network as constraints of a maximization procedure defined within the exponential random graph (ERG) framework [43]. In the case of undirected and unweighted networks, the ERG framework maximizes the likelihood function L=lnPAo, where Ao is the adjacency matrix of the observed portion, that is, training set, and PAo is defined as
(19)PAo=∏i<jpijaij1−pij1−aij,where aij∈Ao and pij=xixj/1+xixj. By solving the system of equations in (20), the maximization of likelihood can be obtained.
(20)kiAo=∑j≠ipij=∑j≠ixixj1+xixj∀i.


## 4. Methodology

A multitude of similarity indices has been carried out for link prediction in complex networks. In general, one similarity index only employs one or two structural features and assumes that they are suitable for all networks. However, different networks usually have different structural features; separate similarity indices need to be taken into account. To address this issue, a novel method is proposed in this paper to forecast missing links by considering link prediction as a multiple-attribute decision-making (MADM) problem. MADM is an approach to rank alternatives in a subjective preference order [30, 31]. In this paper, each potential missing link is viewed as an alternative, and each similarity index is considered as an attribute. In implementation, we adopt TOPSIS [35], a well-known classical MADM method, to uncover the missing links in this paper. Meanwhile, three classical similarity indices, that is, RA, LP, and CAR, are chosen as the multiattribute in our method. For convenience, our method is named LPTOPSIS.In the following of this part, we first introduce the TOPSIS method in Section4.1. Then, the proposed method is presented in Section 4.2. Finally, a simple example is given to explain how the proposed method performs in Section 4.3.


### 4.1. TOPSIS Method

Technique for order preference by similarity to ideal solution (TOPSIS) is a simple but effective ranking method in conception and application [35]. The standard TOPSIS method attempts to determine the best alternative that simultaneously has the shortest distance from the positive ideal solution and the farthest distance from the negative ideal solution. The ranking of the alternatives is calculated according to the relative closeness to the ideal solution.Given a decision matrixX=xijm×n of m alternatives and n criteria (decision attributes) in
(21)X=x11x12⋯x1nx21x22⋯x2n⋮⋮⋱⋮xm1xm2⋯xmn,where xij denotes the value of the ith alternative under jth criteria in matrix X. The procedures of the TOPSIS method are depicted as follows:Step 1.
Normalize the decision matrixX by using the vector-normalization technique.
(22)yij=xij∑i=1mxij2,where yiji=1,2,…,m;j=1,2,…,n is the normalized value of ith alternative under the jth criteria.Step 2.
Calculate the weighted-normalized decision matrixV=vijm×n by using the associated weights.
(23)vij=wj·yij,where wjj=1,2,…,n is the weight of the jth criterion.Step 3.
Determine the positive ideal solutionS+ and negative ideal (anti-ideal) solution S−, respectively.
(24)S+=s1+,s2+,…,sn+,(25)S−=s1−,s2−,…,sn−.
For the benefit criteriaKb:
(26)sj+=maxivij∣j∈Kb,sj−=minivij∣j∈Kb;and for the cost criteria Kc:
(27)sj+=minivij∣j∈Kc,sj−=maxivij∣j∈Kc.Step 4.
Obtain the Euclidean distance of each alternative from the positive ideal and the negative ideal solutions, respectively.(28)di+=∑j=1nvij−sj+2,(29)di−=∑j=1nvij−sj−2,where di+i=1,2,…,m and di−i=1,2,…,m are the Euclidean distances of ith alternative from the positive ideal and the negative ideal solutions, respectively.Step 5.
Compute the relative closeness of each alternative to the ideal solution.(30)Ci=di−di−+di+,where Ci∈0,1 for i=1,2,…,m. An alternative with a higher Ci is supposed to be a better solution and vice versa.


### 4.2. The Proposed Method

Figure1 presents the flow chart of the proposed method. The detailed description of the proposed method is outlined as follows.Step 1.
Determine the weights of different similarity indices.
In TOPSIS, each attribute is associated with a weight. In this work, we employ similarity indices as the multiattribute in TOPSIS application for link prediction. Thence, we need to determine the weight of each index. To this end, we adjust theAUC for micro nodes to propose AUCvi for node vi [44]. For the node vi, let Evi denote the set of existing links between vi and other nodes and E¯vi represent the set of nonexisting links between vi and other nodes. Suppose I be a similarity index, the similarity scores of all links in Evi and E¯vi are computed based on I, respectively. Then, the value of AUCvi is defined as
(31)AUCvi=nvi′+0.5nvi″nvi,where nvi is the total independent comparison time; nvi′ denotes the comparison time that the link from Evi has a higher similarity score, and nvi″ denotes the comparison time that has the same score.Figure 1
The flow chart of the proposed method.To define the weight of similarity indexI, we randomly select p% nodes from the network, and compute the value of AUCvi for each selected node. Let ρ be the group of selected nodes, we define
(32)AUCρ=∑vi∈ρAUCviρ,ρ>00.5,ρ=0The weight of similarity indexI is denoted as wI, which is determined by the ratio of AUCρ and 0.5 (see (33)) [44]. 0.5 represents the result of random prediction.
(33)wI=AUCρ0.5.Algorithm1 lists the procedure for determining the weight of a similarity index. In implementation, we randomly select 10% nodes from the networks.Algorithm 1: Determine weight.
Input:Etr: training graph; I: similarity index;
p%: percentage of nodes
Output: weight of I
1:ρ←randomly selected p% nodes from Etr;
2:for vi∈ρ do
3: Calculate similarity scores for existing links
betweenvi and other nodes based on I;
4: Calculate similarity scores for non-existing links
betweenvi and other nodes based on I;
5: CalculateAUCvi using Eq. (31)
6:end for
7: CalculatewI using Eq. (33);
8:return wI;Step 2.
Calculate the similarity score for each potential missing link by different similarity indices.
As aforementioned, the indices ofRA, LP, and CAR are used in LPTOPSIS. The reason that we adopt these indices is that they are designed based on different but prominent structural features. Suppose that m unconnected node pairs are assigned similarity scores, and the decision matrix is represented as follows:
(34)X=RA1LP1CAR1RA2LP2CAR2⋮⋮⋮RAmLPmCARm.Step 3.
Compute the normalized and weighted decision matrix.
Since the values of different similarity indices are in different scales, we normalize matrixX based on (22). Then, we compute the weighted normalized matrix using (23). The associated weights are obtained in Step 1.Step 4.
Determine the positive ideal and negative ideal solutions.
According to the weighted normalized matrix obtained in Step 2, the positive ideal solutionS+ and negative ideal solution S− are determined using (24) and (25), respectively.Step 5.
Calculate the separation measures of potential missing links from the positive ideal and the negative ideal solutions.
The separation measures between potential missing links and the positive ideal solution are calculated using (28), and the separation measures between potential missing links and the negative ideal solution are calculated using (29).Step 6.
Obtain the relative closeness of each potential missing link to the ideal solution.
The relative closeness is obtained by (30). Sort potential missing links in descending order according to their closeness scores, and the links at the top are most likely to be missing ones.


### 4.3. Example Explanation

This section uses an example to explain how the proposed method works. Figure2 shows the example network. In this example, we simply assume that each similarity index has the same weight. Thus, we have no need to weight the normalized matrix.Figure 2
An example network with 8 nodes and 13 links.First, calculate the values ofRA, LP, and CAR for unconnected node pairs of the network. Thirteen, twenty, and three unconnected node pairs are assigned values by RA, LP, and CAR, respectively. The results are listed in Figure 3(a). Because LP index considers both 2-hop and 3-hop paths, it gives values for the most unconnected node pairs. CAR index demands that there are links between the common neighbors. Since the example network is very simple, the requirement of CAR index cannot always be granted. Therefore, it assigns the score of zero to most node pairs.Figure 3
The values ofRA, LP, and CAR for unconnected node pairs in the example network.
(a)
Similarity scores
(b)
Decision matrix
(c)
Normalized decision matrixSecond, the decision matrixX and the normalized decision matrix Y are obtained according to Figure 3(a) and (22), which are presented in Figures 3(b) and 3(c), respectively.Next, determine the positive ideal solutionS+ and the negative ideal solution S−, which are
(35)S+=0.66699,0.52204,0.72761,S−=0,0.00017,0.Then, computedi+ and di− for each potential missing link, respectively. The results are outlined in Table 1.Table 1
Relative closeness and rank of each node pair.
Node pair
di+
di−
Ci
Rank
(0, 1)
0
1.11653
1
1
(1, 8)
0.39359
0.72441
0.64795
2
(3, 6)
0.46694
0.67170
0.58992
3
(2, 4)
0.84361
0.44484
0.34525
4
(3, 4)
0.84365
0.44471
0.34517
5
(1, 6)
0.95573
0.23258
0.19572
6
(4, 6)
0.95585
0.23232
0.19553
7
(2, 5)
0.97272
0.21318
0.17976
8
(2, 7)
0.97272
0.21318
0.17976
9
(3, 5)
0.97272
0.21318
0.17976
10
(3, 7)
0.97272
0.21318
0.17976
11
(4, 5)
0.97279
0.21303
0.17965
12
(4, 7)
0.97279
0.21303
0.17965
13
(0, 5)
1.11637
0.00035
0.00031
14
(0, 7)
1.11637
0.00035
0.00031
15
(2, 8)
1.11645
0.00017
0.00016
16
(3, 8)
1.11645
0.00017
0.00016
17
(4, 8)
1.11645
0.00017
0.00016
18
(5, 6)
1.11653
0
0
19
(6, 7)
1.11653
0
0
20At last, calculate the relative closeness of all potential missing links and rank them based on their relative closeness. The results are shown in Table1. As mentioned above, rank the potential missing links according to the relative closeness to the ideal solution and assume that the links at top ranks are the real missing ones.


## 4.1. TOPSIS Method

Technique for order preference by similarity to ideal solution (TOPSIS) is a simple but effective ranking method in conception and application [35]. The standard TOPSIS method attempts to determine the best alternative that simultaneously has the shortest distance from the positive ideal solution and the farthest distance from the negative ideal solution. The ranking of the alternatives is calculated according to the relative closeness to the ideal solution.Given a decision matrixX=xijm×n of m alternatives and n criteria (decision attributes) in
(21)X=x11x12⋯x1nx21x22⋯x2n⋮⋮⋱⋮xm1xm2⋯xmn,where xij denotes the value of the ith alternative under jth criteria in matrix X. The procedures of the TOPSIS method are depicted as follows:Step 1.
Normalize the decision matrixX by using the vector-normalization technique.
(22)yij=xij∑i=1mxij2,where yiji=1,2,…,m;j=1,2,…,n is the normalized value of ith alternative under the jth criteria.Step 2.
Calculate the weighted-normalized decision matrixV=vijm×n by using the associated weights.
(23)vij=wj·yij,where wjj=1,2,…,n is the weight of the jth criterion.Step 3.
Determine the positive ideal solutionS+ and negative ideal (anti-ideal) solution S−, respectively.
(24)S+=s1+,s2+,…,sn+,(25)S−=s1−,s2−,…,sn−.
For the benefit criteriaKb:
(26)sj+=maxivij∣j∈Kb,sj−=minivij∣j∈Kb;and for the cost criteria Kc:
(27)sj+=minivij∣j∈Kc,sj−=maxivij∣j∈Kc.Step 4.
Obtain the Euclidean distance of each alternative from the positive ideal and the negative ideal solutions, respectively.(28)di+=∑j=1nvij−sj+2,(29)di−=∑j=1nvij−sj−2,where di+i=1,2,…,m and di−i=1,2,…,m are the Euclidean distances of ith alternative from the positive ideal and the negative ideal solutions, respectively.Step 5.
Compute the relative closeness of each alternative to the ideal solution.(30)Ci=di−di−+di+,where Ci∈0,1 for i=1,2,…,m. An alternative with a higher Ci is supposed to be a better solution and vice versa.


## 4.2. The Proposed Method

Figure1 presents the flow chart of the proposed method. The detailed description of the proposed method is outlined as follows.Step 1.
Determine the weights of different similarity indices.
In TOPSIS, each attribute is associated with a weight. In this work, we employ similarity indices as the multiattribute in TOPSIS application for link prediction. Thence, we need to determine the weight of each index. To this end, we adjust theAUC for micro nodes to propose AUCvi for node vi [44]. For the node vi, let Evi denote the set of existing links between vi and other nodes and E¯vi represent the set of nonexisting links between vi and other nodes. Suppose I be a similarity index, the similarity scores of all links in Evi and E¯vi are computed based on I, respectively. Then, the value of AUCvi is defined as
(31)AUCvi=nvi′+0.5nvi″nvi,where nvi is the total independent comparison time; nvi′ denotes the comparison time that the link from Evi has a higher similarity score, and nvi″ denotes the comparison time that has the same score.Figure 1
The flow chart of the proposed method.To define the weight of similarity indexI, we randomly select p% nodes from the network, and compute the value of AUCvi for each selected node. Let ρ be the group of selected nodes, we define
(32)AUCρ=∑vi∈ρAUCviρ,ρ>00.5,ρ=0The weight of similarity indexI is denoted as wI, which is determined by the ratio of AUCρ and 0.5 (see (33)) [44]. 0.5 represents the result of random prediction.
(33)wI=AUCρ0.5.Algorithm1 lists the procedure for determining the weight of a similarity index. In implementation, we randomly select 10% nodes from the networks.Algorithm 1: Determine weight.
Input:Etr: training graph; I: similarity index;
p%: percentage of nodes
Output: weight of I
1:ρ←randomly selected p% nodes from Etr;
2:for vi∈ρ do
3: Calculate similarity scores for existing links
betweenvi and other nodes based on I;
4: Calculate similarity scores for non-existing links
betweenvi and other nodes based on I;
5: CalculateAUCvi using Eq. (31)
6:end for
7: CalculatewI using Eq. (33);
8:return wI;Step 2.
Calculate the similarity score for each potential missing link by different similarity indices.
As aforementioned, the indices ofRA, LP, and CAR are used in LPTOPSIS. The reason that we adopt these indices is that they are designed based on different but prominent structural features. Suppose that m unconnected node pairs are assigned similarity scores, and the decision matrix is represented as follows:
(34)X=RA1LP1CAR1RA2LP2CAR2⋮⋮⋮RAmLPmCARm.Step 3.
Compute the normalized and weighted decision matrix.
Since the values of different similarity indices are in different scales, we normalize matrixX based on (22). Then, we compute the weighted normalized matrix using (23). The associated weights are obtained in Step 1.Step 4.
Determine the positive ideal and negative ideal solutions.
According to the weighted normalized matrix obtained in Step 2, the positive ideal solutionS+ and negative ideal solution S− are determined using (24) and (25), respectively.Step 5.
Calculate the separation measures of potential missing links from the positive ideal and the negative ideal solutions.
The separation measures between potential missing links and the positive ideal solution are calculated using (28), and the separation measures between potential missing links and the negative ideal solution are calculated using (29).Step 6.
Obtain the relative closeness of each potential missing link to the ideal solution.
The relative closeness is obtained by (30). Sort potential missing links in descending order according to their closeness scores, and the links at the top are most likely to be missing ones.


## 4.3. Example Explanation

This section uses an example to explain how the proposed method works. Figure2 shows the example network. In this example, we simply assume that each similarity index has the same weight. Thus, we have no need to weight the normalized matrix.Figure 2
An example network with 8 nodes and 13 links.First, calculate the values ofRA, LP, and CAR for unconnected node pairs of the network. Thirteen, twenty, and three unconnected node pairs are assigned values by RA, LP, and CAR, respectively. The results are listed in Figure 3(a). Because LP index considers both 2-hop and 3-hop paths, it gives values for the most unconnected node pairs. CAR index demands that there are links between the common neighbors. Since the example network is very simple, the requirement of CAR index cannot always be granted. Therefore, it assigns the score of zero to most node pairs.Figure 3
The values ofRA, LP, and CAR for unconnected node pairs in the example network.
(a)
Similarity scores
(b)
Decision matrix
(c)
Normalized decision matrixSecond, the decision matrixX and the normalized decision matrix Y are obtained according to Figure 3(a) and (22), which are presented in Figures 3(b) and 3(c), respectively.Next, determine the positive ideal solutionS+ and the negative ideal solution S−, which are
(35)S+=0.66699,0.52204,0.72761,S−=0,0.00017,0.Then, computedi+ and di− for each potential missing link, respectively. The results are outlined in Table 1.Table 1
Relative closeness and rank of each node pair.
Node pair
di+
di−
Ci
Rank
(0, 1)
0
1.11653
1
1
(1, 8)
0.39359
0.72441
0.64795
2
(3, 6)
0.46694
0.67170
0.58992
3
(2, 4)
0.84361
0.44484
0.34525
4
(3, 4)
0.84365
0.44471
0.34517
5
(1, 6)
0.95573
0.23258
0.19572
6
(4, 6)
0.95585
0.23232
0.19553
7
(2, 5)
0.97272
0.21318
0.17976
8
(2, 7)
0.97272
0.21318
0.17976
9
(3, 5)
0.97272
0.21318
0.17976
10
(3, 7)
0.97272
0.21318
0.17976
11
(4, 5)
0.97279
0.21303
0.17965
12
(4, 7)
0.97279
0.21303
0.17965
13
(0, 5)
1.11637
0.00035
0.00031
14
(0, 7)
1.11637
0.00035
0.00031
15
(2, 8)
1.11645
0.00017
0.00016
16
(3, 8)
1.11645
0.00017
0.00016
17
(4, 8)
1.11645
0.00017
0.00016
18
(5, 6)
1.11653
0
0
19
(6, 7)
1.11653
0
0
20At last, calculate the relative closeness of all potential missing links and rank them based on their relative closeness. The results are shown in Table1. As mentioned above, rank the potential missing links according to the relative closeness to the ideal solution and assume that the links at top ranks are the real missing ones.


## 5. Experimental Analysis

### 5.1. Datasets

To evaluate the performance of the proposed method, we use 10 real-world networks collected from various fields in this work (all data are downloaded fromhttp://deim.urv.cat/~alexandre.arenas/data/welcome.htm, http://www-personal.umich.edu/~mejn/netdata/, http://vlado.fmf.uni-lj.si/pub/networks/data/, http://noesis.ikor.org/datasets/link-prediction). The brief descriptions of these networks are given as follows:
(1)
C. elegans (CE): the neural network of a Caenorhabditis elegans worm [45].
(2)
Email: a network of email interchanges between members of a university [46].
(3)
Facebook (FBK): a social network collected fromhttps://www.facebook.com/ [47].
(4)
Football (FTB): the network of American football games between Division IA colleges during regular season Fall 2000 [48].
(5)
HEP: the coauthorships network of scientists who posted preprints on the high-energy theory archive from 1995 to 1999 [49].
(6)
Infectious (INF): a network of people’s face-to-face contacts in the exhibition “Infectious: Stay Away” in 2009 at the Science Gallery in Dublin [50].
(7)
Jazz: a network of Jazz musicians [51].
(8)
NetScience (NS): a network of coauthorships between scientists working on network theory and experiment [52].
(9)
Political blogs (PB): a network of blogs about US politics [53].
(10)
USAir: a network of the US air transportation system [17].In this work, all networks are treated as undirected and unweighted networks, and only the giant component of each network is used. Table2 lists the basic statistics of the giant components of these networks.Table 2
The basic statistics of the giant components of the 10 networks.V and E are the total numbers of nodes and edges, respectively. k and d present the average degree and the average shortest distance, respectively. C and r indicate the clustering coefficient [45] and assortative coefficient [54], respectively. H is the degree heterogeneity [17], and e is the network efficiency [55].
Networks
V
E
k
d
C
r
H
e
CE
297
2148
14.465
2.455
0.292
−0.163
1.801
0.445
Email
1133
5451
9.622
3.606
0.220
0.078
1.942
0.300
FBK
4015
87,882
43.777
3.985
0.595
0.071
2.427
0.294
FTB
115
613
10.661
2.508
0.403
0.162
1.007
0.450
HEP
5835
13,815
4.735
7.026
0.506
0.185
1.926
0.155
INF
410
2765
13.488
3.631
0.456
0.226
1.388
0.323
Jazz
198
2742
27.697
2.235
0.617
0.020
1.395
0.513
NS
379
914
4.823
6.042
0.741
−0.082
1.663
0.203
PB
1222
16,714
27.355
2.738
0.320
−0.221
2.971
0.398
USAir
332
2126
12.807
2.738
0.625
−0.208
3.464
0.406


### 5.2. Friedman Test

To further analyze the statistical significance of the proposed method, the Friedman test [56] is introduced in our experiments. This test is a nonparametric statistical hypothesis test used to compare multiple methods on a group of datasets [57]. It ranks the methods for each dataset separately according to their accuracy; the best performing method getting rank 1, the second best rank 2, and so on. In case of ties, average ranks are assigned.Givenk methods and N datasets, ri,j denotes the rank of the ith method on the jth dataset, and Ri is the average rank of the ith method, Ri=1/N∑jri,j. The null-hypothesis in Friedman test is that all the methods are equivalent and then their ranks Ri should be equal. The Friedman statistic is
(36)χF2=12Nkk+1∑iRi2−kk+124,which is distributed according to χF2 with k−1 degrees of freedom. Later, Iman and Davenport found that Friedman statistic is undesirably conservative and presented a better statistic [58], which is
(37)FF=N−1χF2Nk−1−χF2.This statistic is distributed according to theF-distribution with k−1 and k−1N−1 degrees of freedom. If FF is greater than the critical value of Fk−1,k−1N−1, the null-hypothesis is rejected [57]. Consequently, there are significant differences between these approaches.If the null-hypothesis is rejected, a post-hoc test is further proceeded to analyze the significant differences. The critical difference is defined as(38)CD=qαkk+16N,where qα is a critical value for post-hoc test [57]. If their average ranks differ by at least the critical difference, the performance of two approaches is significantly different.


### 5.3. Results and Analysis

Table3 lists the predicted results of different methods under the AUC metric on the 10 networks. The numbers in the round brackets are the ranks. In case of ties, average ranks are assigned. These results are the average of 50 independent realizations for each network. In each realization, we randomly split a network into a training set and a testing set, which contain 90% and 10% links, respectively. The best value for each network is highlighted in boldface. It is evident from Table 3 that LPTOPSIS achieves the best accuracy in terms of AUC on Email, FBK, FTB, INF, and NS and obtains the second best on CE and PB. These results are fairly decent. On HEP, LP outperforms others because this network possesses high average shortest distance, small average degree, and network efficiency. In other words, the network of HEP is very sparse (see Table 2), so the local methods, such as RA, CAR, and CCLP, obtain lower accuracy than LP. As stated in [23], in the relatively sparse network, common neighbor-based methods are less distinguishable. Whereas, the additional information provided by the 3-hop paths introduced by LP can make the similarities much more distinguishable and thus enhances the accuracy. Although LPTOPSIS integrates the advantage of LP index, the CAR index, which is not suitable for very sparse networks, weakens its performance. On Jazz and USAir, the proposed method gets rank 4 and 3, respectively. That is resulted from the poor accuracy of LP index on both networks. In this paper, we uniformly set the parameter of LP index as 0.001; however, the optimal value of the parameter is varying on different networks [21, 23], and detecting the optimal value is very time-consuming. In addition, LRm manifests fairly good predicted results, which obtains three best and three second. Generally speaking, LPTOPSIS performs the best and LRm does the second. The reason is that both methods aggregate several structural features. However, other baselines do not obtain satisfactory results. Take LP index as an example, it is ranked first on HEP but ranked seventh on USAir and eighth on Jazz. In a nutshell, the proposed method is more stable on different networks than baselines. For the MaxE method, which uncovers the missing links by reconstructing the network at hand based on the exponential random graph framework, it performs relative poorly on the networks with well-defined community, such as FBK, FTB, and Email. The reason is the configuration model used in MaxE to reconstruct the network may not be the optimal generative model for those networks. Actually, determining the optimal generative model is very difficult. Nevertheless, on the network with core-periphery structure, for example, PB and USAir, MaxE achieves good accuracy under the metric of AUC. The corresponding values are 0.9009 and 0.8887. These values are acceptable. The configuration model of MaxE takes as input just the nodes degrees; networks with core-periphery structure seem to be largely explained by the degree sequences [28]. Thus, for networks with a core-periphery structure, the MaxE is suitable.Table 3
AUC values of different methods on 10 networks. The results are the average of 50 independent implementations with Ets/E=0.1. The best performance for each network is emphasized by boldface. The numbers in the round brackets are the ranks. In case of ties, average ranks are assigned.
RA
ADP
CAR
CCLP
LP
MI
MaxE
LRm
LNB_CN
LPTOPSIS
CE
0.8680(3)
0.8676(4)
0.7650(9)
0.8651(5)
0.8628(6)
0.8321(8)
0.7531(10)
0.8828(1)
0.8612(7)
0.8784(2)
Email
0.8461(6)
0.8465(5)
0.6968(10)
0.8421(8)
0.9005(2)
0.8514(4)
0.7814(9)
0.8957(3)
0.8458(7)
0.9078(1)
FBK
0.9944(2)
0.9943(3)
0.9842(9)
0.9921(7)
0.9923(5)
0.9891(8)
0.8312(10)
0.9935(4)
0.9923(6)
0.9954(1)
FTB
0.8464(4.5)
0.8464(4.5)
0.8146(8)
0.8420(7)
0.8613(2)
0.7967(9)
0.2318(10)
0.8531(3)
0.8425(6)
0.8636(1)
HEP
0.8995(4.5)
0.8995(4.5)
0.7068(9)
0.8628(7)
0.9160(1)
0.8043(8)
0.6647(10)
0.9121(2)
0.8993(6)
0.9108(3)
INF
0.9444(4.5)
0.9444(4.5)
0.8622(9)
0.9379(7)
0.9575(3)
0.9159(8)
0.7105(10)
0.9604(2)
0.9402(6)
0.9621(1)
Jazz
0.9699(3)
0.9711(2)
0.9528(7)
0.9579(6)
0.9499(8)
0.9455(9)
0.7688(10)
0.9723(1)
0.9584(5)
0.9667(4)
NS
0.9588(3)
0.9587(4)
0.8154(9)
0.9287(7)
0.9576(5)
0.8509(8)
0.6345(10)
0.9597(2)
0.9571(6)
0.9625(1)
PB
0.9230(6)
0.9232(5)
0.8921(10)
0.9209(8)
0.9289(3)
0.9238(4)
0.9009(9)
0.9383(1)
0.9213(7)
0.9321(2)
USAir
0.9516(2)
0.9517(1)
0.9127(8)
0.9381(6)
0.9268(7)
0.9122(9)
0.8887(10)
0.9454(4)
0.9404(5)
0.9475(3)Next, we applied the Friedman test [57] on the above results to analyze the significant differences between baselines and LPTOPSIS. Depending on Table 3, we get χF2=72.115 and FF=36.288. In this paper, there are 10 methods and 10 networks. FF is distributed according to the F-distribution with 10−1=9 and 10−1×10−1=81 degrees of freedom. The critical value of F9,81 for α=0.05 is 1.998. Due to FF=36.288>1.998, we reject the null-hypothesis, which states that all the methods are equivalent.Since the null-hypothesis is rejected, we proceed with a post-hoc test. In our experiments, the Bonferroni-Dunn test [59], in which all methods are compared only to a control method and not between themselves [57], is employed to estimate the significant differences between LPTOPSIS and baselines. The critical difference is CD=2.773×10×10+1/6×10=3.75 for α=0.05. The results are graphically presented in Figure 4. In the axis, the best rank is on the left side. Figure 4 shows that LPTOPSIS is significantly better than LNB_CN, CCLP, MI, CAR, and MaxE. Although there are no significant differences of LRm, ADP, RA, and LP with LPTOPSIS, the average rank of LPTOPSIS is better than them.Figure 4
Comparison ofLPTOPSIS against the others with the Bonferroni-Dunn test. This comparison is based on the results in Table 3. All methods with ranks outside the marked interval are significantly different from LPTOPSIS.Furthermore, Figure5 describes the changes of AUC of all prediction methods for varying proportions of training set Etr in E (from 0.7 to 0.9). Clearly, AUC scores show an upward trend when the proportion increase from 0.7 to 0.9 in Figure 5. The reason is event; the more proportion of training set Etr is, the more information is provided for training. On the contrary, low proportions of Etr will enhance the difficulty of link prediction. Therefore, we do not conduct experiment with lower proportions of Etr, for example, 0.6 and 0.5. According to Figure 5, the AUC values of the proposed method, with varying sizes of training set, are either the best or close to the best. Figure 5(k) exhibits the average ranks of different methods for varying proportions of Etr. It can be observed that the proposed method always gets the best. The significant analysis for Etr/E=0.9 (that is, Ets/E=0.1) is already presented above. Now we give the analysis for Etr/E=0.8 and 0.7, respectively. The corresponding values of FF are 25.415 and 31.898, respectively. Both values are greater than 1.998 (the critical value of F9,81). That means the null-hypothesis, which states that all these methods are equivalent, is rejected. The results of Bonferroni-Dunn test [59] are depicted in Figure 6. From Figure 6, LPTOPSIS ranks first and is significantly better than LNB_CN, CCLP, MI, CAR, and MaxE. These results are similar with that in Figure 4.Figure 5
AUC results on 10 networks with different proportions of training set Etr. The results are the average of 50 independent implementations.
(a)
CE
(b)
Email
(c)
FBK
(d)
FTB
(e)
HEP
(f)
INF
(g)
Jazz
(h)
NS
(i)
PB
(j)
USAir
(k)
Average ranks of different methods on 10 networksFigure 6
The Bonferroni-Dunn test forEtr/E=0.8 and 0.7. All methods with ranks outside the marked interval are significantly different from LPTOPSIS.
(a)
Etr/E=0.8
(b)
Etr/E=0.7On the other hand, the metric ofPrecision focuses on the top-L predicted links. Figure 7 shows the prediction results under the metric of Precision on the 10 networks with different sizes of L. These results demonstrate that LPTOPSIS is invariably in the top place over most networks. However, baselines have wild fluctuations on different networks. For instance, RA index achieves the best on NS, but falls to the second last on PB. In addition, in most methods, Precision shows slightly downward trend when the size of L increases. The reason is that the increase of L, the probability to uncover relevant items will decrease, and then the value of Precision will lower. Figure 7(k) presents the average rank of each method over the 10 networks with respect to different sizes of L. Clearly, LPTOPSIS outperforms others except when L=10 and 20. MI index ranks first when L=10 and 20 but falls behind LPTOPSIS for other values of L. MI index is superior to other baselines under Precision; however, its AUC values are not satisfactory enough. On the whole, LRm performs mediocre in terms of Precision, in spite of its quite good performance under the metric of AUC.Figure 7
Precision results on 10 networks with different values ofL. The results are the average of 50 independent implementations with Ets/E=0.1. The size of Ets for FTB is 61, so the max L selected is 60. Similarly, the max L selected for NS is 90.
(a)
CE
(b)
Email
(c)
FBK
(d)
FTB
(e)
HEP
(f)
INF
(g)
Jazz
(h)
NS
(i)
PB
(j)
USAir
(k)
Average ranks of different methods on 10 networksAt last, we depict the changes ofPrecision of all prediction methods for varying proportions of training set Etr in E (from 0.7 to 0.9) in Figure 8. In this experiment, we set L=Ets for all networks. It can be seen from Figure 8 that Precision exhibits the opposite changing trend in comparison with AUC, that is, Precision scores show a downward trend when the proportion increase from 0.7 to 0.9. This phenomenon has also been observed in [5]. The main reason is that the decrease of training set Etr will lead to weak n1 and strong n2 in the definition of AUC (see (1)) and then lower the value of AUC [5]. Oppositely, the increase of testing set Ets, the probability to obtain the relevant items will increase, which makes it easier for uncovering the missing links [5]. Therefore, combining both metrics in the evaluation of the accuracy of a prediction method is necessary in practical application. Figure 8(k) shows the average ranks of different methods for Etr/E=0.7, 0.8, and 0.9 in terms of Precision. In general, the proposed method is in the second place when Etr/E=0.7 and ranks first when Etr/E=0.8 and 0.9. This indicates the stable performance of the proposed method under the metric of Precision.Figure 8
Precision results on 10 networks with different proportions of training set. The results are the average of 50 independent implementations. In this figure, L=∣Ets∣ for all networks.
(a)
CE
(b)
Email
(c)
FBK
(d)
FTB
(e)
HEP
(f)
INF
(g)
Jazz
(h)
NS
(i)
PB
(j)
USAir
(k)
Average ranks of different methods on 10 networksFrom the aforementioned results, we can conclude that the proposed method outperforms the compared indices and is applicable to more networks. The striking characteristic of the proposed method is that it aggregates several structural features of a network by means of combiningRA, LP, and CAR indices using TOPSIS. Thus, the proposed method can automatically adapt to diverse networks and then performs stability on various networks. Although the ADP index is claimed to be able to automatically adapt to the structure of a network by adaptively penalizing the degrees of common neighbors, it still focuses, in effect, on one structure in a network. Therefore, there are gaps between the accuracy of ADP and LPTOPSIS. Similar with LPTOPSIS, LRm aggregates three structural features with logistic regression. This method achieves the second best under AUC, whereas its accuracy under Precision is very general.


## 5.1. Datasets

To evaluate the performance of the proposed method, we use 10 real-world networks collected from various fields in this work (all data are downloaded fromhttp://deim.urv.cat/~alexandre.arenas/data/welcome.htm, http://www-personal.umich.edu/~mejn/netdata/, http://vlado.fmf.uni-lj.si/pub/networks/data/, http://noesis.ikor.org/datasets/link-prediction). The brief descriptions of these networks are given as follows:
(1)
C. elegans (CE): the neural network of a Caenorhabditis elegans worm [45].
(2)
Email: a network of email interchanges between members of a university [46].
(3)
Facebook (FBK): a social network collected fromhttps://www.facebook.com/ [47].
(4)
Football (FTB): the network of American football games between Division IA colleges during regular season Fall 2000 [48].
(5)
HEP: the coauthorships network of scientists who posted preprints on the high-energy theory archive from 1995 to 1999 [49].
(6)
Infectious (INF): a network of people’s face-to-face contacts in the exhibition “Infectious: Stay Away” in 2009 at the Science Gallery in Dublin [50].
(7)
Jazz: a network of Jazz musicians [51].
(8)
NetScience (NS): a network of coauthorships between scientists working on network theory and experiment [52].
(9)
Political blogs (PB): a network of blogs about US politics [53].
(10)
USAir: a network of the US air transportation system [17].In this work, all networks are treated as undirected and unweighted networks, and only the giant component of each network is used. Table2 lists the basic statistics of the giant components of these networks.Table 2
The basic statistics of the giant components of the 10 networks.V and E are the total numbers of nodes and edges, respectively. k and d present the average degree and the average shortest distance, respectively. C and r indicate the clustering coefficient [45] and assortative coefficient [54], respectively. H is the degree heterogeneity [17], and e is the network efficiency [55].
Networks
V
E
k
d
C
r
H
e
CE
297
2148
14.465
2.455
0.292
−0.163
1.801
0.445
Email
1133
5451
9.622
3.606
0.220
0.078
1.942
0.300
FBK
4015
87,882
43.777
3.985
0.595
0.071
2.427
0.294
FTB
115
613
10.661
2.508
0.403
0.162
1.007
0.450
HEP
5835
13,815
4.735
7.026
0.506
0.185
1.926
0.155
INF
410
2765
13.488
3.631
0.456
0.226
1.388
0.323
Jazz
198
2742
27.697
2.235
0.617
0.020
1.395
0.513
NS
379
914
4.823
6.042
0.741
−0.082
1.663
0.203
PB
1222
16,714
27.355
2.738
0.320
−0.221
2.971
0.398
USAir
332
2126
12.807
2.738
0.625
−0.208
3.464
0.406


## 5.2. Friedman Test

To further analyze the statistical significance of the proposed method, the Friedman test [56] is introduced in our experiments. This test is a nonparametric statistical hypothesis test used to compare multiple methods on a group of datasets [57]. It ranks the methods for each dataset separately according to their accuracy; the best performing method getting rank 1, the second best rank 2, and so on. In case of ties, average ranks are assigned.Givenk methods and N datasets, ri,j denotes the rank of the ith method on the jth dataset, and Ri is the average rank of the ith method, Ri=1/N∑jri,j. The null-hypothesis in Friedman test is that all the methods are equivalent and then their ranks Ri should be equal. The Friedman statistic is
(36)χF2=12Nkk+1∑iRi2−kk+124,which is distributed according to χF2 with k−1 degrees of freedom. Later, Iman and Davenport found that Friedman statistic is undesirably conservative and presented a better statistic [58], which is
(37)FF=N−1χF2Nk−1−χF2.This statistic is distributed according to theF-distribution with k−1 and k−1N−1 degrees of freedom. If FF is greater than the critical value of Fk−1,k−1N−1, the null-hypothesis is rejected [57]. Consequently, there are significant differences between these approaches.If the null-hypothesis is rejected, a post-hoc test is further proceeded to analyze the significant differences. The critical difference is defined as(38)CD=qαkk+16N,where qα is a critical value for post-hoc test [57]. If their average ranks differ by at least the critical difference, the performance of two approaches is significantly different.


## 5.3. Results and Analysis

Table3 lists the predicted results of different methods under the AUC metric on the 10 networks. The numbers in the round brackets are the ranks. In case of ties, average ranks are assigned. These results are the average of 50 independent realizations for each network. In each realization, we randomly split a network into a training set and a testing set, which contain 90% and 10% links, respectively. The best value for each network is highlighted in boldface. It is evident from Table 3 that LPTOPSIS achieves the best accuracy in terms of AUC on Email, FBK, FTB, INF, and NS and obtains the second best on CE and PB. These results are fairly decent. On HEP, LP outperforms others because this network possesses high average shortest distance, small average degree, and network efficiency. In other words, the network of HEP is very sparse (see Table 2), so the local methods, such as RA, CAR, and CCLP, obtain lower accuracy than LP. As stated in [23], in the relatively sparse network, common neighbor-based methods are less distinguishable. Whereas, the additional information provided by the 3-hop paths introduced by LP can make the similarities much more distinguishable and thus enhances the accuracy. Although LPTOPSIS integrates the advantage of LP index, the CAR index, which is not suitable for very sparse networks, weakens its performance. On Jazz and USAir, the proposed method gets rank 4 and 3, respectively. That is resulted from the poor accuracy of LP index on both networks. In this paper, we uniformly set the parameter of LP index as 0.001; however, the optimal value of the parameter is varying on different networks [21, 23], and detecting the optimal value is very time-consuming. In addition, LRm manifests fairly good predicted results, which obtains three best and three second. Generally speaking, LPTOPSIS performs the best and LRm does the second. The reason is that both methods aggregate several structural features. However, other baselines do not obtain satisfactory results. Take LP index as an example, it is ranked first on HEP but ranked seventh on USAir and eighth on Jazz. In a nutshell, the proposed method is more stable on different networks than baselines. For the MaxE method, which uncovers the missing links by reconstructing the network at hand based on the exponential random graph framework, it performs relative poorly on the networks with well-defined community, such as FBK, FTB, and Email. The reason is the configuration model used in MaxE to reconstruct the network may not be the optimal generative model for those networks. Actually, determining the optimal generative model is very difficult. Nevertheless, on the network with core-periphery structure, for example, PB and USAir, MaxE achieves good accuracy under the metric of AUC. The corresponding values are 0.9009 and 0.8887. These values are acceptable. The configuration model of MaxE takes as input just the nodes degrees; networks with core-periphery structure seem to be largely explained by the degree sequences [28]. Thus, for networks with a core-periphery structure, the MaxE is suitable.Table 3
AUC values of different methods on 10 networks. The results are the average of 50 independent implementations with Ets/E=0.1. The best performance for each network is emphasized by boldface. The numbers in the round brackets are the ranks. In case of ties, average ranks are assigned.
RA
ADP
CAR
CCLP
LP
MI
MaxE
LRm
LNB_CN
LPTOPSIS
CE
0.8680(3)
0.8676(4)
0.7650(9)
0.8651(5)
0.8628(6)
0.8321(8)
0.7531(10)
0.8828(1)
0.8612(7)
0.8784(2)
Email
0.8461(6)
0.8465(5)
0.6968(10)
0.8421(8)
0.9005(2)
0.8514(4)
0.7814(9)
0.8957(3)
0.8458(7)
0.9078(1)
FBK
0.9944(2)
0.9943(3)
0.9842(9)
0.9921(7)
0.9923(5)
0.9891(8)
0.8312(10)
0.9935(4)
0.9923(6)
0.9954(1)
FTB
0.8464(4.5)
0.8464(4.5)
0.8146(8)
0.8420(7)
0.8613(2)
0.7967(9)
0.2318(10)
0.8531(3)
0.8425(6)
0.8636(1)
HEP
0.8995(4.5)
0.8995(4.5)
0.7068(9)
0.8628(7)
0.9160(1)
0.8043(8)
0.6647(10)
0.9121(2)
0.8993(6)
0.9108(3)
INF
0.9444(4.5)
0.9444(4.5)
0.8622(9)
0.9379(7)
0.9575(3)
0.9159(8)
0.7105(10)
0.9604(2)
0.9402(6)
0.9621(1)
Jazz
0.9699(3)
0.9711(2)
0.9528(7)
0.9579(6)
0.9499(8)
0.9455(9)
0.7688(10)
0.9723(1)
0.9584(5)
0.9667(4)
NS
0.9588(3)
0.9587(4)
0.8154(9)
0.9287(7)
0.9576(5)
0.8509(8)
0.6345(10)
0.9597(2)
0.9571(6)
0.9625(1)
PB
0.9230(6)
0.9232(5)
0.8921(10)
0.9209(8)
0.9289(3)
0.9238(4)
0.9009(9)
0.9383(1)
0.9213(7)
0.9321(2)
USAir
0.9516(2)
0.9517(1)
0.9127(8)
0.9381(6)
0.9268(7)
0.9122(9)
0.8887(10)
0.9454(4)
0.9404(5)
0.9475(3)Next, we applied the Friedman test [57] on the above results to analyze the significant differences between baselines and LPTOPSIS. Depending on Table 3, we get χF2=72.115 and FF=36.288. In this paper, there are 10 methods and 10 networks. FF is distributed according to the F-distribution with 10−1=9 and 10−1×10−1=81 degrees of freedom. The critical value of F9,81 for α=0.05 is 1.998. Due to FF=36.288>1.998, we reject the null-hypothesis, which states that all the methods are equivalent.Since the null-hypothesis is rejected, we proceed with a post-hoc test. In our experiments, the Bonferroni-Dunn test [59], in which all methods are compared only to a control method and not between themselves [57], is employed to estimate the significant differences between LPTOPSIS and baselines. The critical difference is CD=2.773×10×10+1/6×10=3.75 for α=0.05. The results are graphically presented in Figure 4. In the axis, the best rank is on the left side. Figure 4 shows that LPTOPSIS is significantly better than LNB_CN, CCLP, MI, CAR, and MaxE. Although there are no significant differences of LRm, ADP, RA, and LP with LPTOPSIS, the average rank of LPTOPSIS is better than them.Figure 4
Comparison ofLPTOPSIS against the others with the Bonferroni-Dunn test. This comparison is based on the results in Table 3. All methods with ranks outside the marked interval are significantly different from LPTOPSIS.Furthermore, Figure5 describes the changes of AUC of all prediction methods for varying proportions of training set Etr in E (from 0.7 to 0.9). Clearly, AUC scores show an upward trend when the proportion increase from 0.7 to 0.9 in Figure 5. The reason is event; the more proportion of training set Etr is, the more information is provided for training. On the contrary, low proportions of Etr will enhance the difficulty of link prediction. Therefore, we do not conduct experiment with lower proportions of Etr, for example, 0.6 and 0.5. According to Figure 5, the AUC values of the proposed method, with varying sizes of training set, are either the best or close to the best. Figure 5(k) exhibits the average ranks of different methods for varying proportions of Etr. It can be observed that the proposed method always gets the best. The significant analysis for Etr/E=0.9 (that is, Ets/E=0.1) is already presented above. Now we give the analysis for Etr/E=0.8 and 0.7, respectively. The corresponding values of FF are 25.415 and 31.898, respectively. Both values are greater than 1.998 (the critical value of F9,81). That means the null-hypothesis, which states that all these methods are equivalent, is rejected. The results of Bonferroni-Dunn test [59] are depicted in Figure 6. From Figure 6, LPTOPSIS ranks first and is significantly better than LNB_CN, CCLP, MI, CAR, and MaxE. These results are similar with that in Figure 4.Figure 5
AUC results on 10 networks with different proportions of training set Etr. The results are the average of 50 independent implementations.
(a)
CE
(b)
Email
(c)
FBK
(d)
FTB
(e)
HEP
(f)
INF
(g)
Jazz
(h)
NS
(i)
PB
(j)
USAir
(k)
Average ranks of different methods on 10 networksFigure 6
The Bonferroni-Dunn test forEtr/E=0.8 and 0.7. All methods with ranks outside the marked interval are significantly different from LPTOPSIS.
(a)
Etr/E=0.8
(b)
Etr/E=0.7On the other hand, the metric ofPrecision focuses on the top-L predicted links. Figure 7 shows the prediction results under the metric of Precision on the 10 networks with different sizes of L. These results demonstrate that LPTOPSIS is invariably in the top place over most networks. However, baselines have wild fluctuations on different networks. For instance, RA index achieves the best on NS, but falls to the second last on PB. In addition, in most methods, Precision shows slightly downward trend when the size of L increases. The reason is that the increase of L, the probability to uncover relevant items will decrease, and then the value of Precision will lower. Figure 7(k) presents the average rank of each method over the 10 networks with respect to different sizes of L. Clearly, LPTOPSIS outperforms others except when L=10 and 20. MI index ranks first when L=10 and 20 but falls behind LPTOPSIS for other values of L. MI index is superior to other baselines under Precision; however, its AUC values are not satisfactory enough. On the whole, LRm performs mediocre in terms of Precision, in spite of its quite good performance under the metric of AUC.Figure 7
Precision results on 10 networks with different values ofL. The results are the average of 50 independent implementations with Ets/E=0.1. The size of Ets for FTB is 61, so the max L selected is 60. Similarly, the max L selected for NS is 90.
(a)
CE
(b)
Email
(c)
FBK
(d)
FTB
(e)
HEP
(f)
INF
(g)
Jazz
(h)
NS
(i)
PB
(j)
USAir
(k)
Average ranks of different methods on 10 networksAt last, we depict the changes ofPrecision of all prediction methods for varying proportions of training set Etr in E (from 0.7 to 0.9) in Figure 8. In this experiment, we set L=Ets for all networks. It can be seen from Figure 8 that Precision exhibits the opposite changing trend in comparison with AUC, that is, Precision scores show a downward trend when the proportion increase from 0.7 to 0.9. This phenomenon has also been observed in [5]. The main reason is that the decrease of training set Etr will lead to weak n1 and strong n2 in the definition of AUC (see (1)) and then lower the value of AUC [5]. Oppositely, the increase of testing set Ets, the probability to obtain the relevant items will increase, which makes it easier for uncovering the missing links [5]. Therefore, combining both metrics in the evaluation of the accuracy of a prediction method is necessary in practical application. Figure 8(k) shows the average ranks of different methods for Etr/E=0.7, 0.8, and 0.9 in terms of Precision. In general, the proposed method is in the second place when Etr/E=0.7 and ranks first when Etr/E=0.8 and 0.9. This indicates the stable performance of the proposed method under the metric of Precision.Figure 8
Precision results on 10 networks with different proportions of training set. The results are the average of 50 independent implementations. In this figure, L=∣Ets∣ for all networks.
(a)
CE
(b)
Email
(c)
FBK
(d)
FTB
(e)
HEP
(f)
INF
(g)
Jazz
(h)
NS
(i)
PB
(j)
USAir
(k)
Average ranks of different methods on 10 networksFrom the aforementioned results, we can conclude that the proposed method outperforms the compared indices and is applicable to more networks. The striking characteristic of the proposed method is that it aggregates several structural features of a network by means of combiningRA, LP, and CAR indices using TOPSIS. Thus, the proposed method can automatically adapt to diverse networks and then performs stability on various networks. Although the ADP index is claimed to be able to automatically adapt to the structure of a network by adaptively penalizing the degrees of common neighbors, it still focuses, in effect, on one structure in a network. Therefore, there are gaps between the accuracy of ADP and LPTOPSIS. Similar with LPTOPSIS, LRm aggregates three structural features with logistic regression. This method achieves the second best under AUC, whereas its accuracy under Precision is very general.


## 6. Conclusion

Link prediction aims at finding the missing links and predicting future links in a network. As an important research topic in complex network analysis, it has drawn increasing attention from disparate scientific communities. Among various categories of approaches, similarity-based methods have become the mainstream due to their low complexity and high interpretability. In general, one similarity-based method assumes that its similarity measure is applicable to diverse networks. However, different networks always have different inner topological structures, which results in the unstable performance of similarity-based methods. Inspired by the applications of multiple-attribute decision-making (MADM) problem, we proposed in this paper a novel link prediction method. The proposed method employs three classical similarity indices, that is,RA, LP, and CAR, as the attributes and aggregates their scores by means of TOPSIS, a well-known MADM method, to make a decision for ranking unconnected node pairs.The accuracy of the proposed method is experimentally evaluated over 10 real-world networks with the metrics ofAUC and Precision. The experimental results indicate that the proposed method is not only more effective but also stable than the competing methods. The robustness comparisons of the proposed method with baselines for varying sizes of training sets suggest the robust of the proposed method. The results in our experiments demonstrate that MADM method is an effective way to solve the link prediction problem. In the future work, we can further study the application of MADM method in link prediction.



---

*Source: 3579758-2018-09-02.xml*