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

Doctoral Dissertation

Abstract

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.

Attributes

Attribute NameValues
URN
  • 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 PhD
Defense Date
  • 2012-03-05

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

Subject
  • link analysis

  • data mining

  • link prediction

  • networks

  • graph theory

  • classification

Publisher
  • University of Notre Dame

Language
  • English

Record Visibility and Access Public
Content License
  • All rights reserved

Departments and Units

Files

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.