# Predicting Missing Links Based on a New Triangle Structure

Authors: Shenshen Bai; Longjie Li; Jianjun Cheng; Shijin Xu; Xiaoyun Chen
Journal: Complexity
 (2018)

---

## Abstract

With the rapid growth of various complex networks, link prediction has become increasingly important because it can discover the missing information and predict future interactions between nodes in a network. Recently, the CAR and CCLP indexes have been presented for link prediction by means of different triangle structure information. However, both indexes may lose the contributions of some shared neighbors. We propose in this work a new index to make up the weakness and then improve the accuracy of link prediction. The proposed index focuses on a new triangle structure, i.e., the triangle formed by one seed node, one common neighbor, and one other node. It emphasizes the importance of these triangles but does not ignore the contribution of any common neighbor. In addition, the proposed index adopts the theory of resource allocation by penalizing large-degree neighbors. The results of comparison with CN, AA, RA, ADP, CAR, CAA, CRA, and CCLP on 12 real-world networks show that the proposed index outperforms the compared methods in terms of AUC and ranking score.


---

## Body

## 1. Introduction

As a fundamental research hotspot in complex network analysis, link prediction has a wide range of applications in both theory and reality, such as analysis of network evolution [1, 2], recommendation system [3], and checking potential interactions between proteins in biological networks [4, 5]. The basic task of link prediction is to estimate the missing or latent existent links between unconnected nodes in a network [6, 7]. To date, a host of algorithms and models have been proposed for link prediction [6, 8, 9]. Reference [8] groups them into two ways:similarity-based approaches andlearning-based approaches. A similarity-based approach computes similarity scores between unconnected nodes based on the known information. Then, a ranked list of node pairs in descending order according to their similarity scores is obtained and the node pairs at the top are thought most likely to have links. A learning-based approach formalizes the link prediction problem into a binary classification task [10] and uses machine learning methods to solve the problem. The key job in a learning-based approach is to construct the feature vectors of node pairs. In general, learning-based approaches are more complicated than similarity-based ones.The hypothesis behind similarity-based approaches isthe more similar that two nodes are, the more likely that a link exists between them [8]. This idea is simple and intuitive. Thus, the study of this kind of approaches has become the mainstream [6, 9]. The Common Neighbors (CN) index [11], as its name suggests, simply counts the number of common neighbors between two nodes. The Adamic-Adar (AA) [12] and Resource Allocation (RA) [13] indexes are two variants of the CN index; they penalize the contributions of large-degree common neighbors. These indexes are called local methods because they only use local structure information. Besides, some global and quasilocal methods have also been proposed by researchers, such as Katz [14], SimRank [15], Random Walks with Restart [16], Local Path [17], FriendLink [18], and Local Random Walk [19].With the increasing growth of sizes of complex networks, local methods are still good candidates because they are more efficient in terms of running time than global and quasilocal methods. Therefore, we focus in this study on local methods. Recently, Cannistraciet al. proposed the CAR index [20], which suggests that links between the common neighbors, i.e.,local-community-links (LCLs), are more valuable than common neighbors in link prediction. In CAR index, alocal community is a triangle passing through two common neighbors and one seed node. In the example network shown in Figure 1(a), there is one LCL between the common neighbors of seed nodes a and b (see Figure 1(b)). Thus, CAR index assigns a similarity score of four to nodes a and b. However, if we remove the link between c and d, CAR will assign a zero similarity score to a and b, even though they have four common neighbors. In addition, the idea of LCL is also plugged into AA, RA, and Jaccard indexes [20]. Later, Wuet al. proposed the CCLP index based on the clustering coefficients of common neighbors. This index considers all triangles passing through a common neighbor. For the example network in Figure 1(a), there are triangles passing through nodes c, d, and f, respectively (see Figure 1(c)). Thus, CCLP index accumulates the clustering coefficients of nodes c, d, and f when calculating the similarity between a and b, but utterly neglects the contribution of node e. In real-world networks, it is possible that there are no triangles passing through some or even all shared neighbors of one node pair. Thus, CAR and CCLP indexes may assign a very low or even zero similarity score to the node pair, even if it has many common neighbors.Figure 1
Triangles used in similarity indexes.In this paper, we defines a new type of triangle structure, called TRA-triangle, which is formed by one seed node, one common neighbor, and one other node (see Figure1(d)). Based on the TRA-triangle, a new similarity index, namely, TRA index, is proposed for link prediction. This index suggests that the common neighbors that can form TRA-triangles with a seed node are more important than others. In addition, the proposed index also penalizes the large-degree neighbors, as done in RA index [13]. Although all the TRA, CAR-based, and CCLP indexes are based on triangle structures, the intuitions behind them are different. The CAR-based indexes believe that LCLs are more valuable than common neighbors. The CCLP index is inspired by CAR index but employs all triangles passing through common neighbors, while the TRA index, which only uses the TRA-triangles, strikes a balance between CAR and CCLP. Furthermore, as aforementioned, CAR-based and CCLP indexes lose the contribution of those common neighbors with no triangles passing through them, whereas TRA index counts the contribution of all kinds of common neighbors. Therefore, TRA index can achieve better prediction accuracy than CAR-based indexes and CCLP index. The accuracy of TRA index is evaluated on 12 real-world networks from various fields. The experimental results show that our index is far superior to CAR-based indexes and CCLP index. Take the network of HEP as an example, which is a very sparse network, the improvements made by TRA on CAR and CCLP, under the metric of AUC, are up to 26.9% and 4.2%, respectively.The rest of the paper is structured as follows. In Section2, we give the description of the link prediction problem and the evaluation metrics, list the compared methods and networks, and depict the Wilcoxon signed-ranks test. Section 3 introduces the proposed method. In Section 4, the experimental results and performance analysis of the proposed method are presented. Finally, Section 5 concludes this work.


## 2. Preliminaries

### 2.1. Problem Description and Metric

Given an undirected and unweighted networkG(V,E), in which V and E are the node set and link set, respectively, in this study, multilinks and self-loops are not allowed. Let N=|V| be the number of nodes in the network, and let U be the universal possible link set, which contains N(N-1)/2 possible links. Then, the set of nonobserved links or nonexisting links is U-E. Suppose there are some missing links in U-E, the task of link prediction is to find those links. A similarity-based approach assigns a similarity score to each node pair in U-E and assumes that the higher score a node pair has, the more likely there is a link between them.To test the performance of a similarity index, we randomly divide the link setE into two parts: training set Etr and testing set Ets, such that E=Etr∪Ets and Etr∩Ets=∅. Etr is supposed to be the observed information, and Ets is used for testing. Two parameter-free metrics are employed to quantify the accuracy of link prediction algorithms: AUC [6] and ranking score [21, 22]. In this situation, the AUC score can be interpreted as the probability that a randomly selected missing link (i.e., a link in Ets) is given a higher score than a randomly selected nonexistent link (i.e., a link in U-E). When implementing, if we perform n independent comparisons, there are n1 times that the missing link has higher score and n2 times that they have the same score. The AUC value is then computed as(1)AUC=n1+0.5n2n.Ranking score (RS) takes the ranks of links in testing set after sorting in descend order according to their similarity scores into consideration. LetH=U-Etr be the set of nonobserved links. Let ei be a missing link in Ets and ri be its rank. The ranking score of ei is defined as RS(ei)=ri/|H|, and the ranking score of the link prediction result is as follows:(2)RS=1Ets∑ei∈EtsRSei=1Ets∑ei∈EtsriH.Note that the AUC value is the higher the better, whereas the ranking score is the smaller the better.


### 2.2. Local Similarity Indexes

As yet, many similarity indexes have been proposed for link prediction [6, 8, 9]. Here, we list some local similarity indexes that will be used in our experiments for the purpose of comparison.( 1 ) Common Neighbor (CN) index [11] defines the similarity between x and y as the number of their common neighbors, which is(3)CNx,y=Γx∩Γy,where Γ(x) denotes the set of neighbors of node x.( 2 ) Adamic-Adar (AA) index [12] is a variant of CN index, which believes that small-degree neighbors have more contributions than large-degree neighbors when computing similarity. Its definition is as follows:(4)AAx,y=∑z∈Γx∩Γy1log⁡kz,where kz is the degree of node z.( 3 ) Resource Allocation (RA) index [13] defines the similarity between x and y as the amount of resource that y received from x through their common neighbors, which is(5)RAx,y=∑z∈Γx∩Γy1kz.( 4 ) Adaptive Degree Penalization (ADP) index [23] penalizes a common neighbor according to its degree and the average clustering coefficient of the network. Therefore, it can automatically adapt to the network. The definition of ADP index is as follows:(6)ADPx,y=∑z∈Γx∩Γykz-βC,where β is a constant and C is the average clustering coefficient of the network. We set β=2.5, as suggested by the authors.( 5 ) CAR index [20] suggests that two seed nodes are more likely to link together if there are links between their common neighbors, which is defined as(7)CARx,y=CNx,y·∑z∈Γx∩ΓyLz2,where L(z) is the number of links between z and other common neighbors of x and y.( 6 ) CAA and CRA indexes [20] are generated by plugging the idea of CAR index into the AA and RA indexes, respectively, which are defined as(8)CAAx,y=∑z∈Γx∩ΓyLzlog⁡kz,(9)CRAx,y=∑z∈Γx∩ΓyLzkz.( 7 ) CCLP index [24] computes the similarity between x and y by employing clustering coefficient of common neighbors, which is(10)CCLPx,y=∑z∈Γx∩ΓyCCz,where CCz denotes the clustering coefficient of node z, which is(11)CCz=2tzkzkz-1,in which tz is the number of triangles passing through node z.


### 2.3. Networks

In this study, we use 12 real-world networks drawn from various fields to evaluate the effectiveness of link prediction methods.(1)
Advogato (ADV): a social network whose users are mainly free and open source software developers [25].(2)
C.elegans (CE): the neural network of a Caenorhabditis elegans worm [26].(3)
Dolphin: a social network of 62 dolphins in a community living off Doubtful Sound, New Zealand [27].(4)
Email: a network of email interchanges between members of a university [28].(5)
Foodweb (FW): a food web in Florida Bay during the rainy season [29].(6)
Hamster: a friendship network between users on hamsterster.com [30].(7)
HEP: the coauthorships network of scientists who posted preprints on the high-energy theory archive from 1995 to 1999 [31].(8)
Karate: the social network of a karate club at a US university [32].(9)
Political blogs (PB): a network of blogs about US politics [33].(10)
USAir: a network of the US air transportation system [6].(11)
Word: an adjacency network of common adjectives and noun in the novel “David Copperfield” by Charles Dickens [34].(12)
Yeast: the protein-protein interaction network of budding yeast [35].In this work, all the aforementioned networks are treated as undirected and unweighted networks, and only the giant component of each network is used. Table1 lists the basic statistics of the giant components of these networks.Table 1
The basic structural features of the giant components of the 12 networks.|V| and |E| are the total numbers of nodes and edges, respectively. D denotes the density, which is D=2|E|/|V|(|V|-1). 〈k〉 and 〈d〉 present the average degree and the average shortest distance, respectively. C and r indicate the clustering coefficient [26] and assortative coefficient [36], respectively. H is the degree heterogeneity [6], defined as H=k2/k2, and e is the network efficiency [37].
Networks | V | | E | D 〈 k 〉 〈 d 〉 C r H e ADV 5042 39227 3.1E-03 15.560 3.275 0.253 -0.096 5.303 0.324 CE 297 2148 4.9E-02 14.465 2.455 0.292 -0.163 1.801 0.445 Dolphin 62 159 8.4E-02 5.129 3.357 0.259 -0.044 1.327 0.379 Email 1133 5451 8.5E-03 9.622 3.606 0.220 0.078 1.942 0.300 FW 128 2075 2.6E-01 32.422 1.776 0.335 -0.112 1.237 0.622 Hamster 1788 12476 7.8E-03 13.955 3.453 0.143 -0.089 3.264 0.317 HEP 5835 13815 8.1E-04 4.735 7.026 0.506 0.185 1.926 0.155 Karate 34 78 1.4E-01 4.588 2.408 0.571 -0.476 1.693 0.492 PB 1222 16714 2.2E-02 27.355 2.738 0.320 -0.221 2.971 0.398 USAir 332 2126 3.9E-02 12.807 2.738 0.625 -0.208 3.464 0.406 Word 112 425 6.8E-02 7.589 2.536 0.173 -0.129 1.815 0.442 Yeast 2224 6609 2.7E-03 5.943 4.376 0.138 -0.105 2.803 0.246Given networkG(V,E), suppose x, y be two seed nodes. (x,y) is calleda seed node pair with common neighbors if they have at least one common neighbor. PΛ denotes the set of seed node pairs with common neighbors, formally(12)PΛ=x,y∣x,y∉E∧Γx∩Γy≠∅.Let x, y be two seed nodes, and z is one of their common neighbors. If CCz=0, we call z is azero-triangle-neighbor; otherwise, z is atriangle-neighbor. If L(z)≠0, z is called aCAR-triangle-neighbor and if △(x,y;z)≠0 (see (18)), z is called aTRA-triangle-neighbor. Let S△ be the set of triangle-neighbors, and SCAR, STRA denote the sets of CAR- and TRA-triangle-neighbors, respectively. Clearly, SCAR⊆STRA⊆S△. Let P∃(S¯△) and P∀(S¯△) be two subsets of PΛ. For any pair in P∃(S¯△), at least one of their shared neighbors is not a triangle-neighbor, and for any pair in P∀(S¯△), all of their shared neighbors are not triangle-neighbors. More explicitly,(13)P∃S¯△=x,y∈PΛ∣∃z∈Γx∩Γy∧z∉S△,P∀S¯△=x,y∈PΛ∣∀z∈Γx∩Γy∧z∉S△.Similarly, we define P∃(S¯TRA), P∀(S¯TRA), P∃(S¯CAR), and P∀(S¯CAR), which are(14)P∃S¯TRA=x,y∈PΛ∣∃z∈Γx∩Γy∧z∉STRA,P∀S¯TRA=x,y∈PΛ∣∀z∈Γx∩Γy∧z∉STRA,P∃S¯CAR=x,y∈PΛ∣∃z∈Γx∩Γy∧z∉SCAR,P∀S¯CAR=x,y∈PΛ∣∀z∈Γx∩Γy∧z∉SCAR.Correspondingly, the ratios of those subsets to PΛ are, respectively, defined as(15)R∃S¯△=P∃S¯△PΛ,R∀S¯△=P∀S¯△PΛ,R∃S¯TRA=P∃S¯TRAPΛ,R∀S¯TRA=P∀S¯TRAPΛ,R∃S¯CAR=P∃S¯CARPΛ,R∀S¯CAR=P∀S¯CARPΛ.Table 2 lists these ratios over the 12 networks.Table 2
The ratios of various seed pairs over the 12 networks.
Networks R ∃ ( S - △ ) R ∀ ( S - △ ) R ∃ ( S - C A R ) R ∀ ( S - C A R ) R ∃ ( S - T R A ) R ∀ ( S - T R A ) ADV 0.001 0.001 0.807 0.750 0.018 0.014 CE 0.001 0.000 0.768 0.670 0.012 0.008 Dolphin 0.020 0.011 0.857 0.817 0.089 0.069 Email 0.008 0.005 0.881 0.841 0.070 0.057 FW 0.000 0.000 0.240 0.136 0.005 0.000 Hamster 0.014 0.005 0.893 0.817 0.074 0.048 HEP 0.007 0.007 0.881 0.876 0.029 0.028 Karate 0.004 0.000 0.743 0.706 0.034 0.011 PB 0.001 0.000 0.577 0.497 0.010 0.007 USAir 0.000 0.000 0.510 0.509 0.005 0.005 Word 0.067 0.028 0.799 0.735 0.108 0.062 Yeast 0.083 0.063 0.945 0.931 0.357 0.324


### 2.4. Wilcoxon Signed-Ranks Test

The Wilcoxon signed-ranks test is a nonparametric statistical hypothesis test used to check whether two methods perform equally well over multiple networks [38, 39]. Let di be the difference in performance scores of two link prediction methods on the ith network. The differences are ranked in accordance with their absolute values; in case of ties, average ranks are assigned. Let R+ be the sum of ranks for the networks on which the second method outperformed the first, and R- the sum of ranks for the opposite. For a larger number of networks, the statistics(16)z=T-1/4NN+11/24NN+12N+1is distributed approximately normally [39]. In (16), T=min(R+,R-) and N is the number of networks.Withα=0.05, if z is small than -1.96, we reject the null-hypothesis, which states that both methods perform equally well.


## 2.1. Problem Description and Metric

Given an undirected and unweighted networkG(V,E), in which V and E are the node set and link set, respectively, in this study, multilinks and self-loops are not allowed. Let N=|V| be the number of nodes in the network, and let U be the universal possible link set, which contains N(N-1)/2 possible links. Then, the set of nonobserved links or nonexisting links is U-E. Suppose there are some missing links in U-E, the task of link prediction is to find those links. A similarity-based approach assigns a similarity score to each node pair in U-E and assumes that the higher score a node pair has, the more likely there is a link between them.To test the performance of a similarity index, we randomly divide the link setE into two parts: training set Etr and testing set Ets, such that E=Etr∪Ets and Etr∩Ets=∅. Etr is supposed to be the observed information, and Ets is used for testing. Two parameter-free metrics are employed to quantify the accuracy of link prediction algorithms: AUC [6] and ranking score [21, 22]. In this situation, the AUC score can be interpreted as the probability that a randomly selected missing link (i.e., a link in Ets) is given a higher score than a randomly selected nonexistent link (i.e., a link in U-E). When implementing, if we perform n independent comparisons, there are n1 times that the missing link has higher score and n2 times that they have the same score. The AUC value is then computed as(1)AUC=n1+0.5n2n.Ranking score (RS) takes the ranks of links in testing set after sorting in descend order according to their similarity scores into consideration. LetH=U-Etr be the set of nonobserved links. Let ei be a missing link in Ets and ri be its rank. The ranking score of ei is defined as RS(ei)=ri/|H|, and the ranking score of the link prediction result is as follows:(2)RS=1Ets∑ei∈EtsRSei=1Ets∑ei∈EtsriH.Note that the AUC value is the higher the better, whereas the ranking score is the smaller the better.


## 2.2. Local Similarity Indexes

As yet, many similarity indexes have been proposed for link prediction [6, 8, 9]. Here, we list some local similarity indexes that will be used in our experiments for the purpose of comparison.( 1 ) Common Neighbor (CN) index [11] defines the similarity between x and y as the number of their common neighbors, which is(3)CNx,y=Γx∩Γy,where Γ(x) denotes the set of neighbors of node x.( 2 ) Adamic-Adar (AA) index [12] is a variant of CN index, which believes that small-degree neighbors have more contributions than large-degree neighbors when computing similarity. Its definition is as follows:(4)AAx,y=∑z∈Γx∩Γy1log⁡kz,where kz is the degree of node z.( 3 ) Resource Allocation (RA) index [13] defines the similarity between x and y as the amount of resource that y received from x through their common neighbors, which is(5)RAx,y=∑z∈Γx∩Γy1kz.( 4 ) Adaptive Degree Penalization (ADP) index [23] penalizes a common neighbor according to its degree and the average clustering coefficient of the network. Therefore, it can automatically adapt to the network. The definition of ADP index is as follows:(6)ADPx,y=∑z∈Γx∩Γykz-βC,where β is a constant and C is the average clustering coefficient of the network. We set β=2.5, as suggested by the authors.( 5 ) CAR index [20] suggests that two seed nodes are more likely to link together if there are links between their common neighbors, which is defined as(7)CARx,y=CNx,y·∑z∈Γx∩ΓyLz2,where L(z) is the number of links between z and other common neighbors of x and y.( 6 ) CAA and CRA indexes [20] are generated by plugging the idea of CAR index into the AA and RA indexes, respectively, which are defined as(8)CAAx,y=∑z∈Γx∩ΓyLzlog⁡kz,(9)CRAx,y=∑z∈Γx∩ΓyLzkz.( 7 ) CCLP index [24] computes the similarity between x and y by employing clustering coefficient of common neighbors, which is(10)CCLPx,y=∑z∈Γx∩ΓyCCz,where CCz denotes the clustering coefficient of node z, which is(11)CCz=2tzkzkz-1,in which tz is the number of triangles passing through node z.


## 2.3. Networks

In this study, we use 12 real-world networks drawn from various fields to evaluate the effectiveness of link prediction methods.(1)
Advogato (ADV): a social network whose users are mainly free and open source software developers [25].(2)
C.elegans (CE): the neural network of a Caenorhabditis elegans worm [26].(3)
Dolphin: a social network of 62 dolphins in a community living off Doubtful Sound, New Zealand [27].(4)
Email: a network of email interchanges between members of a university [28].(5)
Foodweb (FW): a food web in Florida Bay during the rainy season [29].(6)
Hamster: a friendship network between users on hamsterster.com [30].(7)
HEP: the coauthorships network of scientists who posted preprints on the high-energy theory archive from 1995 to 1999 [31].(8)
Karate: the social network of a karate club at a US university [32].(9)
Political blogs (PB): a network of blogs about US politics [33].(10)
USAir: a network of the US air transportation system [6].(11)
Word: an adjacency network of common adjectives and noun in the novel “David Copperfield” by Charles Dickens [34].(12)
Yeast: the protein-protein interaction network of budding yeast [35].In this work, all the aforementioned networks are treated as undirected and unweighted networks, and only the giant component of each network is used. Table1 lists the basic statistics of the giant components of these networks.Table 1
The basic structural features of the giant components of the 12 networks.|V| and |E| are the total numbers of nodes and edges, respectively. D denotes the density, which is D=2|E|/|V|(|V|-1). 〈k〉 and 〈d〉 present the average degree and the average shortest distance, respectively. C and r indicate the clustering coefficient [26] and assortative coefficient [36], respectively. H is the degree heterogeneity [6], defined as H=k2/k2, and e is the network efficiency [37].
Networks | V | | E | D 〈 k 〉 〈 d 〉 C r H e ADV 5042 39227 3.1E-03 15.560 3.275 0.253 -0.096 5.303 0.324 CE 297 2148 4.9E-02 14.465 2.455 0.292 -0.163 1.801 0.445 Dolphin 62 159 8.4E-02 5.129 3.357 0.259 -0.044 1.327 0.379 Email 1133 5451 8.5E-03 9.622 3.606 0.220 0.078 1.942 0.300 FW 128 2075 2.6E-01 32.422 1.776 0.335 -0.112 1.237 0.622 Hamster 1788 12476 7.8E-03 13.955 3.453 0.143 -0.089 3.264 0.317 HEP 5835 13815 8.1E-04 4.735 7.026 0.506 0.185 1.926 0.155 Karate 34 78 1.4E-01 4.588 2.408 0.571 -0.476 1.693 0.492 PB 1222 16714 2.2E-02 27.355 2.738 0.320 -0.221 2.971 0.398 USAir 332 2126 3.9E-02 12.807 2.738 0.625 -0.208 3.464 0.406 Word 112 425 6.8E-02 7.589 2.536 0.173 -0.129 1.815 0.442 Yeast 2224 6609 2.7E-03 5.943 4.376 0.138 -0.105 2.803 0.246Given networkG(V,E), suppose x, y be two seed nodes. (x,y) is calleda seed node pair with common neighbors if they have at least one common neighbor. PΛ denotes the set of seed node pairs with common neighbors, formally(12)PΛ=x,y∣x,y∉E∧Γx∩Γy≠∅.Let x, y be two seed nodes, and z is one of their common neighbors. If CCz=0, we call z is azero-triangle-neighbor; otherwise, z is atriangle-neighbor. If L(z)≠0, z is called aCAR-triangle-neighbor and if △(x,y;z)≠0 (see (18)), z is called aTRA-triangle-neighbor. Let S△ be the set of triangle-neighbors, and SCAR, STRA denote the sets of CAR- and TRA-triangle-neighbors, respectively. Clearly, SCAR⊆STRA⊆S△. Let P∃(S¯△) and P∀(S¯△) be two subsets of PΛ. For any pair in P∃(S¯△), at least one of their shared neighbors is not a triangle-neighbor, and for any pair in P∀(S¯△), all of their shared neighbors are not triangle-neighbors. More explicitly,(13)P∃S¯△=x,y∈PΛ∣∃z∈Γx∩Γy∧z∉S△,P∀S¯△=x,y∈PΛ∣∀z∈Γx∩Γy∧z∉S△.Similarly, we define P∃(S¯TRA), P∀(S¯TRA), P∃(S¯CAR), and P∀(S¯CAR), which are(14)P∃S¯TRA=x,y∈PΛ∣∃z∈Γx∩Γy∧z∉STRA,P∀S¯TRA=x,y∈PΛ∣∀z∈Γx∩Γy∧z∉STRA,P∃S¯CAR=x,y∈PΛ∣∃z∈Γx∩Γy∧z∉SCAR,P∀S¯CAR=x,y∈PΛ∣∀z∈Γx∩Γy∧z∉SCAR.Correspondingly, the ratios of those subsets to PΛ are, respectively, defined as(15)R∃S¯△=P∃S¯△PΛ,R∀S¯△=P∀S¯△PΛ,R∃S¯TRA=P∃S¯TRAPΛ,R∀S¯TRA=P∀S¯TRAPΛ,R∃S¯CAR=P∃S¯CARPΛ,R∀S¯CAR=P∀S¯CARPΛ.Table 2 lists these ratios over the 12 networks.Table 2
The ratios of various seed pairs over the 12 networks.
Networks R ∃ ( S - △ ) R ∀ ( S - △ ) R ∃ ( S - C A R ) R ∀ ( S - C A R ) R ∃ ( S - T R A ) R ∀ ( S - T R A ) ADV 0.001 0.001 0.807 0.750 0.018 0.014 CE 0.001 0.000 0.768 0.670 0.012 0.008 Dolphin 0.020 0.011 0.857 0.817 0.089 0.069 Email 0.008 0.005 0.881 0.841 0.070 0.057 FW 0.000 0.000 0.240 0.136 0.005 0.000 Hamster 0.014 0.005 0.893 0.817 0.074 0.048 HEP 0.007 0.007 0.881 0.876 0.029 0.028 Karate 0.004 0.000 0.743 0.706 0.034 0.011 PB 0.001 0.000 0.577 0.497 0.010 0.007 USAir 0.000 0.000 0.510 0.509 0.005 0.005 Word 0.067 0.028 0.799 0.735 0.108 0.062 Yeast 0.083 0.063 0.945 0.931 0.357 0.324


## 2.4. Wilcoxon Signed-Ranks Test

The Wilcoxon signed-ranks test is a nonparametric statistical hypothesis test used to check whether two methods perform equally well over multiple networks [38, 39]. Let di be the difference in performance scores of two link prediction methods on the ith network. The differences are ranked in accordance with their absolute values; in case of ties, average ranks are assigned. Let R+ be the sum of ranks for the networks on which the second method outperformed the first, and R- the sum of ranks for the opposite. For a larger number of networks, the statistics(16)z=T-1/4NN+11/24NN+12N+1is distributed approximately normally [39]. In (16), T=min(R+,R-) and N is the number of networks.Withα=0.05, if z is small than -1.96, we reject the null-hypothesis, which states that both methods perform equally well.


## 3. The Proposed Index

The link prediction problem has a familiar relationship with the network evolving mechanism [2, 40]. A recently proposed triangle growth mechanism demonstrates that various key features observed in most real-world networks can be generated in simulated networks [41]. Therefore, triangle structure information has an important effect in link formation.In this work, we focus on a new triangle structure, namelyTRA-triangle. A TRA-triangle passes through one seed node, one common neighbor, and one other node. In our opinion, the common neighbors that can form TRA-triangles are more important than others. Given two nodes u and v, we denote the number of triangles passing through them as △(u,v), which is(17)△u,v=CNu,v,ifu,v∈E0,otherwiseFor the example network in Figure1(a), the triangles used for seed nodes a, b are shown in Figure 1(d). Clearly, △(a,c)=2 and △(a,d)=1. Thus, node c is in more close contact with a than d. Given seed nodes x and y, z is one of their common neighbors. Function △(x,y;z) sums up the number of TRA-triangles formed by x, z, and y, z, which is(18)△x,y;z=△x,z+△y,z.In this paper, we propose a new similarity index, by combining the aforementioned triangle structure and the idea of RA index [13]. For the convenience of statement, we name our new methodTRA index. Its definition is(19)TRAx,y=∑z∈Γx∩Γy1+△x,y;z/2kz.In (19), the numerator is 1+△(x,y;z)/2. Therefore, the TRA index does not miss the effect of any common neighbor. If all common neighbors are zero-triangle-neighbors, TRA degenerates to RA. For the example network in Figure 1(a), TRA(a,b)=1+3/2/4+1+2/2/3+1+0/2/2+1+0/2/4=49/24.


## 4. Experimental Results

Table3 lists the predicted results of different methods in terms of AUC on the 12 networks. The results are obtained by averaging over 50 independent realizations for each network with testing set containing 10% links. The highest AUC value for each network is highlighted in boldface. Clearly, TRA index gets nine best results over the 12 networks. Meanwhile, TRA index outperforms the CAR, CAA, CRA, and CCLP indexes on all networks. We can see from Table 2 that, on most of the networks, there exist varying degrees of such seed node pairs with common neighbors that belong to P∃(S¯△) and/or P∀(S¯△). As stated in Introduction, CCLP index will give lower or zero similarity scores to those pairs. Furthermore, both values of R∃(S¯CAR) and R∀(S¯CAR) are very high on most of the networks. Particularly, on Dolphin, Email, Hamster, HEP, and Yeast, the corresponding values of R∀(S¯CAR) are greater than 0.8. This phenomenon indicates that only a very small fraction of seed node pairs with common neighbors on those networks can be assigned similarity scores by CAR-based indexes. Although there are some seed node pairs belonging to P∃(S¯TRA) and/or P∀(S¯TRA), TRA index still can assign reasonable similarity scores to them. Therefore, the results of TRA index in Table 3 are better than them of CAR, CAA, CRA, and CCLP indexes. For CN, AA, RA, and ADP indexes, ADP index performs the best, since it can penalize common neighbors by automatically adapting to the network. On Dolphin, HEP, and USAir, ADP index obtains the best accuracy; the performance of our index approximates to the best. In addition, TRA index achieves much better AUC scores than others on FW and Karate. This result suggests that TRA-triangles play an important role on these two networks. From Table 1, both networks are dense ones. Roughly speaking, the probability that there exist TRA-triangle-neighbors between seed nodes on dense networks is more than on sparse ones.Table 3
The AUC of different methods in 12 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.
CN AA RA ADP CAR CAA CRA CCLP TRA ADV 0.8992 0.9026 0.9030 0.9033 0.8054 0.8051 0.8063 0.9011 0.9043 CE 0.8450 0.8613 0.8662 0.8654 0.7657 0.7677 0.7704 0.8625 0.8713 Dolphin 0.7832 0.7863 0.7854 0.7866 0.6475 0.6473 0.6473 0.7804 0.7850 Email 0.8471 0.8491 0.8488 0.8491 0.6994 0.6995 0.6996 0.8452 0.8493 FW 0.6053 0.6071 0.6114 0.6097 0.6192 0.6271 0.6321 0.6323 0.6890 Hamster 0.8037 0.8067 0.8074 0.8067 0.6542 0.6542 0.6543 0.8075 0.8127 HEP 0.8984 0.8987 0.8987 0.8987 0.7079 0.7079 0.7079 0.8624 0.8985 Karate 0.6985 0.7409 0.7523 0.7532 0.5848 0.5881 0.5880 0.7085 0.7755 PB 0.9192 0.9226 0.9239 0.9242 0.8926 0.8929 0.8946 0.9217 0.9282 USAir 0.9357 0.9466 0.9522 0.9523 0.9136 0.9158 0.9202 0.9391 0.9452 Word 0.6656 0.6649 0.6621 0.6651 0.5717 0.5713 0.5714 0.6727 0.6809 Yeast 0.7041 0.7047 0.7045 0.7047 0.5994 0.5994 0.5994 0.6972 0.7054To check whether the proposed index is significantly different with compared methods, we applied Wilcoxon signed-ranks test [39] based on the results in Table 3. The pairwise test results are presented in Figure 2. From the statistical point of view, our index is significantly better than others except ADP index, because ADP index has the capability of adapting to the structure of a network automatically. Although there is no statistical difference between our index and ADP index according to Wilcoxon signed-ranks test, our index performs better than ADP index in terms of AUC.Figure 2
The results of Wilcoxon signed-ranks test based on Table3. With α=0.05, if z<=-1.96, the null-hypothesis is rejected.Figure3 exhibits the changes of AUC on 12 networks when the proportion of Ets in E increases from 10% to 20%. It is quite evident from Figure 3 that the AUC values of all indexes show downward trends when the proportion increases from 10% to 20% except on FW. The reason is that the increase of Ets will decrease the size of training set Etr and then will result in the number of common neighbors between seed nodes becoming small. Consequently, the difficulty of link prediction will enhance. The FW network, which possesses high average degree, small average shortest distance, and small-degree heterogeneity, is a very dense network. Therefore, the decrease of training set gives slight influence of accuracy on FW. In addition, we can observe from Figure 3 that the performance presented by all indexes on ADV, CE, Dolphin, Email, Hamster, HEP, Karate, Word, and Yeast is very similar. On these nine networks, the AUC values of CAR-based indexes are obvious lower than those of others. On the network of FW, the results of CAR-based indexes are better than those of CN, AA, RA, and ADP indexes, because FW is a very dense network in which the ratio of CAR-triangle-neighbor is very high (see Table 2). On PB and USAir, the performance of CAR-based indexes is not as bad as on other nine networks. The reason is both networks have high average degrees, small average shortest distances, and high ratio of CAR-triangle-neighbors.Figure 3
The changes of AUC whenEts/E increases from 10% to 20% on 12 networks. Each point is obtained by averaging over 50 independent realizations.Furthermore, we list the AUC values of different methods on the 12 networks whenEts/E=0.2 in Table 4. The results of our index outperform others on eight among the 12 networks, while CCLP index achieves the highest value on CE.Table 4
The AUC of different methods in 12 networks. The results are the average of 50 independent implementations with|Ets|/|E|=0.2. The best performance for each network is emphasized by boldface.
CN AA RA ADP CAR CAA CRA CCLP TRA ADV 0.8830 0.8862 0.8864 0.8867 0.7672 0.7674 0.7676 0.8845 0.8877 CE 0.8210 0.8381 0.8418 0.8407 0.7079 0.7086 0.7104 0.8469 0.8384 Dolphin 0.7468 0.7494 0.7488 0.7497 0.5891 0.5930 0.5890 0.7322 0.7496 Email 0.8221 0.8239 0.8236 0.8239 0.6564 0.6571 0.6565 0.8186 0.8244 FW 0.6075 0.6099 0.6129 0.6117 0.6174 0.6173 0.6280 0.6354 0.6872 Hamster 0.7859 0.7885 0.7890 0.7883 0.6246 0.6246 0.6246 0.7885 0.7937 HEP 0.8587 0.8590 0.8590 0.8590 0.6460 0.6464 0.6460 0.8190 0.8589 Karate 0.6587 0.6900 0.6946 0.6932 0.5647 0.5597 0.5664 0.6582 0.7082 PB 0.9128 0.9160 0.9166 0.9172 0.8736 0.8719 0.8753 0.9152 0.9218 USAir 0.9280 0.9382 0.9428 0.9428 0.8956 0.8960 0.9000 0.9313 0.9378 Word 0.6546 0.6541 0.6522 0.6545 0.5464 0.5461 0.5462 0.6622 0.6672 Yeast 0.6870 0.6874 0.6873 0.6875 0.5793 0.5800 0.5793 0.6785 0.6879Table5 gives the results in terms of ranking score. These results are similar to those in Table 3. The ranking score of TRA index outperforms others except on Dolphin, HEP, and USAir. The pairwise Wilcoxon signed-ranks test results are shown in Figure 4. Similar to the test in Figure 2, TRA index is significantly better than compared methods except ADP index. As depicted above, ADP has the adaptive capability and hence performs better than other compared methods.Table 5
The ranking score of different methods in 12 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.
CN AA RA ADP CAR CAA CRA CCLP TRA ADV 0.1700 0.1663 0.1660 0.1657 0.1727 0.3780 0.3776 0.1690 0.1647 CE 0.1807 0.1613 0.1568 0.1574 0.2015 0.3930 0.3904 0.1603 0.1518 Dolphin 0.3271 0.3223 0.3232 0.3220 0.3338 0.6788 0.6788 0.3311 0.3234 Email 0.2745 0.2727 0.2731 0.2726 0.2771 0.5941 0.5942 0.2793 0.2724 FW 0.3986 0.3965 0.3925 0.3939 0.3844 0.3873 0.3821 0.3722 0.3179 Hamster 0.3323 0.3295 0.3287 0.3295 0.3357 0.6769 0.6768 0.3297 0.3234 HEP 0.2008 0.2005 0.2005 0.2005 0.2009 0.5839 0.5839 0.2729 0.2007 Karate 0.3393 0.3034 0.2922 0.2913 0.3391 0.7424 0.7424 0.3450 0.2708 PB 0.0988 0.0957 0.0944 0.0942 0.1013 0.1675 0.1657 0.0967 0.0899 USAir 0.0795 0.0688 0.0632 0.0632 0.0820 0.1332 0.1290 0.0782 0.0700 Word 0.4396 0.4362 0.4387 0.4360 0.4631 0.7862 0.7860 0.4317 0.4201 Yeast 0.5739 0.5734 0.5735 0.5734 0.5743 0.7989 0.7989 0.5895 0.5727Figure 4
The results of Wilcoxon signed-ranks test based on Table5. With α=0.05, if z<=-1.96, the null-hypothesis is rejected.Figure5 describes the changes of ranking score on 12 networks when |Ets|/|E| increases from 10% to 20%. Clearly, all indexes yield higher ranking scores with the increase of Ets. Do not forget that higher ranking score means lower accuracy. As analyzed above, FW is very dense. Thus, the changes of AUC on FW are very slight (see Figure 3). However, the changes of ranking score on FW are more evident, especially for CAA and CRA indexes. The reason is that the calculation of ranking score considers all missing links. In addition, as seen in Figure 5, CAA and CRA indexes perform worse than CAR index according to ranking score. From the definitions of these three indexes, we find that both CAA and CRA indexes can get more negative impact than CAR index from zero-triangle-neighbors.Figure 5
The changes of ranking score when|Ets|/|E| increases from 10% to 20% on 12 networks. Each point is obtained by averaging over 50 independent realizations.Finally, the ranking scores of all methods on the 12 networks with|Ets|/|E|=0.2 are listed in Table 6. Our index outperforms all other indexes except on HEP and USAir in terms of ranking score. These results are consistent with them of AUC. In contrast with that on FW, the influence of TRA-triangles on HEP and USAir is small.Table 6
The ranking score of different methods in 12 networks. The results are the average of 50 independent implementations with|Ets|/|E|=0.2. The best performance for each network is emphasized by boldface.
CN AA RA ADP CAR CAA CRA CCLP TRA ADV 0.2027 0.1993 0.1991 0.1989 0.2058 0.4561 0.4558 0.2024 0.1978 CE 0.2234 0.2033 0.1998 0.2006 0.2473 0.5268 0.5224 0.2029 0.1945 Dolphin 0.4040 0.3998 0.4004 0.3995 0.4108 0.7976 0.8029 0.4315 0.3993 Email 0.3274 0.3257 0.3261 0.3257 0.3298 0.6821 0.6829 0.3352 0.3253 FW 0.4008 0.3989 0.3956 0.3971 0.3900 0.4128 0.4032 0.3749 0.3259 Hamster 0.3721 0.3696 0.3690 0.3697 0.3756 0.7388 0.7387 0.3710 0.3644 HEP 0.2810 0.2808 0.2808 0.2808 0.2811 0.7070 0.7079 0.3609 0.2809 Karate 0.4347 0.4061 0.4017 0.4030 0.4376 0.8301 0.8181 0.4478 0.3893 PB 0.1124 0.1093 0.1085 0.1082 0.1159 0.2109 0.2080 0.1101 0.1034 USAir 0.0960 0.0859 0.0812 0.0812 0.0989 0.1781 0.1734 0.0952 0.0864 Word 0.4796 0.4757 0.4775 0.4753 0.5013 0.8580 0.8580 0.4728 0.4621 Yeast 0.6114 0.6110 0.6111 0.6110 0.6118 0.8392 0.8402 0.6298 0.6104From the above results, we can conclude that TRA index is superior to CAR-based indexes and CCLP index and performs better than common-neighbor-based methods on most of networks.


## 5. Conclusion and Discussion

Link prediction is an important research topic of complex network analysis and has a wide range of applications in various fields. Inspired by the triangle growth mechanism in network evolving [41], this paper proposed the TRA index for link prediction. When computing the similarity between two seed nodes, the proposed index not only counts the contributions of all common neighbors but also emphasizes the importance of the neighbors that can form TRA-triangles. To some extent, TRA-triangles reflect the close relationships between neighbors and seed nodes. In addition, the proposed index also adopts the theory of resource allocation [13] due to its effectiveness.The accuracy of the TRA index is experimentally evaluated over 12 real-world networks from various fields in terms of AUC and ranking score. The experimental results show that the proposed index performs far better than CAR-based indexes. Meanwhile, our index outperforms the CCLP index because of the superior strategy in our index. For common-neighbor-based methods, the proposed index yields some improvements of accuracy on most of networks. These results indicate that combining the information of TRA-triangles and the theory of resource allocation in similarity index is a helpful idea for link prediction.There are some improved studies for our index in future. One of them is to analyze the degree of influence of TRA-triangles on different networks and further to be adaptive to set the weight of TRA-triangles on different networks. The second is to study the application of TRA index on other topics, such as community detection and anomaly detection. In addition, for learning-based link prediction approaches, TRA index can be used as a feature for a node pair.



---

*Source: 7312603-2018-12-02.xml*