Link prediction in social graph databases

Abstract

The graph structure is widely researched due to its significance in various areas. The topology of such graphs offers a basis of pattern and knowledge extraction by using various mining algorithms. Domains like social activity, continued to give rise to the popularity of graphs, especially in the field of predictive analysis. The dynamic nature of social graphs motivated various researchers to anticipate the evolution of these networks through time. Predicting the likelihood of social interactions formulating at a future time period is based on the Link Prediction Problem. Realizing these links, help to discover future and hidden activities which are very useful for different sectors. A selection of social activities and interactions are not only dynamic, but their strength and reach evolve over time too. Due to this, a number of studies suggest that considering time as an additional dimension improves the results obtained in link prediction. This study evaluates the effect of this consideration by comparing results obtained from static methods with those returned from temporal methods. A supervised binary classification technique is used on three different social datasets with features describing popular graph metrics representing the similarities and proximities between nodes. This study also proposes and implements a method to assign time-based weights which describe the activeness of the network nodes based on how recent their adjacent interactions are. Various performance measures such as accuracy, precision, and recall are used to aid with the comparative analysis of the results. The results of this study show that the consideration of time-based aspects helps improve the link predictions. The Katz metric yielded the best performance when compared to the other graph metrics. This result on one of the datasets managed to correctly classify seventeen additional links when the time-based method is used.