Link Discovery through Iterative Link Classification: Towards a Real-Time Analysis of Graph Evolution

Abstract

In recent years, link prediction has been applied to a wide range of real-world applications which often generate massive dynamic networks that require an effective real-time approach to predicting the formation of future links. Traditionally, link prediction approaches utilize a single snapshot of a network to predict future links. However, real-world network data often evolves dynamically at a rapid pace by adding and removing links. Therefore, there is a need for a dynamic and online link prediction framework. This dissertation focuses on challenges and solutions with the aim of advancing a link prediction framework for use in real-time analytics.

For real-time link prediction, the framework should 1) be reliable and accurate, 2) maintain learning models, and 3) calculate node similarities in real time. In a real-world application that deals with time-varying networks, it is important to understand predictive models in a time-varying context. In this work, we develop several guidelines for using prediction models in a dynamic network. We also propose an incremental support vector machine method for link prediction, which updates the model using the latest data available as well as historical information.

While being able to forecast future links accurately is vital, another equally important problem is to identify the most important and relevant links among large numbers of future links. To address this problem, we propose a domain-independent, supervised method that predicts the rank of future links using objective interestingness measures.

We also propose an iterative link classification method, which updates the network using only predicted links with a high confidence level at each iteration. Using this method, we observed a significant improvement in accuracy and recall over the baseline link prediction method.

Our proposed solutions address two out of the three requirements defined above, by focusing on maintaining the learning models and increasing the reliability and accuracy of link prediction in a dynamic network. In our future work, we plan to extend this research to address the final requirement by developing the approximation algorithms for computing similarity measures in large dynamic and streaming networks, in real time, using distributed computing frameworks.