{'fraction_non_alphanumeric': 0.027721096899417708, 'fraction_numerical': 0.007390633553974021, 'mean_word_length': 4.882172131147541, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Approach for Link Prediction in Directed Complex Networks based on Asymmetric Similarity-Popularity

Complex networks are graphs representing real-life systems that exhibit unique characteristics not found in purely regular or completely random graphs. The study of such systems is vital but challenging due to the complexity of the underlying processes. This task has nevertheless been made easier in recent decades thanks to the availability of large amounts of networked data. Link prediction in complex networks aims to estimate the likelihood that a link between two nodes is missing from the network. Links can be missing due to imperfections in data collection or simply because they are yet to appear. Discovering new relationships between entities in networked data has attracted researchers' attention in various domains such as sociology, computer science, physics, and biology. Most existing research focuses on link prediction in undirected complex networks. However, not all real-life systems can be faithfully represented as undirected networks. This simplifying assumption is often made when using link prediction algorithms but inevitably leads to loss of information about relations among nodes and degradation in prediction performance. This paper introduces a link prediction method designed explicitly for directed networks. It is based on the similarity-popularity paradigm, which has recently proven successful in undirected networks. The presented algorithms handle the asymmetry in node relationships by modeling it as asymmetry in similarity and popularity. Given the observed network topology, the algorithms approximate the hidden similarities as shortest path distances using edge weights that capture and factor out the links' asymmetry and nodes' popularity. The proposed approach is evaluated on real-life networks, and the experimental results demonstrate its effectiveness in predicting missing links across a broad spectrum of networked data types and sizes.


INTRODUCTION
Coupled biological and chemical systems, neural networks, the World Wide Web, and the Internet are a few examples of systems composed of highly interconnected units. Those systems are best described using graphs models that are neither purely regular nor completely random which are known as complex networks [1]. The study of complex networks has attracted the attention of many researchers in various branches of science and engineering, and considerable efforts have been made to understand complex networks' evolution, structure, and function. A critical issue that the research community faces is the incapacity to observe all relationships due either to limitations in the data collection process or because some relationships are to appear shortly in the future [2]. The process of identifying the yet unformed links is called link prediction.
In recent years, the link prediction problem has attracted increasing attention. Link prediction aims to predict the possible links that can form in the future between nodes based on the currently observed links. This problem is crucial both theoretically and practically. In theory, link prediction can help understand the mechanism of complex networks' evolution. Practically, link prediction can be applied in various fields, such as in biological networks, to infer the existence of a link, which will save time and cost. In social networks, link prediction can recommend new friends and enhance the user's experience. Link prediction can also help design efficient recommendation algorithms that include only the relevant information.
Due to the complexity of link prediction, researchers have proposed many prediction approaches over the years. Not all these algorithms, however, are tailored to complex networks [3]. The nature and topological characteristics of complex networks, such as hierarchical organization, the existence of popular nodes, and communities can be exploited to improve link prediction performance. Furthermore, most previous research focused on the link prediction problem in undirected networks, mainly due to their simplicity. However, not all real-life systems can be represented as undirected networks, and the symmetrization of such networks inevitably results in losing information about the relationships between the system's entities.
Despite the prevalence of directed networked data such as in communication networks, social networks, trust networks, and biological networks, research on directed link prediction methods remains limited. This paper introduces a novel link prediction approach explicitly designed for directed networks. The proposed approach falls into the category of similarity-popularity methods, which have recently been proven successful in undirected networks [4], [5]. Unlike in the undirected case, the proposed algorithms handle edge asymmetry by using asymmetric similarity and popularity measures. The algorithms generalize observed similarities to disconnected nodes using shortest path distances. To prove its performance, we experimentally evalu-ate the proposed method on a broad range of network types and sizes.
The rest of this paper is organized as follows. Section 2 gives a formal definition of the link prediction problem. Section 3 contains an overview of existing link prediction approaches, including those specifically designed for directed networks. The proposed method is presented in details in Section 4 and evaluated experimentally in Section 5. Finally, Section 6 concludes this paper and presents some future research directions.

PROBLEM STATEMENT
Link prediction lies at the intersection of several research fields including machine learning, data mining, recommended systems, and network science [6], [7], [8]. This versatility is due to the fact that many tasks related to networked data, such as product and friend recommendation or prediction of research paper citations and protein interactions, can be reduced to a link prediction task. Formally, a link prediction problem is defined by giving a graph G = (V, E), where V is the set of nodes, and E ⊆ V × V is the set of edges. We call E the set of observed edges and denote by U the set of unobserved edges, where U = V × V − E. The goal is to predict which elements of U should belong to E. The omission of some edges from E can be attributed to limitations in the data collection process or because these edges will appear shortly. In the directed network case, the set V × V , and consequently E and U , consists of ordered couples so that the edge (i, j) = (j, i).

RELATED WORK
This section will first present link prediction methods for undirected networks. Many of these methods can be used or adapted to directed networks but do not exploit the asymmetric nature of the relationships. We will cover four main link prediction approaches: topological similarity approaches, probabilistic approaches, classification-based approaches, and similarity-popularity approaches. Topological similarity-based methods do not require building a model of the network; they measure the score or distance between each pair of nodes in the network. This score is then used to estimate the possibility that the two corresponding nodes will form an edge. Probabilistic methods are usually based on Markov chains and Bayesian networks. They build a model for the whole network, which is then used to estimate the connection probability between disconnected pairs of nodes. Classification-based approaches predict links by training a classifier to discriminate between connected and disconnected couples using various topological features. Similarity-popularity methods assume that the connection between nodes is driven by two factors: popularity, which is an intrinsic property of the node, and similarity between nodes.
Finally, we will present link prediction methods specifically designed for direct networks.

Topological similarity methods
Similarity-based methods assume that nodes tend to connect to other similar nodes. They assign a similarity score to non-existing couples with the convention that pairs with a higher score are more likely to appear than those with a lower score. The similarity measure depends on the network's topological properties, but its form varies from one approach to another. Similarity-based methods can be divided according to the amount of information required to compute the score for a given couple of nodes into three categories: local, global and quasi-local methods.
When the score is calculated based on global methods, which consider the whole network topology, the cost to predict all edges can become prohibitive [3]. On the other hand, a score based on local methods considers only the immediate neighbors of each pair of nodes, which reduces the computational cost and makes them scalable to large complex networks. Lastly, quasi-local methods balance local and global approaches. They typically require more computations than local methods but offer higher prediction accuracy [3].

Local methods
Local similarity-based methods rely on the nodes' neighborhood structure to calculate the similarity to other nodes in the network. Local methods are generally fast and highly parallelizable, but their main drawback is that they fail to predict the formation of edges between nodes at a distance greater than two. Various local similarity measures have been proposed in the literature, including Adamic-Adar Index [9], Common Neighbors Index [10], Hub Depromoted Index [11], Hub Promoted Index [11], Jaccard Index [12], Leicht-Holme-Newman Index [10], Preferential Attachment Index [10], Salton Index [13], and Sorensen Index [14].
Authors in [15] compared the performance of nine local similarity-based methods on six real networks. The results show that Common Neighbors has the best overall performance, followed by Adamic-Adar. They then proposed a new similarity method inspired by resource allocation, and it gave better results than Common Neighbors while not requiring more information or computational time. This method uses information about the next nearest neighbors and enhances the algorithmic accuracy. Authors in [16] used a local path index to score node similarity, which strikes a compromise between computational requirements and prediction accuracy.

Global methods
Global similarity-based methods use the entire network topological information to score the edges. The advantage of these methods is that they can predict long-range edges that are impossible to predict with local methods. However, they have two main drawbacks. First, they scale poorly to large networks because of the intense computation required. The second drawback is that their parallelization can be very complex. Katz Index (KI) is a global link prediction method that sums the influence of all paths between two nodes, incrementally penalizing paths by their length [17]. Katz Index and all global methods generally consider paths of length greater than or equal to two.
The Random Walk method [18] assigns a couple (i, j) a score defined as the probability that a random walk that starts at i reaches j. Random Walk with Restart [19] is similar to Random Walk but introduces a probability of returning to the source node and restarting the walk, which results in higher scores for nodes near the source. Average Commute Time [20] is the average number of steps a random walker starting at node i takes to reach node j and return to i. Flow Propagation [21] is a variation of Random Walk with Restart where the normalized Laplacian matrix replaces the normalized adjacency matrix. SimRank [22] calculates the similarity between two nodes as the expected time it takes two random walks that start at the two nodes to meet.

Quasi-local methods
Quasi-local methods aim at balancing local and global topological similarity measures. They exhibit local methods' computational efficiency and global methods' topological visibility. They are not computationally overwhelmed since they do not consider the similarity between all pair of nodes, but neither are they limited to neighbors of neighbors. The most popular quasi-local methods are based on random walk models [18] and path counting [16]. In general, quasilocal scores can be seen as generalizations of local scores and can become equivalent to them by limiting specific depth parameters or computation steps. The Local Path Index [16] is a quasi-local method strongly based on the Katz index but considers only paths of limited length. Local Random Walk uses the random walk technique but limits the walk to a specific number of iterations [18]. Superposed Random Walk [18] emphasizes nodes in the local neighborhood by continuously releasing a new walker from the source node.

Probabilistic methods
Probabilistic approaches assume that the network has a known structure and build a model to fit this structure by estimating its parameters using statistical methods. The model is then used to estimate the probability of nonexisting edges [23].
The Hierarchical Random Graph model [24] is a probabilistic model that exploits the fact that many real networks exhibit a hierarchical structure. In these kinds of networks, nodes with a high degree have a lower clustering coefficient than low-degree nodes. High-degree nodes weakly connect highly clustered nodes within isolated communities, thus forming a hierarchical structure. Clauset et al. [24] proposed a method to represent a hierarchical structure using a dendrogram where each leaf represents a node in the network, and each internal node represents a cluster. Each internal node of the dendrogram is associated with the probability that a link exists between any of its children. The probability that two nodes are connected can then be computed by finding their lowest common ancestor.
Some networks in the real world do not fit in the hierarchical schema. The Stochastic Block Model assumes instead that the nodes are distributed in communities or blocks. The model restricts the communities from overlapping, and the probability of link formation between any two nodes depends on the block to which they belong [2].
The Fast Blocking Probabilistic Model [25] is based on partitioning the network into a set of blocks of either a community or a particular community composed of small degree nodes. The model uses a greedy strategy to partition the network into communities efficiently. The connection probability between a couple of nodes is estimated by computing the link density between and within communities over a set of partitions. This implies that two nodes will have a higher chance of forming a link if they belong to the same community.
The Cycle Formation Model is based on the assumption that the network aims to have close cycles in its formation process [26]. Such assumption matches the Common Neighbors method, which counts the number of cycles of length three that could be formed. This method captures the longer cycles by extending the clustering coefficient to a generalized clustering coefficient of higher order. This method can thus be seen as a generalization of the Common Neighbors method to longer cycles.

Classification-based approaches
Link prediction can be seen as a classification problem with two classes: one is positive, and the other is negative. The positive class represents connected pairs of nodes, whereas the negative class consists of disconnected couples. Hasan et al. [27] used local features such as the short distance between two nodes, aggregated features such as a sum of neighbors, and semantic features such as the number of matching keywords to discriminate between disconnected and connected couples. They used these features to build a classifier model that helps predict author collaboration and evaluated their approach on two co-authorship networks. They assessed each feature visually by comparing the density of the classes and then using well-defined feature ranking methods. As a result, they found that semantic similarity helps improve link prediction accuracy.
Link prediction is arguably an imbalanced problem where the two classes exhibit vast differences in size. Such extreme class skew reduces the performance of link prediction algorithms. There are generally two approaches to deal with this issue: downsampling the majority classes or oversampling the minority class. However, this approach might cause data loss in downsampling and noise in data oversampling. The second solution is reducing the problem to a cost-sensitive learning problem with unknown missclassification costs as proposed in [28]. The authors tackled this issue by proposing a new cost-sensitive formulation based on chance constraints. They tuned the cost to find the hypothesis that best separates the positive and negative instances and reduces the miss-classification cost. They performed a detailed evaluation of their approach using networks from three different domains. They found that they indeed can effectively formulate the link production as a complex structured prediction problem with many constraints.

Similarity-popularity methods
Similarity-popularity methods ascribe network topology to the similarity between nodes and their popularity, which is their capacity to connect to other nodes. Their assumption is that the more similar and popular the two nodes are, the higher their connection probability.
The complex network model proposed in [29] assumes the existence of a hidden metric space that underlies the network and governs the similarity between nodes. We refer to this model as the Hidden Metric Space Model (HMSM). The probability of connecting two nodes in an undirected network based on HMSM is defined as follows: where d ij is the distance between nodes i and j, κ i and κ j denote their expected degrees, and the characteristic distance scale φ(κ i , κ j ) ≈ κ i κ j . The parameter α represents the influence of the hidden metric space on the observed topology. Large values of α lead to a strong clustering in the network. The connection probability r ij increases when the distance d ij becomes small; similar nodes (characterized by a small distance in the hidden space) have a high probability to connect. The probability r ij also increases when κ i κ j becomes large. This is reflected in real networks where popular nodes (characterized by high degrees) tend to connect to many other nodes. The authors of [30] explored the trade-off between popularity and similarity in growing networks. Nodes in growing networks prefer to link to the most popular nodes and the closest ones to them. The authors compared their results with real-world complex networks, showing that the probability of forming new links was easily predicted with high accuracy. Following [30], the authors in [31] worked on two approaches to predict links in the Twitter network. The first is by combining rankings generated by popularity and similarity methods. The second approach is adapting collaborative filtering methods to combine popularity and similarity. The results showed that popularity-based methods generally achieve better performance. Authors in [32] proposed FastLP, a heuristic method that uses geodesic distance to estimate the distance between the nodes in the hidden metric space. It also uses the hidden metric space model [29] to estimate the nodes linking probabilities. The authors suggested multiplying the geodesic distance with a factor that gives the paths with more edges higher weights. The results show that their FastLP approach can handle large networks without reducing the prediction performance.
In [5], the authors propose a link prediction method where in addition to similarity and popularity, link formation also depends on attraction induced by the local neighborhood. In this approach, node popularity and local attraction are directly estimated from the observed network topology and factored out using a specific edge length map. The latter is then used to approximate the distance between non-adjacent nodes via shortest path distances.The method delivers highly accurate predictions at a low computational cost compared to global methods.

Link prediction in directed networks
Most research on link prediction focuses on undirected networks, mostly to their simplicity compared to directed networks. Nonetheless, some authors tackled the problem explicitly in the directed case [33], [34].
In [33], the authors proposed a link prediction technique using a graph pattern called Triadic Closeness to predict links between nodes in directed graphs. The approach assigns a probability to edges that might be closed in the future based on node weight. The weighting procedure distinguishes between the popular neighbors and the neighbors unique only to a few users by giving the latter a higher weight. The authors also designed a reusable framework to handle different social networks. The framework consists of three layers: data, prediction, and presentation. The data layer is concerned with low-level data handling and persistence management. The prediction layer groups the logic of metric calculations and triad detection. The similarity algorithms and evaluation metrics are applied in this layer to compare the results. Finally, the presentation layer provides visualization and export capabilities. The results show that the pattern-based approach gives better results than local algorithms.
Authors in [34] tacked the problem of link prediction in large networks where algorithms suffer from low scalability and precision problems. As a trade-off between these two issues, the authors proposed a link prediction algorithm that exploits the hierarchical properties of directed networks. The proposed method can be classified as a local method for scoring the edges, making it scalable to large networks. They assume the existence of a local hierarchy which results in better prediction precision. They demonstrated the effectiveness and efficiency of their method on two hierarchical datasets and one non-hierarchical dataset.
Compared to research on link prediction in undirected networks, link prediction in directed networks has received little attention from the research community. There is a clear need for methods specific to directed networked data that can handle and exploit the asymmetric nature of node relationships to produce more accurate predictions, which constitutes the aim of this work.

THE PROPOSED ALGORITHMS
The hidden metric space model [4], [29], [35], [36] is a similarity-popularity model initially proposed for undirected networks. It assumes that nodes tend to connect if they are popular or similar; that is, they are close to each other in the hidden metric space. This idea inspires the first link prediction algorithm we propose in this paper. We assume that each node i has a hidden in-degree κ in i and a hidden out-degree κ out i in addition to the hidden distance. The probability that a node i connects to a node j is then given by where d ij is the hidden distance between nodes i and j, and φ is the characteristic distance scale function that should be increasing in its two parameters. We propose to use the following characteristic distance scale function: where κ out max and κ in max are the maximum in-degree and outdegree in the network respectively. Hence, the probability of the directed edge (i, j) increases when i has a large hidden out-degree and j has a large hidden in-degree. Using this formula implies that, in general, r ij = r ji even if the distances are symmetric. Note that, in contrast to the Algorithm 1 1: for each node i ∈ V do 2:κ in i ← the observed in-degree of node i, 3:κ out i ← the observed out-degree of node i, 4: end for 5: for each link (i, j) ∈ E do 6: w ij ← log(κ out i + 1) + log(κ in j + 1) log(κ out max + 1) + log(κ in max + 1) , 7: end for 8: {d ij } ←ShortestPathDistance(V, E, {w ij }, h) 9: for each couple (i, j) / ∈ E do 10: π ij ← log(κ out i + 1) + log(κ in j + 1) log(κ out max + 1) + log(κ in max + 1) , 11: Since the metric space is hidden, we will use the partially observed topology to estimate the hidden distances d ij . To achieve this, we assume that the hidden degree of the node equals the observed one, that is, κ out i =κ out i and κ in i = κ in i , whereκ out i andκ in i are the observed out-degree and in-degree of node i respectively. For each edge (i, j) in the network, we assign the weight w ij defined as follows: Hence edges between popular nodes are assigned larger weights than edges linking unpopular nodes. The rationale is that the connection between two nodes with a large degree can be explained by their popularity and does not require high similarity between them. Distance between non-adjacent nodes is computed as the (directed) shortest path distance between them. If no path exists between two nodes, their distance is set to +∞. We use Dijkstra's algorithm to calculate the shortest path distances due to its low computational time complexity compared to other algorithms. To reduce the computational overhead further, we follow [5] and impose a horizon depth limit on the shortest paths. Namely, we run Dijkstra's algorithm up to h edges from the source node; Any nodes that cannot be reached by up to h edges are assigned infinite distance. Finally, the directed edge (i, j) is assigned the score: The resulting link prediction algorithm is shown in Algorithm 1.
The second algorithm we propose in this paper is an adaptation of the one proposed in [5] to directed networks. This approach is also a similarity-popularity link prediction method but assumes an additional factor that affects the formation of links: local attraction. More precisely, the likelihood of a link joining two nodes i and j is assumed proportional to where σ ij is the similarity between i and j, π ij is the popularity term, and η ij represents the attraction induced by the local neighborhood. Following [5], we define the similarity between the two nodes i and j as To adapt the method to directed networks, we set the popularity term to: Finally, we define the local attraction term as: where: .
Note that using this definition, we focus on the nodes that lie on a directed path of length two, starting at i and ending at j and vice versa. The lower the degree of these nodes, the more strongly i and j are attracted.
Similar to Algorithm 1, we introduce a weight map on the network, were each edge link (i, j) ∈ E is assigned the weight: Note that due to the asymmetry in the definition of π ij and η ij , we have that w ij = w ji in general. This weight definition assigns larger weights to nodes with low local attraction. The rationale is that nodes with high local attraction are likelier to belong to the same neighborhood and hence have high similarity. The resulting method is shown in Algorithm 2.

EXPERIMENTAL EVALUATION
To evaluate the proposed algorithms' performance, we perform several experiments on real network data. We start by assessing the effect of the horizon depth on the performance of our algorithms. We then compare their performance to topological similarity-based link prediction algorithms. In the remainder of this section, we will present the datasets and performance measures used in the evaluation procedure, followed by a presentation of the competing methods and finally a discussion of the obtained results.

Datasets
We use 23 real-life networks of various types and sizes for the experimental evaluation of the proposed algorithms. These networks are available through different public data repositories [37], [38], [39]. We assess the performance of the methods over a wide range of dataset types, including social, informational, linguistic, communicational, and biological networks. All used networks are directed with sizes 1: for each node i ∈ V do 2:κ in i ← the observed in-degree of node i, 3:κ out i ← the observed out-degree of node i, 4:κ i ←κ in i +κ out i , 5: end for 6: for each link (i, j) ∈ E do 7: π ij ← log(κ out i + 1) + log(κ in j + 1) log(κ out max + 1) + log(κ in max + 1) , 8: , 9: η out ij ← 1 − k∈Γ out i ∩Γ in j log(κ k + 2) log(κ max + 2) , 10:

Performance measures
We will use the three performance measures commonly encountered in the evaluation of link prediction algorithms: the area under the receiver operating curve (AUROC), the area under the precision-recall curve (AUPR), and topprecision (TPR). The AUROC, which can be computed as the probability that a false negative link is assigned a higher score than a true negative link, has long been the primary performance metric in link prediction literature [62]. However, due to the severe imbalance in link prediction datasets, especially in large spare networks, authors have recently realized its limitations in evaluating link prediction algorithms. Indeed, the AUROC tends to produce overlyoptimistic results due to the severe difference in magnitude between the negative and positive set sizes [5], [63], [64], [65], [66]. The AUPR remedies this by focusing only on the positive set, which is particularly useful in link prediction problems [67] [63].
TPR, also known as top-k precision [63], is computed by first sorting the negative links in decreasing order of the score and then taking the ratio of removed links among the top k ranked links. It is custom to choose k as the total number of removed edges, which means that a perfect link prediction algorithm will have a TPR equal to 1 [62], [63]. Similar to the AUPR, TPR avoids the pitfalls of the AUROC and has consequently been adopted as the primary performance metric for link prediction algorithms in recent years [5], [65], [66]. We will follow this practice in this paper and adopt TPR as the primary performance criterion, especially in large networks where its computation is much more efficient than the AUROC and the AUPR. Furthermore, we will use the average significant ranking procedure recently introduced in [5] to aggregate the performance results over multiple heterogeneous datasets. In this approach, we perform a two-tailed paired t-test to compare the mean performance results of each couple of algorithms on every dataset. If the statistical test reveals insignificance at the specified confidence level, the two algorithms are assigned the score of 0 for the corresponding network; otherwise, the algorithm with the higher performance is assigned the score of 1, and the other algorithm the score of -1. We then rank the algorithms based on the scores obtained for all networks, and in the case of a tie, we use the average rank. An algorithm's final aggregate performance measure is its average rank over all networks, with the convention that the lower the rank, the better. Because of the use of statistical significance tests, this procedure produces a more statistically robust comparison than simply ranking the algorithms as in [65], [66].

Competing methods
To assess the performance of the proposed algorithms, we compare them to the most widely used similarity methods. However, to carry a fair comparison, we adapt these methods to the directed network settings. In what follows, Index assigns more significant weight to neighbors with fewer neighbors. To handle the case of a directed network, we consider neighbors on a directed path of length two joining the two nodes of interest: • Directed Common Neighbors (DCNE): Common Neighbors simply counts the number of neighbors common to both nodes. In the directed case, we count only nodes lying on a directed path of length two, starting at the first node and ending at the second: • Directed Hub Depromoted Index (DHDI): Given a couple (i, j), the Hub Depromoted Index scales the number of common neighbors (Common Neighbors score) by the maximum between the degree of i and that of j, which discourages connections to nodes with high degrees, also known as hubs. In the directed case, we scale the DCNE score by the maximum between the out-degree of i and the in-degree of j: .

(15)
• Directed Hub Promoted Index (DHPI): Given a couple (i, j), the Hub Promoted Index scales the number of common neighbors by the minimum between the degree of i and that of j, which to the converse of the Hub Promoted Index encourages connections to hubs. In the directed case, and similar to DHDI, we scale the DCNE score by the minimum between the out-degree of i and the in-degree of j: .
• Directed Jaccard Index (DJID): Jaccard Index assigns higher scores to pairs of nodes that share a higher proportion of common neighbors relative to the number of non-shared neighbors. For a couple (i,j), the directed version we propose focuses on the out-neighbors of i and in-neighbors of j: • Directed Leicht-Holme-Newman Index (DLHN): Leicht-Holme-Newman Index scales the number of common neighbors by the product of the degrees of the two nodes. In the direct case, we scale the DCNE score of the couple (i, j) by the product of the out-degree of i and in-degree of j: • Directed Preferential Attachment Index (DPAT): The Preferential Attachment Index assigns a higher score to pairs of nodes if one or both have a high degree. In the directed network case, we focus on the out-degree of the first node and the in-degree node of the second: • Directed Salton Index (DSAI): Salton Index mimics the cosine similarity between the two nodes. In the directed network case, we focus on the in and out neighbors of the two nodes: • Directed Sorensen Index (DSOI): Sorensen Index scales the Common Neighbors score by the sum of the degrees of the two nodes, which in the case of a directed network translates to scaling by the sum of the outdegree of the first node and the in-degree of the second: (21)

Experimental results
Starting from a ground truth network, we randomly remove 10% of existing links to use as a test set and present the remaining 90% to the link prediction algorithm. The latter uses the observed links to assign a score to non-observed edges to discriminate between removed links (false negative links) and originally non-existing links (true negative links). We repeat this process 1000 times for small networks having less than 1000 nodes and 100 times for large networks with more than 1000 nodes and report the performance measures averaged over all trials. For small networks, we report all three performance measures: TPR, AUPR, and AUROC, whereas, for large networks, we report only TPR due to computational considerations.

Effect of the horizon depth limit
In this experiment, we measure the effect of the horizon depth limit on the performance of the algorithms. For this, we use nine small networks and vary the horizon limit h from 2 to 9. Since most complex networks have a small radius due to the small world property, going beyond depth 9 will have no noticeable effect on the results. Figure 1 shows the average rank over all networks using TPR, AUPR and AUROC for Algorithm 1, whereas Figure2 shows the corresponding results for Algorithm 2.
We can see that the horizon depth has a noticeable effect on AUROC in both algorithms, with the best depth being 5. The AUPR does improve with larger horizon depths in Algorithm 2 with 4 being the best depth. On the other hand, TPR does not improve with deeper horizons in both algorithms. Since we are adopting TPR as our primary performance measure, we will set the horizon depth limit to 2 in the remaining experiments, a value that has the additional advantage of reducing the algorithm's computational complexity in terms of space and time.

Comparison against other algorithms
In this experiment, we compare the proposed algorithms with the nine similarity-based link prediction algorithms presented in Section 5.3. We set the horizon depth limit to 2 as suggested in Section 5.4.1 and run all algorithms on two sets of networks: small networks and large networks. We use nine small networks having less than 1000 nodes on which we repeat the experiment 1000 times and report TPR, AUPR, and AUROC. We also use 14 large networks having more than 1000 nodes and up to 13,000 nodes. For each of these networks, we report TPR averaged over 100 trials. Tables 2, 3 and 4 respectively show the TPR, AUPR, and AUROC obtained on small networks. Table 5 shows the TPR results obtained on large networks. The results show that Algorithm 2 achieves the best overall rank in small networks using all three performance measures, particularly TPR. It produces significant performance improvement compared to the other algorithms in most networks. Algorithm 2 is followed by directed Adamic-Adard Index and then Algorithm 1. Compared to small networks, the superiority of Algorithm 2 is more pronounced in large networks, where it gives the best results in 12 networks out of 14. In large  networks, Algorithm 2 is followed in second position by directed Adamic-Adard Index, directed Common Neighbors, and then Algorithm 1.
To further assess the statistical significance of the obtained results, we perform a two-sample, one-tailed Mann-Whitney-Wilcoxon test of the average significant ranks of TPR obtained on large networks. We run the test for each pair of algorithms and report the results in Table 6. The upper triangle of the table contains the test p-values after adjustment using the Benjamini, Hochberg, and Yekutieli method. Results that are significant at 95% confidence level are shown in bold. The lower triangular part reports the comparison of the average significant rank between the algorithm in the row and the one in the column if significant at p-value =0.05. The results show that the superiority of Algorithm 6 over all other algorithms is statistically significant at a 95% confidence level.

CONCLUSION
Link prediction in complex networks aims to predict the future links that can form between nodes based on the currently observed connections. Link prediction is a problem with significant theoretical and practical value and has received increasing attention from the research community. The drive behind this interest is the need to analyze and predict the evolution of networked systems and deal with incomplete observations caused by the shortcomings typically encountered in the data collection process.
Due to the complexity and difficulty of the link prediction task, many prediction approaches have been proposed by researchers, particularly for undirected complex networks. However, not all real systems can be represented as undirected networks, and treating them as such inevitably results in information loss and, consequently, the degradation of the algorithms' predictive power. Despite the widespread of directed networks in real-life data, research effort in developing link prediction algorithms tailored to directed systems remains limited.
This paper introduced a novel approach to tackling the link prediction problem in directed networks. The proposed approach builds on the recent success of similaritypopularity methods in undirected networks. The presented algorithms are designed to handle and harness the asymmetry in node relationships by modeling it as asymmetry in similarity and popularity. Given the observed network topology, the algorithms estimate hidden similarities using shortest path distances based on an edge weight map designed to capture and factor out the asymmetry in node relations. An extensive experimental evaluation of the proposed approach demonstrates its effectiveness in predicting missing links in real-life networks of various types and sizes.
In future work, we propose to develop a network embedding framework tailored for directed networks based on the presented similarity-popularity link prediction method. Such embedding can be used for detecting spurious links and other network analysis tasks such as community and pattern detection.  [5] S. Kerrache, R. Alharbi, and H. Benhidour, "A scalable similaritypopularity link prediction method," Scientific reports, vol. 10, no. 1, pp. 6394-6394, 2020.
[7] X. Li and H. Chen, "Recommendation as link prediction: a graph kernel-based machine learning approach," in Proceedings of the 9th ACM/IEEE-CS joint conference on Digital libraries. ACM, 2009, pp.