# Link Prediction in Complex Network via Penalizing Noncontribution Relations of Endpoints

Authors: Xuzhen Zhu; Yang Tian; Hui Tian
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Similarity based link prediction algorithms become the focus in complex network research. Although endpoint degree as source of influence diffusion plays an important role in link prediction, some noncontribution links, also called noncontribution relations, involved in the endpoint degree serve nothing to the similarity between the two nonadjacent endpoints. In this paper, we propose a novel link prediction algorithm to penalize those endpoints’ degrees including many null links in influence diffusion, namely, noncontribution relations penalization algorithm, briefly called NRP. Seven mainstream baselines are introduced for comparison on nine benchmark datasets, and numerical analysis shows great improvement of accuracy performance, measured by the Area Under roc Curve (AUC). At last, we simply discuss the complexity of our algorithm.


---

## Body

## 1. Introduction

Many systems can be properly described as complex networks with nodes representing individuals or organizations and links mimicking the relations among them [1–3]. Link prediction as a critical problem of forecasting potential relations between nonadjacent nodes meaningfully provides strong ability to explore the evolution of network and unveils the development mechanism of network, attracting so many researchers’ interests [4]. In real-world applications, link prediction gives help to significantly discover potential network links [5], bring in many striking applications of recommending friends in online social networks [6], explore protein-to-protein interactions [7], reconstruct airline networks [8], and boost e-commerce scales [9, 10].Most conventional methods model the task of link prediction in the form of estimating the probability that two nonadjacent nodes would be linked, which is believed to be positively correlated with the similarity between them [11]. Mainstream methods take into account topological similarity based on network structures and can be classified into three major classes [11]. The first class calculates topological similarity with global structural information, such as theKatz Index that counts all paths connecting two nodes with shorter paths preferred [12]. Such global indices show fair performance in prediction but suffer from high computational complexity [11]. The second class, defined on local structures, typically includesCommon Neighbors(CN) Index [13] counting the number of common nodes,Preferential Attachment(PA) Index [14] preferring the links between endpoints of high degrees, and the methods penalizing high-degree common neighbors, such asAdamic-Adar(AA) Index [15],Resource Allocation(RA) Index [16],Optimized AA(OAA) Index,Optimized RA(ORA) Index [17], andCentrality based Index (DC-CN, BD-CN, and CC-CN) [18]. In spite of successfully reducing the computational expense, local indices suffer from relatively poor prediction performance [11]. In order to find a nice tradeoff between performance and complexity, the third class of similarity indices is proposed on quasilocal structures. TheLocal Path(LP) Index ignores long-path terms inKatz Index [19], and its bounded version (BLP) relates local paths in an elaborate way [20]. TheSignificant Path(SP) Index comprehensively considers paths and intermediate node degree [21]. TheLocal Random Walk(LRW) Index limits a random walk within a local range [22], while theSuperposed Random Walk(SRW) Index continuously releases a random walker at the starting node to emphasize the nodes near the target node [22].Influence of a node plays a very important role in link prediction, so that a node with powerful influence can attract and impact on other nodes in a network, such as a very important person (VIP) in a social network, possessing strong power to transmit his/her reputation to attract others to follow. In a network, a node with high degree is believed to have more powerful influence and more likely to arise links in the future. However, when carefully examining the node degree influence in link prediction, we find that not all the influence is significant to the counterpart endpoint. In other words, there are noncontribution relations in node degree influence. For example, in Figure1, we define the influence degree as the number of endpoint relations, valid influence degree as the number of endpoint relations which can eventually reach the counterpart endpoint, and connectivity chance as the proportion the valid influence occupies in the total amount of an endpoint, featuring the total valid amount of influence emanating from the endpoint. Despite an apparently high influence degree of 3 in subgraph (b), v
4 and v
6 in fact possess valid influence degree only of 1 and connectivity chance only accounting for 1
/
3 because of two noncontribution relations, and, in contrast, v
1 and v
3 although just with lower influence degree of 1 cast all influence degree to each other and have greater connectivity chance of 1. Furthermore, in subgraph (c),  v
7 and v
11 obtain the highest valid influence degree of 3 and also greater connectivity chance of 1 without any useless relations as v
1 and v
3 in subgraph (a). Therefore, we reasonably deduce the link likelihood order (c) > (a) > (b), according to the valid influence degree and connectivity chance. From the theoretical analysis and real illustration, we extract a finding that obviously the high chance of connectivity can enhance link likelihood and on the contrary the noncontribution relations would harm it.Illustration of noncontribution relations and valid influence diffusion. With the same valid influence degree of 1 and smaller connectivity chance of1
/
3 than 1 in subgraph (a), link likelihood in (b) is less than (a) because of two noncontribution relations attached on v
4 and v
6; meanwhile, subgraph (c) with the highest valid influence degree of 3 and the same connectivity chance in (a) obtains the greatest link likelihood. Totally, we rank (c) > (a) > (b) according to reasonable link likelihood.
(a)
(b)
(c)In this paper, we propose a novel similarity index considering penalization on noncontribution relations with a tunable penalization factorβ and random walk based valid influence diffusion, namely, noncontribution relations penalization (NRP) index. In contrast with recently published SP Index [21] and also a link prediction algorithm, there are obvious differences: NRP focuses on the penalization on noncontribution relations in endpoints and meanwhile adds bidirectional valid influence diffusions together to form the model, but SP just considers single direction paths and focuses on the heterogeneity of different paths concerning the intermediate nodes without considering the endpoints. Besides novelty, compared with seven mainstream baselines via experiments on nine benchmark datasets, numerical analysis shows a great improvement on NRP.The rest of the paper is organized as follows: in Section2, the new model based on penalization on noncontribution relations and significant connectivity is introduced; in Sections 3 and 4, the experimental materials of nine benchmark datasets and methods including metrics and seven mainstream baselines are described, respectively; we present the results and discussions in Section 5 and finally make a conclusion.


## 2. Method

An undirected networkG
(
V
,
E
) is considered, where V and E stand for the sets of nodes and links, respectively. Multiple links and self-connections are not allowed. For each pair of nodes, x, y
∈
V, every algorithm referred to in this paper assigns a score s
x
y. This score can be viewed as a measure of similarity between nodes x and y, and hereinafter we do not distinguish similarity and score. All the nonexistent links are sorted in decreasing order according to their scores, and the links at the top are most likely to exist. To test the algorithm’s accuracy, the set of links E is randomly divided into two parts: the training set E
T is treated as known information, while the testing set E
P is used for testing and no information in this set is allowed to be used for training. Clearly, E
T
⋃
‍
E
P
=
E and E
T
⋂
‍
E
P
=
∅.As described in the introduction and Figure1, the probability of link between two nonadjacent endpoints is based on the similarity established via considering valid influence diffusion which can be regarded as a resource diffusion process [22]. Here, for the sake of emphasizing the common transferring capability in bidirectional resource diffusion, we first extract the intermediate connectivity C ignoring the transfer probability values 1
/
k
x and 1
/
k
y emanating from the endpoints in Definition 1 as follows.Definition 1.
On an undirected unweighted networkG
(
V
,
E
), one defines the intermediate connectivity C of a l-step path q
=
{
v
0
=
x
,
v
1
,
…
,
v
l
-
1
,
v
l
=
y
}; connecting x and y equals the product of transfer probability from v
1 to v
l or from v
l
-
1 to v
0 ignoring the transfer probability from the endpoint, as
(1)
C
x
,
y
l
j
=
∏
i
=
1
l
-
1
‍
P
v
i
+
1
∣
v
i
=
∏
i
=
1
l
-
1
‍
P
v
l
-
1
-
i
∣
v
l
-
i
,
where P
v
i
+
1
∣
v
i
=
1
/
k
(
v
i
) is the transfer probability from v
i to v
i
+
1 with k
(
v
i
) denoting the degree of node v
i.Although the numbers of links are different in networks, the total resources in different networks are the same, simply set as one, necessarily normalizing resource of endpoint ask
x
/
2
E with k
x denoting the influence degree of endpoint x and E denoting the number of links [22]. And, importantly, the more the quantity of the valid resource from one endpoint can be delivered to the counterpart, the more similar the two endpoints are. Furthermore, we add the bidirectional resource diffusion quantities on paths with length from 2 to t together and simplify the ultimate formalism in Definition 2 as our similarity index—noncontribution relations penalization (NRP) index.Definition 2.
On an undirected unweighted networkG
(
V
,
E
), with the initial resource usually assigned according to the importance of nodes, here, one simply sets the initial resource of node x proportional to its normalized degree k
x
/
2
E [22]. The link prediction similarity index sim
(
x
,
y
)
|
l on a path q
=
{
v
0
=
x
,
v
1
,
…
,
v
l
=
y
} equals the sum of product of normalized and penalized node degrees and transfer probability between two ends in both directions from x to y and from y to x, as
(2)
sim
x
,
y
l
=
∑
j
=
1
N
l
‍
k
y
2
E
β
k
x
2
E
β
1
k
x
C
x
,
y
l
j
ddddddd
+
k
y
2
E
β
1
k
y
C
x
,
y
l
j
=
∑
j
=
1
N
l
‍
1
2
E
β
C
x
,
y
l
j
k
x
β
-
1
+
k
y
β
-
1
.
After merging, we obtain the processed equation, where β is penalty factor in [
0
,
+
∞
) and N
(
l
) is the number of paths of length l, C
(
x
,
y
) represents the intermediate connectivity deleting the impact from the endpoint, and [
(
k
x
)
β
-
1
+
(
k
y
)
β
-
1
] emphasizes the depressed influence of endpoints. At last, we obtain the NRP index of summation on path lengths from 2 to t, saying that
(3)
s
x
y
NRP
t
=
∑
l
=
2
t
‍
sim
x
,
y
l
.Since paths longer than three cost expensive computations contribute but little for predicting links, we just consider the paths withl
=
2 and 3 in practice and later experiments [19, 22].


## 3. Experiments Data

Experiments are performed on nine real-world networks (datasets are freely downloaded from the following academic websites:http://vlado.fmf.uni-lj.si/pub/networks/data, http://wiki.gephi.org/index.php?title=Datasets, http://lovro.lpt.fri.uni-lj.si/support.jsp, http://konect.uni-koblenz.de/networks/, and http://www.linkprediction.org/index.php/link/resource/data). We converted arcs into undirected links and removed loops and multilinks to make them simple networks. (i) Network US Air97 (USAir) [23] is the network of the US air transportation system. (ii) Network Yeast PPI (Yeast) [24] is the protein-protein interaction network of yeast. (iii) Network NetScience (NS) [25] is the network of coauthorships between scientists publishing on the topic of networks. (iv) Network Jazz [26] is the network of Jazz musicians. (v) NetworkC.elegans (CE) [27] is the neural network of the nematode wormC. elegans. (vi) Network Slovka [28] is the Facebook friendship network of Slavko Žitnik. (vii) Network Email (Email) [29] is the email communication network of University of Rovira i Virgili (URV) in Tarragona, Spain. (viii) Network Infectious (Infec) [30] is the face-to-face contact network of people during the exhibition “Infectious: Stay Away” in 2009 at the Science Gallery in Dublin. (ix) Network EuroSiS (ES) [31] is the mapping network between Science in Society actors on the Web of 12 European countries. Table 1 reports the basic topological features of these networks.Table 1
The basic topological features of the nine benchmark networks.|
V
| denotes the number of nodes, |
E
| is the number of links, 〈
k
〉 represents the average degree, 〈
d
〉 denotes the average distance, C indicates the clustering coefficient [27], r indicates the assortativity coefficient [33], and H is the degree heterogeneity, defined as H
=
〈
k
2
〉
/
〈
k
〉
2.
Nets
|
V
|
|
E
|
〈
k
〉
〈
d
〉
C
r
H
USAir
332
2128
12.81
2.74
0.749
-
0.208
3.36
Yeast
2370
10904
9.2
5.16
0.378
0.469
3.35
NS
1461
2742
3.75
5.82
0.878
0.461
1.85
Jazz
198
2742
27.7
2.24
0.633
0.02
1.4
CE
453
2025
8.94
2.66
0.655
-
0.225
4.49
Slavko
334
2218
13.28
3.05
0.488
0.247
1.62
Email
1133
5451
9.62
3.61
0.254
0.078
1.94
Infec
410
2765
13.49
3.63
0.467
0.226
1.39
ES
1272
6454
10.15
3.86
0.382
-
0.012
2.46Each dataset is randomly divided into a training setE
T containing 90% links and a testing set E
P containing the remaining 10% links.


## 4. Experiments Metrics

Area under curve (AUC) [32], an accurate metric, can be interpreted as the probability that a randomly chosen missing link (a link in E
P) is given a higher score than a randomly chosen nonexistent link (a link in U
∖
E, where E denotes the universal link set). In the implementation, among n independent comparisons, if there are n
′ times the missing link has a higher score and n
′
′ times they are the same score, AUC can be calculated as follows:
(4)
AUC
=
n
′
+
0.5
n
′
′
n
.AUC estimates the accuracy of the index globally, with the significance that if all the scores generated from independent and identical distribution, the accuracy should be about 0.5. Therefore, the degree to which the accuracy exceeds 0.5 indicates how much better the algorithm performs than pure chance.


### 4.1. Baselines

For comparison, we introduce six classical algorithms as follows.(1)
Common Neighbors (CN) Index [13]: considering if two endpoints are similar, they may have many common neighbors with definition by calculating the number of common neighbors:
(5)
s
x
y
CN
=
Γ
(
x
)
∩
Γ
(
y
)
,
whereΓ
(
x
) is the set of neighbor nodes belonging to endpoint x and Γ
(
x
)
∩
Γ
(
y
) denotes the set of common neighbors of endpoints x and y.
(2)
Preferential Attachment (PA) Index [14]: believing the probability that the new link will connect x and y is proportional to k
x
×
k
y:
(6)
s
x
y
PA
=
k
x
×
k
y
,
wherek
x and k
y denote the degree of node x and y, respectively.
(3)
Adamic-Adar (AA) Index [15]: based on CN, punishing the common neighbors with high degree by considering the logarithm of reciprocal of common neighbors’ degrees:
(7)
s
x
y
AA
=
∑
z
∈
Γ
(
x
)
∩
Γ
(
y
)
‍
1
log
⁡
k
z
.
(4)
Resource Allocation (RA) Index [16]: similar to AA, punishing the common neighbors with high degree just by considering the reciprocal of common neighbors’ degrees:
(8)
s
x
y
RA
=
∑
z
∈
Γ
(
x
)
∩
Γ
(
y
)
‍
1
k
z
.
(5)
Local Path (LP) Index [16, 19]: additionally counting the contribution of local paths with length 3 as follows:
(9)
S
LP
=
A
2
+
ε
A
3
,
whereA is the adjacency matrix and ε is a free parameter.
(6)
Bounded Local Path (BLP) Index [20]: bounding local paths with structural coefficients according to path lengths:
(10)
s
x
y
BLP
=
∑
i
=
2
l
max
⁡
‍
1
i
-
1
·
P
i
v
x
,
v
y
∏
j
=
2
i
‍
N
-
j
,
wherel
max
⁡ indicates the maximum length under consideration and P
i
(
v
x
,
v
y
) is the number of all paths connecting v
x and v
y with length i.
(7)
Superposed Random Walk (SRW) Index [22]: considering superposition of local paths less than t steps and the degrees of two endpoints as follows:
(11)
s
x
y
SRW
t
=
∑
τ
=
1
t
‍
q
x
π
x
y
τ
+
q
y
π
y
x
τ
,
where q
x
=
k
x
/
2
E and π
x
y
(
τ
) denote normalized initial resource and transfer probability from node x to y, respectively.


## 4.1. Baselines

For comparison, we introduce six classical algorithms as follows.(1)
Common Neighbors (CN) Index [13]: considering if two endpoints are similar, they may have many common neighbors with definition by calculating the number of common neighbors:
(5)
s
x
y
CN
=
Γ
(
x
)
∩
Γ
(
y
)
,
whereΓ
(
x
) is the set of neighbor nodes belonging to endpoint x and Γ
(
x
)
∩
Γ
(
y
) denotes the set of common neighbors of endpoints x and y.
(2)
Preferential Attachment (PA) Index [14]: believing the probability that the new link will connect x and y is proportional to k
x
×
k
y:
(6)
s
x
y
PA
=
k
x
×
k
y
,
wherek
x and k
y denote the degree of node x and y, respectively.
(3)
Adamic-Adar (AA) Index [15]: based on CN, punishing the common neighbors with high degree by considering the logarithm of reciprocal of common neighbors’ degrees:
(7)
s
x
y
AA
=
∑
z
∈
Γ
(
x
)
∩
Γ
(
y
)
‍
1
log
⁡
k
z
.
(4)
Resource Allocation (RA) Index [16]: similar to AA, punishing the common neighbors with high degree just by considering the reciprocal of common neighbors’ degrees:
(8)
s
x
y
RA
=
∑
z
∈
Γ
(
x
)
∩
Γ
(
y
)
‍
1
k
z
.
(5)
Local Path (LP) Index [16, 19]: additionally counting the contribution of local paths with length 3 as follows:
(9)
S
LP
=
A
2
+
ε
A
3
,
whereA is the adjacency matrix and ε is a free parameter.
(6)
Bounded Local Path (BLP) Index [20]: bounding local paths with structural coefficients according to path lengths:
(10)
s
x
y
BLP
=
∑
i
=
2
l
max
⁡
‍
1
i
-
1
·
P
i
v
x
,
v
y
∏
j
=
2
i
‍
N
-
j
,
wherel
max
⁡ indicates the maximum length under consideration and P
i
(
v
x
,
v
y
) is the number of all paths connecting v
x and v
y with length i.
(7)
Superposed Random Walk (SRW) Index [22]: considering superposition of local paths less than t steps and the degrees of two endpoints as follows:
(11)
s
x
y
SRW
t
=
∑
τ
=
1
t
‍
q
x
π
x
y
τ
+
q
y
π
y
x
τ
,
where q
x
=
k
x
/
2
E and π
x
y
(
τ
) denote normalized initial resource and transfer probability from node x to y, respectively.


## 5. Results and Discussions

Because of small contribution and expensive cost of computation on long paths, experiments on NRP just consideringt
=
3 in nine networks are implemented (referenced in [19, 22]). After obtaining AUC values experiments, in Section 5.1, we demonstrate important meaning of penalizing noncontribution relations in NRP in Figure 2 of nine subgraphs corresponding to nine different datasets. Furthermore, performance explanations about the nine subgraphs will be offered with different values of penalization factor β when searching for optimal values in [
0
,
5
] which is wide enough to find the optimal values. Then, we compare our algorithms with CN, PA, AA, RA, LP, BLP, and SRW via Table 2. At last, the computational complexity is discussed in Section 5.3.Table 2
Prediction accuracy measured by AUC values on the nine benchmark networks. Each data point is an average over 10 independent runs, each of which corresponds to a random 90%–10% division of training set and testing set. All the present results are optimal values. Numbers in brackets stand for the standard deviations.
AUC
CN
PA
AA
RA
LP
BLP
SRW
NRP
USAir
0.937 (0.008)
0.885 (0.017)
0.948 (0.007)
0.954 (0.007)
0.938 (0.007)
0.931 (0.010)
0.953 (0.011)
0.957 (0.011)
Yeast
0.723 (0.005)
0.494 (0.008)
0.724 (0.005)
0.723 (0.005)
0.732 (0.005)
0.733 (0.004)
0.735 (0.005)
0.736 (0.005)
NS
0.940 (0.011)
0.679 (0.012)
0.940 (0.011)
0.940 (0.011)
0.940 (0.011)
0.943 (0.009)
0.943 (0.009)
0.944 (0.009)
Jazz
0.953 (0.005)
0.762 (0.013)
0.961 (0.004)
0.970 (0.004)
0.954 (0.005)
0.951 (0.005)
0.960 (0.004)
0.970 (0.004)
CE
0.914 (0.011)
0.808 (0.021)
0.948 (0.010)
0.954 (0.010)
0.914 (0.011)
0.911 (0.007)
0.953 (0.009)
0.960 (0.009)
Slavko
0.941 (0.009)
0.775 (0.013)
0.945 (0.009)
0.946 (0.010)
0.944 (0.010)
0.943 (0.010)
0.949 (0.009)
0.952 (0.009)
Email
0.844 (0.007)
0.782 (0.007)
0.846 (0.007)
0.846 (0.007)
0.893 (0.006)
0.902 (0.005)
0.903 (0.007)
0.908 (0.006)
Infec
0.939 (0.009)
0.703 (0.013)
0.942 (0.009)
0.943 (0.009)
0.954 (0.012)
0.958 (0.006)
0.964 (0.006)
0.966 (0.006)
ES
0.910 (0.005)
0.820 (0.007)
0.912 (0.006)
0.912 (0.006)
0.936 (0.007)
0.938 (0.005)
0.945 (0.005)
0.946 (0.005)AUC of NPR, respectively, on nine different datasets withβ in [
0,5
]. The optimal AUC is obtained at β
opt. All AUC values are obtained by averaging over ten independently random divisions.
(a)
USAir
(b)
Yeast
(c)
NS
(d)
CE
(e)
Jazz
(f)
Infec
(g)
Slavko
(h)
Email
(i)
ES


### 5.1. Performances of Penalization on Noncontribution Relations

There are nine subgraphs in Figure2 about AUC of NRP showing functions of penalization on noncontribution relations of endpoint degrees with penalization factor β varying in the range [
0,5
], measured by average AUC under 10 independent runs obeying random divisions of training sets and testing sets. The β-axis represents the penalization degree on endpoint degrees. According to (2) and (3), β
<
1, that is, β
-
1
<
0, suggests endpoints with noncontribution relations will be penalized and the smaller the β is, the more severely the noncontribution relations are suppressed, and vice versa. In Figure 2, the optimal β’s of all nine datasets locate between 0 and 1 when AUC curves reach the peaks, say, USAir at 0.38, Yeast at 0.77, NS at 0.86, CE at 0.11, Jazz at 0.36, Infec at 0.5, Slavko at 0.63, Email at 0.84, and ES at 0.63, which means CE suffers the most penalization and NS suffers the least. And when β
>
1, the AUC performances decrease very severely compared with the optimal AUCs. The β
<
1 consistently happening in nine various kinds of datasets means indeed that the noncontribution relations of endpoint degrees are penalized, and the performance will get worse if they are promoted when β
>
1.


### 5.2. Comparison on AUC

To demonstrate the prediction ability, we report the performances of NRP index with the optimalβ values on nine datasets, respectively. Table 2 reports the average AUC values of NRP and baselines. The results in the table are all optimal and the best values are emphasized in bold font. NRP achieves the best performances in all nine datasets (see boldface in Table 2). Notice that those datasets represent different kinds of networks with heterogeneous topological features (see Table 1) and disparate organization principles; the comparison highlights that NRP works well consistently on various situations.Analyzing the difference in performance between NRP and baselines, we realize that it is the penalization on large-degree nodes with many noncontribution relations and emphasis on connectivity based on random walk that explain the difference. PA simply assumes that only if the higher the degrees the two endpoints have, the more similar the two endpoints are, ignoring the existence of noncontribution relations in degrees of endpoints and the significant connectivity between endpoints, leading to the poorest accuracy performance, especially in Yeast. Instead, CN considers the connectivity via counting the number of common neighbors on 2-hop paths, but ignoring influence of endpoint degrees and connectivity of long paths, resulting in an improved but still worse performance. Further, AA and RA extend CN by similarly penalizing intermediate large-degree nodes and not surprisingly obtain better performance than CN. However, as the same as CN, ignorance of influence of endpoint degrees and long paths cause AA and RA to still work dissatisfiedly such as in Yeast. In contrast, LP and BLP take long paths into account and thus outperform on many networks such as in ES. However, lacking consideration of influence of endpoint degree, LP and BLP meet difficulty in accurately predicting missing links in contrast to NRP, such as in USAir. An exception for BLP is its worse performance especially than CN in USAir, Jazz, and CE because of inelegant formalism of coefficient which cannot hit an optimal value to help it overwhelmingly defeat CN. SRW, with consideration of influence of high endpoint degree and of long paths based on random walk, further improves the performance in contrast to the former algorithms, but neglect of penalization on endpoint degree with noncontribution relations preventing it from better prediction performance. Above all, NRP, outstandingly leveraging the valid influence of endpoint degree with penalization on noncontribution relations and connectivity based on random walk, outperforms all other mainstream algorithms on nine datasets.


### 5.3. Complexity Discussion

In application of algorithm, the low computation complexity is another very important concern in the design of prediction algorithm. As we know, the time complexity of product of twoN
×
N matrices is O
(
N
3
). From the definitions of CN, PA, AA, RA, LP, BLP, and SRW, PA has the time complexity of O
(
N
2
), CN, PA, AA, and RA have the time complexity of O
(
N
3
), and LP, BLP, and SRW are of the complexity M
×
O
(
N
3
) with coefficient M
≪
N
3. In contrast, although with the same time complexity of M
×
O
(
N
3
) of LP, BLP, and SRW, more than CN, PA, AA, and RA, our index shows stronger performance than them all. Above all, our index, NRP, achieves the best performance with little increase in complexity.


## 5.1. Performances of Penalization on Noncontribution Relations

There are nine subgraphs in Figure2 about AUC of NRP showing functions of penalization on noncontribution relations of endpoint degrees with penalization factor β varying in the range [
0,5
], measured by average AUC under 10 independent runs obeying random divisions of training sets and testing sets. The β-axis represents the penalization degree on endpoint degrees. According to (2) and (3), β
<
1, that is, β
-
1
<
0, suggests endpoints with noncontribution relations will be penalized and the smaller the β is, the more severely the noncontribution relations are suppressed, and vice versa. In Figure 2, the optimal β’s of all nine datasets locate between 0 and 1 when AUC curves reach the peaks, say, USAir at 0.38, Yeast at 0.77, NS at 0.86, CE at 0.11, Jazz at 0.36, Infec at 0.5, Slavko at 0.63, Email at 0.84, and ES at 0.63, which means CE suffers the most penalization and NS suffers the least. And when β
>
1, the AUC performances decrease very severely compared with the optimal AUCs. The β
<
1 consistently happening in nine various kinds of datasets means indeed that the noncontribution relations of endpoint degrees are penalized, and the performance will get worse if they are promoted when β
>
1.


## 5.2. Comparison on AUC

To demonstrate the prediction ability, we report the performances of NRP index with the optimalβ values on nine datasets, respectively. Table 2 reports the average AUC values of NRP and baselines. The results in the table are all optimal and the best values are emphasized in bold font. NRP achieves the best performances in all nine datasets (see boldface in Table 2). Notice that those datasets represent different kinds of networks with heterogeneous topological features (see Table 1) and disparate organization principles; the comparison highlights that NRP works well consistently on various situations.Analyzing the difference in performance between NRP and baselines, we realize that it is the penalization on large-degree nodes with many noncontribution relations and emphasis on connectivity based on random walk that explain the difference. PA simply assumes that only if the higher the degrees the two endpoints have, the more similar the two endpoints are, ignoring the existence of noncontribution relations in degrees of endpoints and the significant connectivity between endpoints, leading to the poorest accuracy performance, especially in Yeast. Instead, CN considers the connectivity via counting the number of common neighbors on 2-hop paths, but ignoring influence of endpoint degrees and connectivity of long paths, resulting in an improved but still worse performance. Further, AA and RA extend CN by similarly penalizing intermediate large-degree nodes and not surprisingly obtain better performance than CN. However, as the same as CN, ignorance of influence of endpoint degrees and long paths cause AA and RA to still work dissatisfiedly such as in Yeast. In contrast, LP and BLP take long paths into account and thus outperform on many networks such as in ES. However, lacking consideration of influence of endpoint degree, LP and BLP meet difficulty in accurately predicting missing links in contrast to NRP, such as in USAir. An exception for BLP is its worse performance especially than CN in USAir, Jazz, and CE because of inelegant formalism of coefficient which cannot hit an optimal value to help it overwhelmingly defeat CN. SRW, with consideration of influence of high endpoint degree and of long paths based on random walk, further improves the performance in contrast to the former algorithms, but neglect of penalization on endpoint degree with noncontribution relations preventing it from better prediction performance. Above all, NRP, outstandingly leveraging the valid influence of endpoint degree with penalization on noncontribution relations and connectivity based on random walk, outperforms all other mainstream algorithms on nine datasets.


## 5.3. Complexity Discussion

In application of algorithm, the low computation complexity is another very important concern in the design of prediction algorithm. As we know, the time complexity of product of twoN
×
N matrices is O
(
N
3
). From the definitions of CN, PA, AA, RA, LP, BLP, and SRW, PA has the time complexity of O
(
N
2
), CN, PA, AA, and RA have the time complexity of O
(
N
3
), and LP, BLP, and SRW are of the complexity M
×
O
(
N
3
) with coefficient M
≪
N
3. In contrast, although with the same time complexity of M
×
O
(
N
3
) of LP, BLP, and SRW, more than CN, PA, AA, and RA, our index shows stronger performance than them all. Above all, our index, NRP, achieves the best performance with little increase in complexity.


## 6. Conclusions

In research on topological similarity based link prediction, we find that not all relations involved in the degree of endpoint make contribution to valid influence diffusion due to the existence of noncontribution relations. Accordingly, we expect, in case of penalizing the noncontribution relations in endpoints degree with a penalization factorβ in the valid influence diffusion process, the link prediction performance could be improved. Therefore, in this paper a model named NRP based on noncontribution relations penalization of endpoint degree and random walk based valid influence diffusion is proposed. To detect our model, many experiments are implemented on nine benchmark networks and the results compared with the CN, PA, AA, RA, LP, BLP, and SRW confirm our expectation that penalization on noncontribution relations of endpoint degree could greatly improve the accuracy performance in link prediction.And due to the various structures and properties of experimental datasets, it is obvious that our model can be used in many applications of link prediction, such as transportation planning, biological reactions, friend recommendation in social network, and disease prevention.



---

*Source: 453546-2014-11-16.xml*