Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

The Learnability of Link Prediction and Recommendation Systems

David Choi

Given a subset of edges in a graph (for example, representing observed ties in a social network), the link prediction problem is to infer the presence of hidden edges representing unobserved or potential new relationships. In this talk, we examine previous efforts to apply classification algorithms from machine learning to link prediction. Learning theorems for classification can be adapted to the link prediction setting; however, the results take on a different nature in the new setting, and suggest performance limitations for link prediction on sparse graphs. The theoretical results are tested using the MovieLens data set, where predicted links represent product recommendations for consumers.

Problems with this site should be emailed to