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

Doctoral Dissertation


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.


Attribute NameValues
  • etd-03132012-161556

Author Ryan N. Lichtenwalter
Advisor Nitesh V. Chawla
Contributor Nitesh V. Chawla, Committee Chair
Contributor David S. Hachen Jr., Committee Member
Contributor Zoltan Toroczkai, Committee Member
Contributor Douglas Thain, Committee Member
Degree Level Doctoral Dissertation
Degree Discipline Computer Science and Engineering
Degree Name Doctor of Philosophy
Defense Date
  • 2012-03-05

Submission Date 2012-03-13
  • United States of America

  • link analysis

  • data mining

  • link prediction

  • networks

  • graph theory

  • classification

  • University of Notre Dame

  • English

Record Visibility Public
Content License
  • All rights reserved

Departments and Units

Digital Object Identifier


This DOI is the best way to cite this doctoral dissertation.


Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.