# A Combinatory Framework for Link Prediction in Complex Networks
## 7 Evaluation Process
### Evaluation of Basic Algorithms  
In each graph corresponding to the sets of edges train_set and test_set, we apply the five basic link prediction algorithms we use. The application and evaluation of each basic algorithm for each graph is carried out with code that we have written. In a graph and for each edge missing from it, we apply a basic algorithm, which returns for this edge its estimate, which is a real number. We store all estimates for all edges (along with the edge for each estimate) in an evaluation list and then sort this evaluation list in descending order of the basic algorithm's estimate. Then we use the omissible_edge_set corresponding to the graph we are considering. The evaluation of the basic algorithm we implemented results from how many edges in the first len(omissible_edge_set) or |omissible_edge_set| positions of the evaluation list are actually contained in the omissible_edge_set. The more edges the evaluation list contains than those that are really missing in its first len(omissible_edge_set) positions, the more effective is the estimation that the algorithm gives us for an edge that does not exist in the graph.  
For example, if 500 edges are missing (i.e., we have previously removed) from a graph and a basic algorithm manages to have 350 of them in the first 500 positions of its evaluation list, then we can conclude how correct of estimates it can make for edges that do not exist in the graph and may be added in the future. In our tests, this score is the point of comparison of the effectiveness of the basic algorithms we use and of the new enhanced predictor tool of the framework we propose and results from their composition. As a consequence of all the above, the higher the score of an algorithm, the more effective it is in the specific network graph.  
From the above method of evaluating an algorithm, the value of a well-known metric evaluation, which is Precision [32], is derived. Precision is defined as the ratio of the true positive item to the sum of true positive and false positive selected items:\[Precision=\frac{TruePositives}{TruePositives+FalsePositives}. \tag{17}\]  
Corresponding to the previous ones, the true positives are the edges that the algorithm found and are really missing from the graph, while the denominator corresponds to the number of edges that we have actually removed from the graph before.  
Another standard that we have measured and reported in our experiments is the Area Under the Curve (AUC) [32]. For link prediction, AUC can be interpreted as the probability that a randomly selected missing edge gives a higher score than a randomly selected nonexistent edge. In this work, at each time we randomly pick an existing edge and a non-existing edge to compare their scores, if among \(n\) independent comparisons, there are \(n_{1}\) times that the existing edge has a higher score and \(n_{2}\) times that they have the same or lower score, the AUC value is  
\[AUC=\frac{n_{1}+0.5n_{2}}{n}. \tag{18}\]  
If all the scores are from independent and identical distributions, then the AUC should be approximately 0.5. Therefore, the degree to which AUC exceeds 0.5 indicates that link prediction is much better than random selection. In our work, we have taken AUC measurements with \(n=1000\).