Link Prediction using Network based Inference - A quick matrix based implementation

I explored a paper proposed by Zhou etal used Network based Inference(NBI) method to predict missing links in bipartite network and was thinking a lot how to implement using some simple matrix ways. I have taken the pic below from Zhou paper above  to explain the idea .Given the bipartite graph , a two phase resource transfer Information from  X(x,y,z) set of nodes gets distributed to Y set of nodes and then again goes back to resource X .  This process allows us to define a technique for the calculation of the weight matrix W.  In 2010 a modified version of this approach is proposed in Solving the apparent diversity-accuracy dilemma of recommender systems which used a modified Hybrid algorithm in which the functions defined in NBI and HeatS are combined in connection with a parameter called λ.

In this post i am going to implement the algorithm how does this work using simple matrix method in R. Interested readers must see those publications for the mathematical equations explained. Before going a bit further , if we are given a weight matrix W( which is calculated using the algorithms above) and the adjacency matrix A of the bipartite network, it is possible to compute the recommendation matrix R using the equation below, where W is n x n matrix and A is n x m matrix .

                                                                               R = W.A      (1)

The R list is then sorted in a descending order with respect to the score.

We use this kind of calculations in chemo-genomics predictions and also other bipartite type data. When doing Drug target prediction we can use W is as the sequence similarity matrix and A as the Drug target adjacency matrix to obtain recommendation of targets based on sequence similarity . Similarity W can be a compound similarity matrix and A the bipartite compound target matrix. Now we can use equation (1) above to get recommendations of compounds given a sequence of interest. This trick of using matrix just blowed my mind off !! Isn't it cool ?

Now for the functions here it goes below. If you are using the codes do let me know the results how does it work. My next post would be integrating similarity matrices information along with the degree information into W.

Link Prediction using Bipartite Networks .

Missing link prediction of networks is  of practical significance in modern science like in Social Networks , Biological Networks and Food networks and lots others. Adamic-Adar  index refines the simple counting of common neighbors by assigning the lower connected neighbors more weights which is given by the equation below. More on the other indexes are ,

1 . Link Prediction in Complex Networks

2 . Predicting missing links via local information

3.  Link prediction problem in social networks

∑w∈Γ(u)∩Γ(v)1log|Γ(w)|  

The code takes a bipartite graph as input (stored as a text file in an adjacency list) and computes the Adamic/Adar similarity of each non-neighboring node pair. The similarity is computed using the degree of the intermediate nodes. The output file is written as a text file containing three fields per row score , Proteins and Drugs. However this can be applied to other bipartite networks also.

After calculation the predicted links are stored in an output file and the highest predicted links can be obtained by sorting the first column. The Bipartite data (inputdata.txt) and code is avialable at Git.