Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Julian_Robinson_MS_Thesis_Final.pdf (962.28 KB)

ETD Abstract Container

Abstract Header

The Use of Negative Sampling in the Evaluation of Link Prediction Algorithms

Robinson, Julian Everett
http://rave.ohiolink.edu/etdc/view?acc_num=case1662716551375378

Abstract Details

, Master of Sciences, Case Western Reserve University, EECS - Computer and Information Sciences.
Link prediction is a constantly growing field, but the evaluation of newly developed algorithms requires a lot of computational resources that can be prohibitively expensive to perform on large networks. To resolve this issue, a possible approach is to reduce the computational complexity by randomly sampling the negative edges. Here, we investigate the effect of negative sampling on the evaluation of link prediction algorithms, propose models to estimate the sampling error based on the number of negative edges sampled, and suggest minimum values bounding the error to a desired amount. Across a wide-array of real networks, we show that the suggested values can appropriately bound the error and can speed up the evaluation process ~1000x times for large networks having $10^6$ nodes with minimal error. We anticipate that these results and our estimated model can help researchers keep the evaluation of link prediction methods accessible on large, real-world networks.
Mehmet Koyuturk (Advisor)
Michael Lewicki (Committee Chair)
Soumya Ray (Committee Member)
Computer Science
Link Prediction; Negative Sampling;

Recommended Citations

Citations

  • Robinson, J. E. (n.d.). The Use of Negative Sampling in the Evaluation of Link Prediction Algorithms [Master's thesis, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1662716551375378

    APA Style (7th edition)

  • Robinson, Julian. The Use of Negative Sampling in the Evaluation of Link Prediction Algorithms. Case Western Reserve University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1662716551375378.

    MLA Style (8th edition)

  • Robinson, Julian. "The Use of Negative Sampling in the Evaluation of Link Prediction Algorithms." Master's thesis, Case Western Reserve University. Accessed APRIL 06, 2025. http://rave.ohiolink.edu/etdc/view?acc_num=case1662716551375378

    Chicago Manual of Style (17th edition)

case1662716551375378
162
© , all rights reserved.
This open access ETD is published by Case Western Reserve University School of Graduate Studies and OhioLINK.