# A Combinatory Framework for Link Prediction in Complex Networks
## 6 Theoretical Analysis  
In the literature, there are several link prediction algorithms [14; 15; 16; 17; 18; 19; 20; 21] which, depending on the type of network applied, exhibit different performance. We use appropriate metrics to evaluate these results. One of the most well-known and effective metrics is Precision [32], which is defined as follows:  
\[Precision=\frac{TP}{TP+FP} \tag{8}\]  
where \(TP\) stands for True Positive and \(FP\) stands for False Positive. The values of this metric range between 0 and 1. It is clear that the higher the Precision value a prediction algorithm gives, the more suitable it is for the network to which it is applied. From the Precision we can define the top \(K\) predictive rate [32]. The top \(K\) predictive rate is the percentage of correctly classified positive samples among the top \(K\) instances in the ranking produced by a link predictor \(P\). We denote the top \(K\) predictive rate as \(TPR_{K}\), where \(K\) is a definable threshold. In the following, when we refer to Precision, we will mean the \(TPR_{K}\) with a well-defined \(K\). To find the Precision of a predictor \(P\) in a network, we work as follows. First, we randomly remove \(K\) edges from the network and store them in a set, denoted as \(removed\_E\). The \(K\) threshold comes from a percentage of the number of edges in the network, usually more than 1000 and less than half the number of edges in the network so as not to spoil the original network's structure. In the experiments we have performed, the number of edges of the networks we have used is over 5000 and we removed a small percentage of them (between 5% and 30%). If \(G=(V,E)\) is the initial graph, then the resulting graph is  
\[G^{\prime}=(V,E^{\prime}),E^{\prime}=E-removed\_E. \tag{9}\]  
Let \(E^{\prime\prime}\) be the set of edges where they do not belong to \(G^{\prime}\), that is,  
\[E^{\prime\prime}=(u,v):u,v\in V,(u,v)\
otin E^{\prime}, \tag{10}\]  
and let \(Eval\_Set=P(E^{\prime\prime})\), where \(P(E^{\prime\prime})\) is a tuple \((u,v,value):(u,v)\in E^{\prime\prime}\) and \(value\) the \(P\) evaluation value for the edge \((u,v)\), where \(value\in\mathbb{R}\). Thus, if we have \(P_{1},P_{2},\ldots,P_{n}\), we can order them according their \(TPR_{K}\), where \(P_{i}>P_{j}\) if \(TPR_{Ki}>TPR_{kj}\), for \(0<i,j\leq n\). Let \(Eval\_Set\_sorted\) be the \(Eval\_Set\) in descending order by \(value\). From the definition of \(TPR_{K}\), it is clear that the more edges that are actually missing in the first \(K\) edges of an \(Eval\_Set\_sorted\), the better the Predictor \(P\) that generated it. Therefore, if we want to have a worthwhile Predictor that will make good predictions, this Predictor should give \(Eval\_Set\_sorted\), where its first \(K\) elements contain as many missing edges as possible. But we can also think the other way around. We can construct in an organized way, and using the \(Eval\_Set\_sorted\) sets of Predictors that we already have, a new \(Eval\_Set\_sorted\) set that contains in its first \(K\) elements more edges that are truly missing and thus a larger \(TPR_{K}\) than all the rest of the \(Eval\_Set\_sorted\) sets. We can construct a better \(Eval\_Set\_sorted\) if we improve every value of the tuples of which it consists. The improvement will come from the corresponding values of the \(Eval\_Set\_sorted\) sets for each missing network edge. This problem is an optimization problem and can be formulated as follows. If we have \(P_{1},P_{2},\ldots,P_{n}\) Predictor algorithms which we have applied to \(G^{\prime}\) and these Predictors have constructed \(n\ Eval\_Set\_sorted\) sets, is there a weight vector \(w^{T}=[w_{1},w_{2},\ldots,w_{n}],w_{i}\in[0,1]\) such that for every missing edge value of these sets, a new missing edge value is created and all these new values and corresponding missing edges result in a \(Eval\_Set\_sorted\) with larger \(TPR_{K}\)?