# Linkboost: A Link Prediction Algorithm to Solve the Problem of Network Vulnerability in Cases Involving Incomplete Information

Authors: Chengfeng Jia; Jie Ma; Qi Liu; Yu Zhang; Hua Han
Journal: Complexity
 (2020)

---

## Abstract

The vulnerability of network information systems has attracted considerable research attention in various domains including financial networks, transportation networks, and infrastructure systems. To comprehensively investigate the network vulnerability, well-designed attack strategies are necessary. However, it is difficult to formulate a global attack strategy as the complete information of the network is usually unavailable. To overcome this limitation, this paper proposes a novel prediction algorithm named Linkboost, which, by predicting the hidden edges of the network, can complement the seemingly missing but potentially existing connections of the network with limited information. The key aspect of this algorithm is that it can deal with the imbalanced class distribution present in the network data. The proposed approach was tested on several types of networks, and the experimental results indicated that the proposed algorithm can successfully enhance the destruction rate of the network even with incomplete information. Furthermore, when the proportion of the missing information is relatively small, the proposed attack strategy relying on the high degree nodes performs even better than that with complete information. This finding suggests that the nodes important to the network structure and connectivity can be more easily identified by the links added by Linkboost. Therefore, the use of Linkboost can provide useful insight into the operation guidance and design of a more effective attack strategy.


---

## Body

## 1. Introduction

With the development of big data, the management of intensive knowledge in a complex network represents a key technique that can dramatically change the way we perceive the world. Most real-world networks, such as traffic, social, or biological networks, are complex and inevitably undergo network failures [1]. To solve this problem, the critical nodes, the removal of which may lead to network collapse, must be determined. Therefore, the vulnerability or robustness of complex networks, especially in terms of the failure of critical nodes, has attracted considerable attention in the past few years [2].The most fundamental network vulnerability approach mainly relies on removing some crucial nodes and their corresponding edges in the network and calculating the retention of the largest giant component of the network [3]. From the mathematical point of view, it is desirable to find a strategy to remove the important nodes, to ensure that the structure of the network can be destroyed at the lowest cost. To protect such critical nodes, the connectivity of the network should be preserved as much as possible. If complete information regarding the network is available, the network vulnerability can be evaluated in a relatively easy manner, and several methods are available to determine the nodes that critically influence the network vulnerability. Holme et al. [4] proposed a node attacking strategy based on the rank of degree, and a residual network was used to calculate the size of the largest giant component of the network. The results indicated that the high degree nodes can be usually considered as the most important nodes influencing the network vulnerability. Chen et al. [5] used the method of the so-called “equal graph partitioning degree” to identify the key nodes. In particular, they divided a network into two clusters with an arbitrary size ratio and determined the key nodes that connected these clusters. It was observed that the attack on these key nodes could rapidly disintegrate the entire network. Hu et al. [6] used the dynamic Bayesian network to predict the best attack order on the nodes and found that attacking a small number of key nodes could lead to a rapid collapse of the complete network.However, all the abovementioned approaches assumed the network to be panoramic; in other words, it was considered that all the connections in the network are known in advance. In real life, it is difficult to obtain such perfect data. For instance, in a terrorist relationship network, only knowing part of the terrorist information is not sufficient to uncover the organizational structure and the mutual relationship contained in the network [7]. Another example is the biological virus network, in which although the molecular composition can be learned through chemical analysis, the comprehensive connections between the molecules are difficult to determine [8]. Thus, the network connections that we can observe are often partial and incomplete. Although all the information regarding the nodes can be obtained from the network topology, some latent connections exist that cannot be discovered directly, similar to that in the situations shown in Figure 1. For such networks with incomplete information, the vulnerability cannot be directly investigated by using the topology of the network, as performed in traditional methods.Figure 1
Network with different proportions of missing information: (a) more missing information, (b) less missing information, and (c) full information.
(a)
(b)
(c)The research on network vulnerability with incomplete information is generally divided into two categories. The first category involves studies employing statistical methods such as the random walk to find several hidden key nodes [9]. The second category involves studies that use a recently popular technology, namely, the link prediction technology to find the hidden edges from incomplete network connections. In this case, once the network has been complemented, the traditional attack strategies can be employed to study the vulnerability.Despite the considerable research effort pertaining to link prediction, the current state-of-the-art algorithms mostly do not consider the imbalanced distribution of the network data [10]. In general, in a real network, the nodes are paired and the number of paired nodes with edges is considerable smaller than that of the nodes without edges. From the view of supervised learning, the number of connected node pairs is not sufficient to enable learning owing to the lack of sampling, resulting in low prediction accuracy. In the network, because the learning algorithm is biased toward the nonconnected pair samples, it is more difficult to predict the connections between the nodes with small degrees. However, such hard-to-recall edges are critical to perform a network vulnerability analysis, as they may represent the pivot connecting the largest giant component [4], and the nodes with a larger betweenness tend to have a smaller degree value [5]. Therefore, the presence of an uneven data class distribution is a considerable challenge for realizing link prediction, although such imbalanced data is actually crucial to realize a network attack with incomplete information.To solve the problem of the data class imbalance, SMOTE [11] and other data generation algorithms can be used to generate a new data of a minority class to balance the class distribution. However, the use of these methods may change the original distribution of the data, thereby reducing the overall prediction accuracy. In contrast from the approach of changing the original distribution of data, this work focused on the minority class samples obtained by changing the sampling weight of the raw data. The most representative and effective algorithm involving sampling weights is the AdaBoost algorithm [12], which, as a data-driven algorithm, can adaptively change the technique of data sampling on the basis of the classification results in the latest iteration. However, because this algorithm cannot deal with the imbalanced data, it is difficult to achieve a high accuracy in link prediction. To overcome this limitation, this paper proposes a novel link prediction algorithm, Linkboost, which can improve the AdaBoost algorithm by increasing the sampling weight of the minority samples in an adaptive manner.The main contributions of this work can be summarized as follows:(i)
The proposed Linkboost improves the AdaBoost algorithm by adaptively updating the sampling weight, which is advantageous in dealing with the imbalanced class distribution of the network data. The weight updating rule lays more emphasis on the cost of misclassifying the minority class samples than the corresponding cost for the majority class samples. Specifically, this rule increases the sampling weights of the wrongly classified samples in the minority class more aggressively and decreases the weights of the correctly classified samples more conservatively. Furthermore, the convergence of the Linkboost is demonstrated by analyzing the upper bound of the loss function.(ii)
When Linkboost is applied for link prediction, the edges that need to be added are supposed to be closely related to the latent connections. Consequently, we quantify the degree of the network incompleteness and the magnitude of the additional link information. These two key factors can facilitate the development of better attack strategies as the optimum magnitude of the additional information can be specified accordingly in terms of the degrees of network incompleteness.(iii)
In many real-world information networks, owing to privacy or legal restrictions, implicit connections exist in the network, which make it difficult to evaluate the importance of the nodes that are not explicitly connected. Linkboost can determine these implicit edges, thereby providing useful insight for the operation guidance and design of a more effective attack strategy regardless of whether the network is completely observed.


## 2. Literature Review

In most of the early works regarding network vulnerability, it was assumed that the complete information of the network structure can be obtained. With complete information, the nodes that are important to the network vulnerability can be identified by employing various available node importance measures. However, in real life, the complete knowledge of the network structure is not always available. For such cases, some researchers employed partial information to identify the most important nodes to perform network crash analyses. Gallos et al. [13] first studied the stability of scale-free networks by using different attack strategies when the edges were partially hidden in the network; they reported that the optimal node attack strategy has a strong correlation with the degree of the nodes. Wu et al. [14] recognized that the global index (such as the median, shortest distance, and commute time) of the network is unstable when only a few edges are missing, which leads to the deviation of the selection of the key nodes. In this regard, the researchers proposed a hybrid index based on the local information combined with the maximum connected graph and verified the stability of the mixed indicator. Liu and Li [15] applied this concept for the protection of power networks, in which the distribution of the local roads and power capacity information of the power station are available, while a part of the connections remains unknown.All the abovementioned studies identified the important nodes according to the observed topology of the network. However, because these nodes are recognized using incomplete information, the identification of these “important nodes” is not always correct. Therefore, it is of significance to develop an optimum attack strategy for such incomplete networks. Consequently, in this study, we develop a link prediction algorithm to examine the vulnerability of complex networks with incomplete information by restoring the missing information of the network. Subsequently, the widely used high degree strategy [16] is applied to perform the attack.In recent years, link prediction has become a hotspot branch in the field of complex networks. In most of the recent studies, link prediction was performed to estimate the likelihood of the existence of a link between the node pairs in the network. Similarly, in our work, one of the link prediction algorithms is used to recover parts of the missing links before the attack, and the targets are later identified based on the predicted network. Among the existing link prediction algorithms, machine-learning algorithms, which treat link prediction as a binary classification problem, are widely used in large-scale networks [17, 18]. To determine whether the node pairs have connected edges, the node pairs are divided into positive and negative examples, which represent the connected and unconnected pairs, respectively. However, in a real network, the node pairs connected to other pairs are considerably fewer than the node pairs with no connections. For instance, of all Facebook users, considerably fewer pairs of users follow each other than those that do not. The large-scale authorship network is another such example. In most cases, papers and studies are published under the name of a single author, and co-authorship only exists in a few cases (because a balanced network requires each author in the network to engage in co-authorship with half of the authors in the network). In the classification problem, the classification result will be biased if the contribution of the negative sample is ignored, and the optimization goal is simply the minimization of the classification error [19]. More importantly, such an imbalance considerably influences the network vulnerability because the node pairs with high degree nodes are more easily detected, whereas the pairs with low degree nodes tend to be ignored more frequently. These low degree nodes are likely to be crucial nodes [4], the failure of which may lead to the collapse of the largest connected subcomponent [20]. To overcome this limitation, this paper proposes a new link prediction algorithm to solve the imbalance problem.


## 3. Proposed Algorithm

### 3.1. Network Vulnerability and Class Imbalance

A network can be represented as a simple undirected graphG = (V, E), where V is the set of nodes and E is the set of links. Let N = |V| and W = |E| be the numbers of nodes and links, respectively. ki denotes the degree of the node vi, which equals the number of links connected to node. We assume that all the nodes are known, but the partial link information is missing. The network can be observed as GO. It is assumed that the missing link information is predicted using the link prediction algorithm, and the predicted network is GP.We identify the crucial nodes from the predicted networkGP, and then use these nodes to attack the complete network G. Once a node is attacked, its attached edges are removed simultaneously. V^⊆Vdenotes the set of nodes that are attacked (important nodes), and E^⊆E denotes the set of removed links. Thus, the network obtained after the node attacks is G^=V−V^,E−E^. We define the disintegration ratioS=V^/NS∈0,1 as the vulnerability evaluation index of the node attacks. In this study, the high degree strategy [16] is employed, in which the nodes are selected to be attacked according to their degree ranks (i.e., high degree nodes are attacked first).Figure2 shows the difference in the direct attack and attack after link prediction. We assume that three links are hidden, which are marked as red edges in Figure 2(a), and the observed network GO is as shown in Figure 2(b). In this case, Vb is the largest degree node (degree = 3) that can be observed. According to the high degree strategy, Vb is attacked first. When Vb is removed, the residual network is as shown in Figure 2(c). At this point, the disintegration ratio S=V^/N=4/7. In contrast from the direct attack, the proposed method involves adding a possible edge by using the link prediction algorithm on the basis of the incomplete networkGO, which generates the repaired network GP, as shown in Figure 2(d). Next, we use the high degree strategy from GP to attack the network. The largest degree node is Ve, which has a degree of four. After attacking node Ve, the residual network is as shown in Figure 2(e), and the disintegration ratioS=V^/N=3/7. This finding shows that the attack strategy is more effective after the network is repaired using the link prediction algorithm.Figure 2
Comparison between the residual networks for a direct attack and attack after link prediction. (a) Complete networkG. (b) Incomplete network GO with three hidden edges. (c) Residual network after node Vb, which is the highest degree node in the incomplete network GO, is attacked. (d) Predicted network GP with three predicted links added (red dotted lines). (e) Residual network after node Ve, which is the highest degree node in the predicted network GP, is attacked.Figure2 indicates that the use of a suitable link prediction algorithm is the core of the abovementioned network attack strategy. Such algorithms aim at estimating the likelihood of the existence of a link between two nodes based on the observed network structure and the attributes of the nodes. Given that G=V,E, all the nodes are assumed to be known, and the partial link information is considered missing. We define α=EM/W,α∈0,1 as the proportion of the missing links. In general link prediction research, the hidden edges are randomly selected. EO and EM denote the sets of the observed links and missing links, respectively. Clearly, EO∪EM=E. Therefore, the observed network can be represented as GO=V,EO. Let EU=V×V represent the universal set containing all N(N − 1)/2 possible links. The task of link prediction is to reveal the set of missing links EM via link prediction. GP represents the improved network involving the additional predicted links EP. β=EP/EO is defined as the magnitude of the additional link information.In the existing research, many scholars demonstrated that the use of machine-learning algorithms could achieve a high accuracy in link prediction. From the perspective of machine-learning algorithms, the link prediction problem can be regarded as a binary classification problem. Ifu∈V,v∈V, and u,v∈EO, the pair of nodes u,v can be considered a positive example if a link exists between u and v. In contrast, if the pair of nodes is a negative example, no edge is present between u and v. In a real network, the number of connected nodes in the network is considerably smaller than the number of node pairs without an edge, which means E≪EU−E. In the field of machine learning, this condition represents an imbalanced classification problem. Because the goal of most machine algorithms is to minimize the overall sample prediction error, the prediction results may be biased if we ignore the imbalanced distribution of the classes. For a given network, the misclassification of minority class samples means that the hidden edges are not correctly recognized. In particular, when the degree of a node is extremely small, the link prediction algorithm tends to predict that the node has no connection to other nodes. However, in the study of the network vulnerability, some nodes connecting the subnetwork may have only a few connected edges, and these may represent the minority class samples. If this part of the node pairs is not correctly predicted, the wrong attack strategy will be formulated. Therefore, this work focuses on the design of the link prediction algorithm for the class imbalance problem, aiming to restore the network as much as possible to develop the optimal attack strategy.


### 3.2. Linkboost Link Prediction

The link prediction problem, as one of the most significant link analysis and mining tasks, has been used to restore complete networks according to partially observed information. The link prediction algorithm has been applied in the social, biological, and bioinformatics domains to help better analyze and understand the structural topology and evolution mechanism of a network. In this study, we propose a novel link prediction algorithm, Linkboost, which improves the AdaBoost algorithm by increasing the sampling weight of the minority samples in an adaptive manner. The proposed algorithm is expected to solve the problem of imbalanced data distribution in the network and improve the accuracy of link prediction.The link prediction framework of Linkboost is shown in Figure3. First, the static indicators (such as the degree) of the network and similarity indicators (such as the common neighbor) of the node networks are used to extract the feature of the node pairs in the network. Next, the Linkboost algorithm is used to improve the classification accuracy of the minority class by performing resampling with preference. Finally, the network vulnerability is examined using high degree attack strategies by considering the proportion of the missing link α and the magnitude of the additional link β.Figure 3
Overview of the Linkboost framework.In the existing link prediction research, many network structural features have been used to describe the topology characteristics of the network. Based on the past literature [21, 22] and considering the global characteristics of real network nodes, we add two kinds of features based on the distance and random walk:(1)
Node-based features: node degree and high-order degree(2)
Features based on common neighbors: number of common neighbors, Jaccard index, AA index, Katz index, and Salton index(3)
Features based on distance: shortest path and partial region path(4)
Features based on random walks: PageRank [23] and SimRank [22]After completing the feature extraction of the network, these features are fed into the Linkboost algorithm. The pseudocode of the Linkboost algorithm is presented as Algorithm1.Algorithm 1: Process flow of the Linkboost link prediction algorithm.
Input: Network missing adjacency matrix A
Output: Final strong hypothesis Hx=∑t=1Tαthtx, connection score R1, nonconnection score R2.
(1)
Extract features and tag,S=x1,y1,…,xm,ym, xi∈X, yi∈−1,+1. Here xi is the feature of the network node pair, yi is the label of the node pair, indicating whether there is an edge exists. M=EO, N=EU−EO.
(2)
Initialize the weight distribution of the training data.D1=w11,w12,…,w1A, where w1,i=1/2M, if yi=1; w1,i=1/2N, if yi=−1.
(3)
For t in T iterations
(4)
ResampleS according to Dt
(5)
Findht:argminεj=∑i=1my≠hjxi, wherehj∈H.
(6)
If εi<1/2
(7)
Continue
(8)
else
(9)
saveht, calculate αt=1/2∗log1−εt/εt,
(10)
updateDt+1=wt+1,1,wt+1,2,…,wt+1,A and Zt=∑jAwt+1,j
(11)
If yi=1, wt+1,j=1/2M;
(12)
If yi=−1,wt+1,j=wt,i/Ztexp−αmyihtxi,i=1,2,…,A
(13)
End If
(14)
End For
(15)
Predict connection of the network usingHx=∑t=1Tαthtx, obtain R1 and R2As mentioned previously, in the proposed algorithm, the sampling mode is changed so that each iteration of the sampling focuses not only on the misclassified samples but also on the minority class samples. Specifically, in the initialization step, the weight of the positive examples (which also belong to the minority class) is defined asw1i+=1/2M, where M is the number of edges. The weight of the negative examples (which also belong to the majority class) is defined as w1i−=1/2N, where N is the number of nodes pairs without a connection. In most real-world networks, M≪N and w1,i+≫w1,i−; therefore, the positive sample is easier to be sampled. In the process of iteration, the update mode is also affected by the class label. For a positive sample, the weight of the next sample is the same as 1/2M, so as to assign a higher probability of being sampled. For a negative sample, the weights are updated based on whether they are classified correctly. In negative cases, the misclassified node pairs have a higher probability of being sampled in the next iteration. If the negative sampleyi=−1 is classified correctly, htxi=−1. Consequently, −αmyihtxi<0 and wt+1<wt. This means that if the negative samples are classified correctly, the probability of being sampled in the next iteration is decreased. If the prediction is wrong, the probability of being sampled in the next round increases. However, because of the limitation of the normalization factor Zt, the expectation of the sampling weight of the negative samples is smaller than that of the positive samples Ew+>Ew−. This means that the model pays more attention to the recall of the positive samples while focusing on learning the samples that are easily misclassified. This improved sampling method can help recognize more node pairs with connected edges.As the proposed approach modified the calculation method of the initial and iterative weights of the traditional AdaBoost algorithm, the convergence of this algorithm must be demonstrated by considering the upper bound of the loss function. For the overall sample, the loss function is(1)1M+N∑i=1M+NHxi≠yiifHxi≠yi,Hxi≠yi=1;ifHxi=yi,Hxi≠yi=0.Theorem 1.
1
/
M
+
N
∑
i
=
1
M
+
N
H
x
i
≠
y
i
≤
1
/
M
+
N
∑
i
exp
−
y
i
H
x
i
=
∏
T
Z
i
−
1
/
2.Proof.
IfHxi≠yi, −yiHxi<0. So, exp−yiHxi≥1, the left inequality is proofed:(2)wt+1,i=1/2M,ifyi=1,wt,i/Ztexp−αtyiHtxi,ifyi=−1,Zt=∑i=1M+Nwt,i=M∑i=1M12M+∑i=M+1M+nwt,iZtexp−αtyiHtxi=12+∑i=M+1M+nwt,iZtexp−αtyiHtxi,1M+N∑iexp−yiHxi=1M+N∑iexp−∑i=1M+NαtyiHtxi=w1,i∑iexp−∑i=1M+NαtyiHtxi=w1,i∏1M+Nexp−αtyiHtxi=Z1−12∑iw2,i∏2M+Nexp−αtyiHtxi=Z1−12Z2−12∑iw3,i∏3M+Nexp−αtyiHtxi=Z1−12Z2−12…ZT−1∑iwT,iexp−αTyiHTxi=∏1TZt−12.
Theorem1 indicates that although the algorithm assigns more importance to the classification accuracy of the minority class samples, the loss function of the overall sample is still convergent. Therefore, when using the Linkboost algorithm, the node pairs with the connected edges have a high recall rate, which provides a good basis for the development of the attack strategy.


## 3.1. Network Vulnerability and Class Imbalance

A network can be represented as a simple undirected graphG = (V, E), where V is the set of nodes and E is the set of links. Let N = |V| and W = |E| be the numbers of nodes and links, respectively. ki denotes the degree of the node vi, which equals the number of links connected to node. We assume that all the nodes are known, but the partial link information is missing. The network can be observed as GO. It is assumed that the missing link information is predicted using the link prediction algorithm, and the predicted network is GP.We identify the crucial nodes from the predicted networkGP, and then use these nodes to attack the complete network G. Once a node is attacked, its attached edges are removed simultaneously. V^⊆Vdenotes the set of nodes that are attacked (important nodes), and E^⊆E denotes the set of removed links. Thus, the network obtained after the node attacks is G^=V−V^,E−E^. We define the disintegration ratioS=V^/NS∈0,1 as the vulnerability evaluation index of the node attacks. In this study, the high degree strategy [16] is employed, in which the nodes are selected to be attacked according to their degree ranks (i.e., high degree nodes are attacked first).Figure2 shows the difference in the direct attack and attack after link prediction. We assume that three links are hidden, which are marked as red edges in Figure 2(a), and the observed network GO is as shown in Figure 2(b). In this case, Vb is the largest degree node (degree = 3) that can be observed. According to the high degree strategy, Vb is attacked first. When Vb is removed, the residual network is as shown in Figure 2(c). At this point, the disintegration ratio S=V^/N=4/7. In contrast from the direct attack, the proposed method involves adding a possible edge by using the link prediction algorithm on the basis of the incomplete networkGO, which generates the repaired network GP, as shown in Figure 2(d). Next, we use the high degree strategy from GP to attack the network. The largest degree node is Ve, which has a degree of four. After attacking node Ve, the residual network is as shown in Figure 2(e), and the disintegration ratioS=V^/N=3/7. This finding shows that the attack strategy is more effective after the network is repaired using the link prediction algorithm.Figure 2
Comparison between the residual networks for a direct attack and attack after link prediction. (a) Complete networkG. (b) Incomplete network GO with three hidden edges. (c) Residual network after node Vb, which is the highest degree node in the incomplete network GO, is attacked. (d) Predicted network GP with three predicted links added (red dotted lines). (e) Residual network after node Ve, which is the highest degree node in the predicted network GP, is attacked.Figure2 indicates that the use of a suitable link prediction algorithm is the core of the abovementioned network attack strategy. Such algorithms aim at estimating the likelihood of the existence of a link between two nodes based on the observed network structure and the attributes of the nodes. Given that G=V,E, all the nodes are assumed to be known, and the partial link information is considered missing. We define α=EM/W,α∈0,1 as the proportion of the missing links. In general link prediction research, the hidden edges are randomly selected. EO and EM denote the sets of the observed links and missing links, respectively. Clearly, EO∪EM=E. Therefore, the observed network can be represented as GO=V,EO. Let EU=V×V represent the universal set containing all N(N − 1)/2 possible links. The task of link prediction is to reveal the set of missing links EM via link prediction. GP represents the improved network involving the additional predicted links EP. β=EP/EO is defined as the magnitude of the additional link information.In the existing research, many scholars demonstrated that the use of machine-learning algorithms could achieve a high accuracy in link prediction. From the perspective of machine-learning algorithms, the link prediction problem can be regarded as a binary classification problem. Ifu∈V,v∈V, and u,v∈EO, the pair of nodes u,v can be considered a positive example if a link exists between u and v. In contrast, if the pair of nodes is a negative example, no edge is present between u and v. In a real network, the number of connected nodes in the network is considerably smaller than the number of node pairs without an edge, which means E≪EU−E. In the field of machine learning, this condition represents an imbalanced classification problem. Because the goal of most machine algorithms is to minimize the overall sample prediction error, the prediction results may be biased if we ignore the imbalanced distribution of the classes. For a given network, the misclassification of minority class samples means that the hidden edges are not correctly recognized. In particular, when the degree of a node is extremely small, the link prediction algorithm tends to predict that the node has no connection to other nodes. However, in the study of the network vulnerability, some nodes connecting the subnetwork may have only a few connected edges, and these may represent the minority class samples. If this part of the node pairs is not correctly predicted, the wrong attack strategy will be formulated. Therefore, this work focuses on the design of the link prediction algorithm for the class imbalance problem, aiming to restore the network as much as possible to develop the optimal attack strategy.


## 3.2. Linkboost Link Prediction

The link prediction problem, as one of the most significant link analysis and mining tasks, has been used to restore complete networks according to partially observed information. The link prediction algorithm has been applied in the social, biological, and bioinformatics domains to help better analyze and understand the structural topology and evolution mechanism of a network. In this study, we propose a novel link prediction algorithm, Linkboost, which improves the AdaBoost algorithm by increasing the sampling weight of the minority samples in an adaptive manner. The proposed algorithm is expected to solve the problem of imbalanced data distribution in the network and improve the accuracy of link prediction.The link prediction framework of Linkboost is shown in Figure3. First, the static indicators (such as the degree) of the network and similarity indicators (such as the common neighbor) of the node networks are used to extract the feature of the node pairs in the network. Next, the Linkboost algorithm is used to improve the classification accuracy of the minority class by performing resampling with preference. Finally, the network vulnerability is examined using high degree attack strategies by considering the proportion of the missing link α and the magnitude of the additional link β.Figure 3
Overview of the Linkboost framework.In the existing link prediction research, many network structural features have been used to describe the topology characteristics of the network. Based on the past literature [21, 22] and considering the global characteristics of real network nodes, we add two kinds of features based on the distance and random walk:(1)
Node-based features: node degree and high-order degree(2)
Features based on common neighbors: number of common neighbors, Jaccard index, AA index, Katz index, and Salton index(3)
Features based on distance: shortest path and partial region path(4)
Features based on random walks: PageRank [23] and SimRank [22]After completing the feature extraction of the network, these features are fed into the Linkboost algorithm. The pseudocode of the Linkboost algorithm is presented as Algorithm1.Algorithm 1: Process flow of the Linkboost link prediction algorithm.
Input: Network missing adjacency matrix A
Output: Final strong hypothesis Hx=∑t=1Tαthtx, connection score R1, nonconnection score R2.
(1)
Extract features and tag,S=x1,y1,…,xm,ym, xi∈X, yi∈−1,+1. Here xi is the feature of the network node pair, yi is the label of the node pair, indicating whether there is an edge exists. M=EO, N=EU−EO.
(2)
Initialize the weight distribution of the training data.D1=w11,w12,…,w1A, where w1,i=1/2M, if yi=1; w1,i=1/2N, if yi=−1.
(3)
For t in T iterations
(4)
ResampleS according to Dt
(5)
Findht:argminεj=∑i=1my≠hjxi, wherehj∈H.
(6)
If εi<1/2
(7)
Continue
(8)
else
(9)
saveht, calculate αt=1/2∗log1−εt/εt,
(10)
updateDt+1=wt+1,1,wt+1,2,…,wt+1,A and Zt=∑jAwt+1,j
(11)
If yi=1, wt+1,j=1/2M;
(12)
If yi=−1,wt+1,j=wt,i/Ztexp−αmyihtxi,i=1,2,…,A
(13)
End If
(14)
End For
(15)
Predict connection of the network usingHx=∑t=1Tαthtx, obtain R1 and R2As mentioned previously, in the proposed algorithm, the sampling mode is changed so that each iteration of the sampling focuses not only on the misclassified samples but also on the minority class samples. Specifically, in the initialization step, the weight of the positive examples (which also belong to the minority class) is defined asw1i+=1/2M, where M is the number of edges. The weight of the negative examples (which also belong to the majority class) is defined as w1i−=1/2N, where N is the number of nodes pairs without a connection. In most real-world networks, M≪N and w1,i+≫w1,i−; therefore, the positive sample is easier to be sampled. In the process of iteration, the update mode is also affected by the class label. For a positive sample, the weight of the next sample is the same as 1/2M, so as to assign a higher probability of being sampled. For a negative sample, the weights are updated based on whether they are classified correctly. In negative cases, the misclassified node pairs have a higher probability of being sampled in the next iteration. If the negative sampleyi=−1 is classified correctly, htxi=−1. Consequently, −αmyihtxi<0 and wt+1<wt. This means that if the negative samples are classified correctly, the probability of being sampled in the next iteration is decreased. If the prediction is wrong, the probability of being sampled in the next round increases. However, because of the limitation of the normalization factor Zt, the expectation of the sampling weight of the negative samples is smaller than that of the positive samples Ew+>Ew−. This means that the model pays more attention to the recall of the positive samples while focusing on learning the samples that are easily misclassified. This improved sampling method can help recognize more node pairs with connected edges.As the proposed approach modified the calculation method of the initial and iterative weights of the traditional AdaBoost algorithm, the convergence of this algorithm must be demonstrated by considering the upper bound of the loss function. For the overall sample, the loss function is(1)1M+N∑i=1M+NHxi≠yiifHxi≠yi,Hxi≠yi=1;ifHxi=yi,Hxi≠yi=0.Theorem 1.
1
/
M
+
N
∑
i
=
1
M
+
N
H
x
i
≠
y
i
≤
1
/
M
+
N
∑
i
exp
−
y
i
H
x
i
=
∏
T
Z
i
−
1
/
2.Proof.
IfHxi≠yi, −yiHxi<0. So, exp−yiHxi≥1, the left inequality is proofed:(2)wt+1,i=1/2M,ifyi=1,wt,i/Ztexp−αtyiHtxi,ifyi=−1,Zt=∑i=1M+Nwt,i=M∑i=1M12M+∑i=M+1M+nwt,iZtexp−αtyiHtxi=12+∑i=M+1M+nwt,iZtexp−αtyiHtxi,1M+N∑iexp−yiHxi=1M+N∑iexp−∑i=1M+NαtyiHtxi=w1,i∑iexp−∑i=1M+NαtyiHtxi=w1,i∏1M+Nexp−αtyiHtxi=Z1−12∑iw2,i∏2M+Nexp−αtyiHtxi=Z1−12Z2−12∑iw3,i∏3M+Nexp−αtyiHtxi=Z1−12Z2−12…ZT−1∑iwT,iexp−αTyiHTxi=∏1TZt−12.
Theorem1 indicates that although the algorithm assigns more importance to the classification accuracy of the minority class samples, the loss function of the overall sample is still convergent. Therefore, when using the Linkboost algorithm, the node pairs with the connected edges have a high recall rate, which provides a good basis for the development of the attack strategy.


## 4. Experiment and Results Analysis

### 4.1. Proportion of the Missing Links and Magnitude of the Additional Link Information

Linkboost predicts a network from an incomplete network; however, two problems remain. (1) The degree of incompleteness for a network, that is, the missing link proportion in the network must be defined. (2) Although the Linkboost algorithm can be used to determine the classification scoresR1 and R2, where R1+R2=1, the threshold to separate the two classes must still be determined. In the network, the number of edges predicted to be added must be determined. To address these two problems, we define two parameters α and β:(3)α=EME,β=EPEO.Here,α represents the proportion of the edges that are missed among all the edges. A smaller α means that a larger number of positive samples can be learned using the learning algorithm. β represents the ratio of the additional link information obtained using Linkboost.


### 4.2. Experimental Data and Evaluation Metrics

To experimentally validate the effectiveness of the algorithm and analyze the sensitivity of the parametersα and β in different networks, four real large-scale networks were employed, including ArXiv hep-th, Cora citation, Facebook, and Skitter. ArXiv hep-th [24] is the network of publications in ArXiv’s High Energy Physics, Theory (hep-th) section. The directed links that connect the publications are citations. In the Cora network [25], the nodes represent scientific papers, and the edge between two nodes indicates the existence of co-authorship. The Facebook network [26] describes a network in which a part of Facebook users follow each other. The Skitter network [24] is the undirected network of autonomous systems on the Internet connected to each other, as obtained from the Skitter project. Table 1 presents a clear representation of the imbalance of the network data and the impact of the network topology attributes on the network vulnerability.Table 1
Topology index of the four networks.
Network
V
E
k
Cluster coefficient
Assortativity
ArXiv hep-th
27,770
352,807
25.41
0.12
−0.03
Cora network
23,166
91,500
7.90
0.12
−0.05
Facebook
46,952
876,993
37.35
0.09
0.22
Skitter
1,696,415
11,095,298
13.08
0.53
−0.08The evaluation index used in this study is divided into two parts: one to evaluate the accuracy of the Linkboost algorithm in the link prediction task, and the other to evaluate the vulnerability of the network with differentα and β values. In machine learning, the area under the curve (AUC) approach is generally used to evaluate the accuracy of classification for data with an imbalanced class distribution. The AUC index is more accurate than other predictive accuracy indicators such as the accuracy, recall, and precision.After using the link prediction algorithm, the network is predicted with the added edges. Owing to the implementation of the effective high degree strategy, the network begins to collapse. To measure the vulnerability of the network after the attack, Xiao et al. [27] considered the largest component size during all possible baleful attacks and presented an evaluation metric Sn:(4)Sn=VSV,f=nV,whenSn=0,where V is the number of nodes in a complex network, VS is the largest component fraction after attackingn nodes, and Sn reflects the degree of network destruction. A smaller Sn corresponds to a larger amount of network destroyed. The zero point (which refers to the point of complete collapse of the network) of Sn is denoted by the disintegration evaluation metric f, which represents the proportion of nodes that needs to be attacked.


### 4.3. Comparative Algorithm Theory

The Linkboost algorithm proposed in this paper mainly targets at the data with imbalanced class distribution, such as complex network node pairs. In order to study the accuracy and applicability of this algorithm, other existing algorithms are used for comparison.AUC-logistic regression [28]: for training sets, T=i,j,zi,j∈E,i,z∉E. The optimization goals of the learning algorithm are(5)φAUC−Logistic=∑i,j,z∈TℓxiTMxj−xiTMxZ,where M is the feature matrix and xiis the ith row of the adjacent matrix.K-means undersampled [29]: in this algorithm, K-means algorithm is used to find the cluster center, and the data around the cluster center are undersampled. By reducing the majority of class samples, the positive and negative class distribution is balanced.Entropy algorithm [30]: the algorithm proves the applicability of crossentropy to the distributed unbalanced data and uses the sorting of crossentropy to find the hidden edge:(6)minMLM=λΩM+∑q∈VφSRM,Rq,where SqM represents the independence between vectors in the feature matrix M, Ω represents the regularized parameters to prevent overfitting of the learning algorithm, P is crossentropy, and the function ϕ is(7)φS,R=−∑i=1N−1PRilogPsi.RankSVM [31]: the training set T=i,j,zi,j∈E,i,z∉E. The optimization goals of the learning algorithm are(8)φSVM=∑i,j,z∈Tmax0,1+xiTMxz−xiTMxj,where M is the adjacent matrix and xi is the ith row of the connection matrix.Because the Linkboost algorithm is an improvement of the AdaBoost algorithm, we compare it with the original AdaBoost algorithm to demonstrate that the proposed technique is more suitable for the classification of imbalanced data.


### 4.4. Analysis of Experimental Results

Table2 presents the performance of each algorithm on the AUC index. In general, the Linkboost algorithm achieves high prediction accuracy.Table 2
Comparison of link prediction results.
AUC
AUC-logistic
K-means undersampled
Entropy
RankSVM
Adaboost
Linkboost
ArXiv hep-th
0.9098
0.6502
0.8239
0.8412
0.7715
0.9122
Cora citation
0.9397
0.7201
0.9066
0.8239
0.8024
0.9401
Facebook
0.8510
0.7701
0.7923
0.6248
0.8122
0.8517
Skitter
0.8760
0.7245
0.7966
0.8539
0.8038
0.8839the prediction is completed, it is necessary to set the threshold to identify the number of edges added to the observed networkEO so that the high degree attack strategy can be developed on the basis of the network EO+EP. In the analysis described herein, we use different α and β to observe the change in the network vulnerability index f and determine the optimal edge addition proportion β∗, which makes the network most prone to collapse. Specifically, we perform testing on the ArXiv hep-th network, as shown in Figure 4.Figure 4
Disintegration evaluation metric as a function of the additional link information ratio with regard to the complete and predicted networks. (a)α = 0.1. (b) α = 0.3. (c) α = 0.5. (d) α = 0.7.
(a)
(b)
(c)
(d)As shown in Figure4, the red dashed lines represent the proportion of the attacking nodes when the network totally collapses with complete information. The blue lines represent the proportion of the attacking nodes when the network totally collapses with the additional predicted information. Figure 4(a) illustrates a unique phenomenon involving 10% covered edges. After different proportions β of edges are added through link prediction, the network crashes faster than in the case of an attack with complete information. This finding is in contrast to an intuitive sense that decisions made with incomplete information should be less accurate than those made with complete information.To further evaluate this unexpected phenomenon, we examined the vulnerability indexf of the network under different parameter combinations α,β, and the results are shown in Figure 5. It can be seen that when the network has a few missing edges, adding the edges appropriately can accelerate the network collapse. When β is more than a certain threshold, the efficiency of the network disintegration roughly increases as β increases. The thresholds differ from each other as the missing link proportion α changes.Figure 5
Disintegration evaluation metricf as a function of the proportion of missing links and ratio of the additional link information.To illustrate the influence ofα on the network vulnerability, we control the ratio of α and change the attack node proportion. Four scenarios are considered: (1) α=0.1; (2) α=0.2; (3) α=0.5; and (4)α=0.7, where β=β∗. By adopting the high degree node attacking strategy, the vulnerability of the original networks is calculated after each attack. Subsequently, the network vulnerability evaluation metric is calculated. Figure 6 shows the simulation results for the four scenarios in the route views network, which has relatively few nodes (6747 nodes) for convenient calculation. It can be seen that when α=0.1,0.2,0.5, the attack strategy after link prediction is more effective than a direct attack (marked as green areas). In particular, when α=0.1, the high degree attack strategy after link prediction outperforms the degree attack strategy with complete information.Figure 6
Size of the giant component versus the proportion of attacked nodes with regard to the incomplete, complete, and predicted networks. (a)α = 0.1. (b) α = 0.3. (c) α = 0.5. (d) α = 0.7.
(a)
(b)
(c)
(d)To examine whether this phenomenon is also applicable to other networks, we performed research considered four large networks. A total of 10% of the edges in the network were hidden randomly, yieldingα=0.1. Next, we observed the change in the vulnerability index f under different β. According to Figure 7, in the ArXiv hep-th, Cora citation, and Skitter network, the high degree attack strategy based on the repaired network is better than that with complete information. However, in the Facebook network, regardless of the number of links added, the high degree attack strategy under complete information is always the optimal choice.Figure 7
Disintegration evaluation metric as a function of the ratio of additional link information in four real networks when the proportion of the missing links is small (α = 0.1). (a) ArXiv hep-th network. (b) Cora citation network. (c) Facebook network. (d) Skitter network.
(a)
(b)
(c)
(d)This phenomenon can be explained as follows. For many real-world information networks, owing to privacy or legal restrictions, the problem of data sparsity exists in the network structure [32]. In other words, implicit connections exist in the network, which makes it difficult to evaluate the importance of the nodes that are not explicitly connected [33]. Consequently, Linkboost is designed to clarify the implicit structure as much as possible, which provides valuable guidance for the design of a more effective attack strategy.To verify this aspect, we repeated the previous test on a complete network. In contrast from the last experiment, the role of link prediction was not to reveal the edges selected to be hidden but to add implicit edges to assist in formulating attack strategies. Consequently, we setα=0 and varied β. Similar to the last experiment, the high degree node attacking strategy was adopted, and f was calculated after each attack.Figure8 shows that the attack strategy after link prediction still outperforms the direct attack even in a complete network. The exception to this rule is the Facebook network, in which after β>0, f increases with the increase in β, as shown in Figure 8(c). In a sense, this example illustrates that Linkboost does not provide effective guidance for the attack strategy of the Facebook network. This exception can be explained by the network topologies listed in Table 1. In contrast to that of other three networks, the assortativity index of the Facebook network is positive (0.22), indicating that the high degree nodes tend to connect with other large degree nodes in the network. Furthermore, this trend indicates that the implicit edge in the network may exist in the node pairs with a high degree. However, Linkboost prioritizes the classification accuracy of the minority samples, which makes it difficult to predict the connection between the large degree nodes. This aspect explains why Linkboost cannot effectively develop an effective attack strategy on a network with positive assortativity, such as the Facebook network.Figure 8
Disintegration evaluation metric as a function of the ratio of additional link information in four real networks with no missing linksα=0. Linkboost is applied on these four complete networks to reveal the implicit links to help design a more effective attack strategy. (a) ArXiv hep-th network. (b) Cora citation network. (c) Facebook network. (d) Skitter network.
(a)
(b)
(c)
(d)


## 4.1. Proportion of the Missing Links and Magnitude of the Additional Link Information

Linkboost predicts a network from an incomplete network; however, two problems remain. (1) The degree of incompleteness for a network, that is, the missing link proportion in the network must be defined. (2) Although the Linkboost algorithm can be used to determine the classification scoresR1 and R2, where R1+R2=1, the threshold to separate the two classes must still be determined. In the network, the number of edges predicted to be added must be determined. To address these two problems, we define two parameters α and β:(3)α=EME,β=EPEO.Here,α represents the proportion of the edges that are missed among all the edges. A smaller α means that a larger number of positive samples can be learned using the learning algorithm. β represents the ratio of the additional link information obtained using Linkboost.


## 4.2. Experimental Data and Evaluation Metrics

To experimentally validate the effectiveness of the algorithm and analyze the sensitivity of the parametersα and β in different networks, four real large-scale networks were employed, including ArXiv hep-th, Cora citation, Facebook, and Skitter. ArXiv hep-th [24] is the network of publications in ArXiv’s High Energy Physics, Theory (hep-th) section. The directed links that connect the publications are citations. In the Cora network [25], the nodes represent scientific papers, and the edge between two nodes indicates the existence of co-authorship. The Facebook network [26] describes a network in which a part of Facebook users follow each other. The Skitter network [24] is the undirected network of autonomous systems on the Internet connected to each other, as obtained from the Skitter project. Table 1 presents a clear representation of the imbalance of the network data and the impact of the network topology attributes on the network vulnerability.Table 1
Topology index of the four networks.
Network
V
E
k
Cluster coefficient
Assortativity
ArXiv hep-th
27,770
352,807
25.41
0.12
−0.03
Cora network
23,166
91,500
7.90
0.12
−0.05
Facebook
46,952
876,993
37.35
0.09
0.22
Skitter
1,696,415
11,095,298
13.08
0.53
−0.08The evaluation index used in this study is divided into two parts: one to evaluate the accuracy of the Linkboost algorithm in the link prediction task, and the other to evaluate the vulnerability of the network with differentα and β values. In machine learning, the area under the curve (AUC) approach is generally used to evaluate the accuracy of classification for data with an imbalanced class distribution. The AUC index is more accurate than other predictive accuracy indicators such as the accuracy, recall, and precision.After using the link prediction algorithm, the network is predicted with the added edges. Owing to the implementation of the effective high degree strategy, the network begins to collapse. To measure the vulnerability of the network after the attack, Xiao et al. [27] considered the largest component size during all possible baleful attacks and presented an evaluation metric Sn:(4)Sn=VSV,f=nV,whenSn=0,where V is the number of nodes in a complex network, VS is the largest component fraction after attackingn nodes, and Sn reflects the degree of network destruction. A smaller Sn corresponds to a larger amount of network destroyed. The zero point (which refers to the point of complete collapse of the network) of Sn is denoted by the disintegration evaluation metric f, which represents the proportion of nodes that needs to be attacked.


## 4.3. Comparative Algorithm Theory

The Linkboost algorithm proposed in this paper mainly targets at the data with imbalanced class distribution, such as complex network node pairs. In order to study the accuracy and applicability of this algorithm, other existing algorithms are used for comparison.AUC-logistic regression [28]: for training sets, T=i,j,zi,j∈E,i,z∉E. The optimization goals of the learning algorithm are(5)φAUC−Logistic=∑i,j,z∈TℓxiTMxj−xiTMxZ,where M is the feature matrix and xiis the ith row of the adjacent matrix.K-means undersampled [29]: in this algorithm, K-means algorithm is used to find the cluster center, and the data around the cluster center are undersampled. By reducing the majority of class samples, the positive and negative class distribution is balanced.Entropy algorithm [30]: the algorithm proves the applicability of crossentropy to the distributed unbalanced data and uses the sorting of crossentropy to find the hidden edge:(6)minMLM=λΩM+∑q∈VφSRM,Rq,where SqM represents the independence between vectors in the feature matrix M, Ω represents the regularized parameters to prevent overfitting of the learning algorithm, P is crossentropy, and the function ϕ is(7)φS,R=−∑i=1N−1PRilogPsi.RankSVM [31]: the training set T=i,j,zi,j∈E,i,z∉E. The optimization goals of the learning algorithm are(8)φSVM=∑i,j,z∈Tmax0,1+xiTMxz−xiTMxj,where M is the adjacent matrix and xi is the ith row of the connection matrix.Because the Linkboost algorithm is an improvement of the AdaBoost algorithm, we compare it with the original AdaBoost algorithm to demonstrate that the proposed technique is more suitable for the classification of imbalanced data.


## 4.4. Analysis of Experimental Results

Table2 presents the performance of each algorithm on the AUC index. In general, the Linkboost algorithm achieves high prediction accuracy.Table 2
Comparison of link prediction results.
AUC
AUC-logistic
K-means undersampled
Entropy
RankSVM
Adaboost
Linkboost
ArXiv hep-th
0.9098
0.6502
0.8239
0.8412
0.7715
0.9122
Cora citation
0.9397
0.7201
0.9066
0.8239
0.8024
0.9401
Facebook
0.8510
0.7701
0.7923
0.6248
0.8122
0.8517
Skitter
0.8760
0.7245
0.7966
0.8539
0.8038
0.8839the prediction is completed, it is necessary to set the threshold to identify the number of edges added to the observed networkEO so that the high degree attack strategy can be developed on the basis of the network EO+EP. In the analysis described herein, we use different α and β to observe the change in the network vulnerability index f and determine the optimal edge addition proportion β∗, which makes the network most prone to collapse. Specifically, we perform testing on the ArXiv hep-th network, as shown in Figure 4.Figure 4
Disintegration evaluation metric as a function of the additional link information ratio with regard to the complete and predicted networks. (a)α = 0.1. (b) α = 0.3. (c) α = 0.5. (d) α = 0.7.
(a)
(b)
(c)
(d)As shown in Figure4, the red dashed lines represent the proportion of the attacking nodes when the network totally collapses with complete information. The blue lines represent the proportion of the attacking nodes when the network totally collapses with the additional predicted information. Figure 4(a) illustrates a unique phenomenon involving 10% covered edges. After different proportions β of edges are added through link prediction, the network crashes faster than in the case of an attack with complete information. This finding is in contrast to an intuitive sense that decisions made with incomplete information should be less accurate than those made with complete information.To further evaluate this unexpected phenomenon, we examined the vulnerability indexf of the network under different parameter combinations α,β, and the results are shown in Figure 5. It can be seen that when the network has a few missing edges, adding the edges appropriately can accelerate the network collapse. When β is more than a certain threshold, the efficiency of the network disintegration roughly increases as β increases. The thresholds differ from each other as the missing link proportion α changes.Figure 5
Disintegration evaluation metricf as a function of the proportion of missing links and ratio of the additional link information.To illustrate the influence ofα on the network vulnerability, we control the ratio of α and change the attack node proportion. Four scenarios are considered: (1) α=0.1; (2) α=0.2; (3) α=0.5; and (4)α=0.7, where β=β∗. By adopting the high degree node attacking strategy, the vulnerability of the original networks is calculated after each attack. Subsequently, the network vulnerability evaluation metric is calculated. Figure 6 shows the simulation results for the four scenarios in the route views network, which has relatively few nodes (6747 nodes) for convenient calculation. It can be seen that when α=0.1,0.2,0.5, the attack strategy after link prediction is more effective than a direct attack (marked as green areas). In particular, when α=0.1, the high degree attack strategy after link prediction outperforms the degree attack strategy with complete information.Figure 6
Size of the giant component versus the proportion of attacked nodes with regard to the incomplete, complete, and predicted networks. (a)α = 0.1. (b) α = 0.3. (c) α = 0.5. (d) α = 0.7.
(a)
(b)
(c)
(d)To examine whether this phenomenon is also applicable to other networks, we performed research considered four large networks. A total of 10% of the edges in the network were hidden randomly, yieldingα=0.1. Next, we observed the change in the vulnerability index f under different β. According to Figure 7, in the ArXiv hep-th, Cora citation, and Skitter network, the high degree attack strategy based on the repaired network is better than that with complete information. However, in the Facebook network, regardless of the number of links added, the high degree attack strategy under complete information is always the optimal choice.Figure 7
Disintegration evaluation metric as a function of the ratio of additional link information in four real networks when the proportion of the missing links is small (α = 0.1). (a) ArXiv hep-th network. (b) Cora citation network. (c) Facebook network. (d) Skitter network.
(a)
(b)
(c)
(d)This phenomenon can be explained as follows. For many real-world information networks, owing to privacy or legal restrictions, the problem of data sparsity exists in the network structure [32]. In other words, implicit connections exist in the network, which makes it difficult to evaluate the importance of the nodes that are not explicitly connected [33]. Consequently, Linkboost is designed to clarify the implicit structure as much as possible, which provides valuable guidance for the design of a more effective attack strategy.To verify this aspect, we repeated the previous test on a complete network. In contrast from the last experiment, the role of link prediction was not to reveal the edges selected to be hidden but to add implicit edges to assist in formulating attack strategies. Consequently, we setα=0 and varied β. Similar to the last experiment, the high degree node attacking strategy was adopted, and f was calculated after each attack.Figure8 shows that the attack strategy after link prediction still outperforms the direct attack even in a complete network. The exception to this rule is the Facebook network, in which after β>0, f increases with the increase in β, as shown in Figure 8(c). In a sense, this example illustrates that Linkboost does not provide effective guidance for the attack strategy of the Facebook network. This exception can be explained by the network topologies listed in Table 1. In contrast to that of other three networks, the assortativity index of the Facebook network is positive (0.22), indicating that the high degree nodes tend to connect with other large degree nodes in the network. Furthermore, this trend indicates that the implicit edge in the network may exist in the node pairs with a high degree. However, Linkboost prioritizes the classification accuracy of the minority samples, which makes it difficult to predict the connection between the large degree nodes. This aspect explains why Linkboost cannot effectively develop an effective attack strategy on a network with positive assortativity, such as the Facebook network.Figure 8
Disintegration evaluation metric as a function of the ratio of additional link information in four real networks with no missing linksα=0. Linkboost is applied on these four complete networks to reveal the implicit links to help design a more effective attack strategy. (a) ArXiv hep-th network. (b) Cora citation network. (c) Facebook network. (d) Skitter network.
(a)
(b)
(c)
(d)


## 5. Conclusions

This paper proposes a novel link prediction algorithm Linkboost, considering the imbalanced class distribution of network data. This method is conducive to the development of an attack strategy when the complete information of network cannot be obtained directly. The algorithm can be applied to different real networks, and it can help discover valuable linking information to conduct a network vulnerability investigation. To solve the problem of classification with imbalanced data, Linkboost changes the manner of updating the sampling weight adaptively when constructing the subclassifiers. The convergence of the algorithm was demonstrated by analyzing the upper bound of the loss function. Finally, we verified the effectiveness of the algorithm using four actual networks with different parameters. Linkboost achieved the best performance compared to that of other imbalanced classification algorithms. When using the complemented network, the developed attack strategy is more effective in accelerating the network collapse, which is more advantageous than a direct attack. Consequently, the proposed algorithm provides more sophisticated insights into incomplete information and helps restore the information of the network, which facilitates the identification of crucial nodes for network survivability.



---

*Source: 7348281-2020-04-08.xml*