Network Analysis and Link Prediction: Effective and Meaningful Modeling and Evaluation

Link prediction is succinctly stated as identifying unobserved links in a network. It has important applications ranging from recommending beneficial relationships in social networks to discovering new protein-protein interactions in biological networks. This dissertation primarily focuses on link prediction in homogeneous, single-relational networks, but it also introduces new techniques for handling multi-relational networks. We identify what we view as the three principal components of effective link prediction: high-performance algorithms and methods, proper evaluation, and computational scalability. Performance is the natural requirement that the predictive models provide usably correct outputs. Evaluation is the surprisingly difficult question of how to determine the correctness of a model in order to compare models and develop an expectation of effectiveness in real deployment. Computational scalability is necessary to obtain output from a link prediction framework in a reasonable amount of time on large networks. Each of these three components poses significant challenges, and it is reasonable to say that any of these challenges individually can stand in the way of the proliferation of link prediction techniques for useful research and domain applications.