A Framework for Predicting Links Between Indirectly Interacting Nodes

Link prediction is the problem of inferring new relationships among nodes in a network that are likely to occur in the near future. Classical approaches mainly consider neighborhood structure similarity when linking nodes. However, we may also want to take into account if the two nodes are already indirectly interacting and if they will benefit from the link by having an active interaction over the time. For instance, it is better to link two nodes u and v if we know that these two nodes will interact in the social network even in the future, rather than suggesting v', who will never interact with u .

In this paper, we deal with a new variant of the link prediction problem: given a pair of indirectly interacting nodes, predict whether or not they will form a link in the future. We propose a solution to this problem that leverages the predicted duration of their interaction and propose two supervised learning approaches to predict how long will two nodes interact in a network. Given a set of network-based predictors, the basic approach consists of learning a binary classifier to predict whether or not an observed indirect interaction will last in the future. The second and more fine-grained approach consists of estimating how long the interaction will last by modeling the problem via survival analysis or as a regression task. Once the duration is estimated, new links are predicted according to their descending order. Experimental results on the Facebook Network and Wall Interaction dataset show that our more fine-grained approach performs the best with an AUROC of 0.85 and clearly beats a link prediction model that does not consider the interaction duration and is based only on network properties.