Multilayer Graph Association Rules for Link Prediction

Authors

  • Michele Coscia IT University of Copenhagen, Copenhagen, Denmark
  • Michael Szell IT University of Copenhagen, Copenhagen, Denmark ISI Foundation, Turin, Italy

Keywords:

Social network analysis; communities identification; expertise and authority discovery, Qualitative and quantitative studies of social media

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.

Downloads

Published

2021-05-22

How to Cite

Coscia, M., & Szell, M. (2021). Multilayer Graph Association Rules for Link Prediction. Proceedings of the International AAAI Conference on Web and Social Media, 15(1), 129-139. Retrieved from https://ojs.aaai.org/index.php/ICWSM/article/view/18047