Multilayer Graph Association Rules for Link Prediction

Abstract

Multiplex networks allow us to study a variety of complex systems where nodes connect to each other in multiple ways, for example friend, family, and co-worker relations in social networks. Link prediction is the branch of network analysis allowing us to forecast the future status of a network: which new connections are the most likely to appear in the future? In multilayer link prediction we also ask: in which layer? Because this last question is unanswerable with classical link prediction, here we investigate the use of graph association rules to inform multilayer link prediction. We derive such rules by identifying all frequent patterns in a network via multilayer graph mining, and then score each unobserved link's likelihood by finding the occurrences of each rule in the original network. Association rules add new abilities to multilayer link prediction: to predict new node arrivals, to consider higher order structures with four or more nodes, and to be memory efficient. In our experiments, we show that, exploiting graph association rules, we are able to achieve a prediction performance close to an ideal ensemble classifier. Further, we perform a case study on a signed multilayer network, showing how graph association rules can provide valuable insights to extend social balance theory.