Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


20999.pdf (4.41 MB)

ETD Abstract Container

Abstract Header

Link Prediction in Time-Evolving Graphs

Mendu, Prasad Reddy
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470757663

Abstract Details

2016, MS, University of Cincinnati, Engineering and Applied Science: Computer Science.
With the increase in number of social networks and technological advancements in the last two decades, there is vast amount of digital communication happening between people. Most of these communication networks evolve with time and can be represented in the form of graphs. Link Prediction is finding edges that may appear in the future in the network using the current data in the network. Link prediction finds many applications such as “Recommender systems” in social networks like Facebook, Twitter, LinkedIn etc. Link prediction is a vast area and many link prediction algorithms exist today each catering to its specific purpose. Some of these algorithms deal with the problem of link prediction in Time-evolving graphs and they have comparatively better performance than a random predictor. However, their raw performance, when considered by itself, can still be improved. In our work, we aim to develop an algorithm that not only has comparatively better performance than the random predictor, but also to have very good raw performance. In this work, the main idea for link prediction is to take into account the past data along with the current data to predict the edges to be formed in the future. To do this, we calculate the conditional probability of two nodes having an edge between them in the future given they have certain feature value. Proximity measures are taken as features between the nodes, and they are calculated for every possible edge. Bayesian inference is used to calculate the posterior probability of an edge to occur in the future, given we have current and past data. Past data is used to calculate Prior probability of edges. We also experimented with the way Prior probability of an edge is computed by changing the way in which it is computed currently, and observed the algorithm’s behavior with this version of Prior probability. Using this methodology, our algorithm is tested against different types of datasets and the relevancy measures such as precision, recall, and specificity are calculated to evaluate the performance of link prediction algorithm. A detailed analysis of the results confirms that the proposed link prediction algorithm performs better than the existing algorithms with significantly improved precision and recall values. Our algorithm is also tested by using an alternative second method to calculate the Prior probability of an edge and interestingly, it showed that even though the performance of our first proposed method is better than this, the second version has better precision and recall values than some of the existing algorithms.
Raj Bhatnagar, Ph.D. (Committee Chair)
Nan Niu, Ph.D. (Committee Member)
Yizong Cheng, Ph.D. (Committee Member)
142 p.
Computer Science
link prediction; graphs; time-evolving

Recommended Citations

Citations

  • Mendu, P. R. (2016). Link Prediction in Time-Evolving Graphs [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470757663

    APA Style (7th edition)

  • Mendu, Prasad Reddy. Link Prediction in Time-Evolving Graphs. 2016. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470757663.

    MLA Style (8th edition)

  • Mendu, Prasad Reddy. "Link Prediction in Time-Evolving Graphs." Master's thesis, University of Cincinnati, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470757663

    Chicago Manual of Style (17th edition)

ucin1470757663
418
© 2016, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.