# A Combinatory Framework for Link Prediction in Complex Networks
## 2 Related Work  
As mentioned before, the problem of link prediction is a well-known problem and there are many proposed algorithms in the literature. In this section, we present five of the most well-known and effective link prediction algorithms. Each of them relies on a different metric regarding the properties of network nodes and/or links to make link predictions, such as the information exchanged between the network nodes, the common neighbors, and the degree of the network nodes. From the experiments performed in Section 8, we observe that the yielded results are in some cases quite different, even for the same network. Our effort is in composing these results to obtain more reliable predictions. Resource Allocation Index[14]: The Resource Allocation Index expresses the fraction of information that a network node can send to another node, through their common neighbors. The Resource Allocation Index of nodes \(X\) and \(Y\) is defined as  
\[res\_alloc(X,Y)=\sum_{u\in N(X)\cap N(Y)}\frac{1}{|N(u)|}, \tag{1}\]  
where \(N(u)\) denotes the neighborhood of node \(u\). According to (1), the Resource Allocation Index of nodes \(X\), \(Y\) is the sum over the inverse of the node degree of all common neighbors of \(X\) and \(Y\), \((N(X)\cap N(Y))\). One may conclude that the more common neighbors that nodes \(X\) and \(Y\) have, the higher the value of this index will be. The value of the index grows even more if the common neighbors of \(X\) and \(Y\) have a small degree, i.e., they have few edges to other nodes. Adamic-Adar Index[15]: The Adamic-Adar Index is very similar to the Resource Allocation Index. The only difference is that rather than considering the degree of the common neighbors, the log of this degree is considered. The Adamic-Adar Index of nodes \(X\) and \(Y\) is defined as  
\[adamic\_adar(X,Y)=\sum_{u\in N(X)\cap N(Y)}\frac{1}{log(|N(u)|)}. \tag{2}\]  
Common Neighbor Centrality[16; 17; 18]: It computes the Common Neighbor and Centrality-based Parameterized Algorithm's (CCPA) score of all node pairs in the common neighborhood. The Common Neighbor and Centrality-based Parameterized Algorithm's score of nodes \(X\) and \(Y\) is defined as  
\[CCPA(X,Y)=a*(|N(X)\cap N(Y)|)+(1-a)*\frac{N}{d_{XY}}, \tag{3}\]  
where \(a\) is a parameter that varies in the range \([0,1]\), \(N\) denotes the total number of nodes in the network, and \(d_{XY}\) denotes the shortest distance between \(X\) and \(Y\). This algorithm is based on two vital properties of nodes, namely the number of common neighbors and their centrality [2]. Jaccard Coefficient[19; 20]: The Jaccard Coefficient takes into account the number of common neighbors of two nodes, normalizing it by the total number of their cumulative neighbors. Thus, the Jaccard coefficient of nodes \(X\) and \(Y\) is defined as  
\[jaccard\_coeff(X,Y)=\frac{|N(X)\cap N(Y)|}{|N(X)\cup N(Y)|}. \tag{4}\]  
Preferential Attachment[20; 21]: According to the Preferential Attachment rule, the nodes that have a very high degree are more likely to attract more neighbors in the future. The Preferential Attachment rule for nodes \(X\) and \(Y\) is defined as  
\[pref\_attach(X,Y)=|N(X)|*|N(Y)|. \tag{5}\]The intuition behind this measure is that if one looks at a pair of nodes and they both have a very high degree, they are more likely to be connected to each other in the future. The above approaches for link prediction are a small indicative subset of the vast relevant research. There are many different link prediction algorithms, owing to the different application objectives and underlying network topologies. There are link prediction algorithms for PPI [22] (protein-protein interaction) networks [23; 24; 25; 26], for social networks [3; 15; 27], for recommendation systems [28], etc. Our framework incorporates the results of the above link prediction algorithms and also employs a genetic algorithm approach.