University of Notre Dame
Browse
LichtenwalterRN032012D.pdf (1.82 MB)

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

Download (1.82 MB)
thesis
posted on 2012-03-13, 00:00 authored by Ryan N. Lichtenwalter
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.

History

Date Modified

2017-06-02

Defense Date

2012-03-05

Research Director(s)

Nitesh V. Chawla

Committee Members

David S. Hachen Jr. Zoltan Toroczkai Douglas Thain

Degree

  • Doctor of Philosophy

Degree Level

  • Doctoral Dissertation

Language

  • English

Alternate Identifier

etd-03132012-161556

Publisher

University of Notre Dame

Program Name

  • Computer Science and Engineering

Usage metrics

    Dissertations

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC