Temporal probabilistic measure for link prediction in collaborative networks

摘要

Link prediction addresses the problem of finding potential links that may form in the future. Existing state of art techniques exploit network topology for computing probability of future link formation. We are interested in using Graphical models for link prediction. Graphical models use higher order topological information underlying a graph for computing Co-occurrence probability of the nodes pertaining to missing links. Time information associated with the links plays a major role in future link formation. There have been a few measures like Time-score, Link-score and T_Flow, which utilize temporal information for link prediction. In this work, Time-score is innovatively incorporated into the graphical model framework, yielding a novel measure called Temporal Co-occurrence Probability (TCOP) for link prediction. The new measure is evaluated on four standard benchmark data sets : DBLP, Condmat, HiePh-collab and HiePh-cite network. In the case of DBLP network, TCOP improves AUROC by 12 % over neighborhood based measures and 5 % over existing temporal measures. Further, when combined in a supervised framework, TCOP gives 93 % accuracy. In the case of three other networks, TCOP achieves a significant improvement of 5 % on an average over existing temporal measures and an average of 9 % improvement over neighborhood based measures. We suggest an extension to link prediction problem called Long-term link prediction, and carry out a preliminary investigation. We find TCOP proves to be effective for long-term link prediction.