Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


thesis.pdf (330.08 KB)

ETD Abstract Container

Abstract Header

Hub-Network for Distance Computation in Large Social Networks

You, Bo
http://rave.ohiolink.edu/etdc/view?acc_num=kent1412601464

Abstract Details

2014, MS, Kent State University, College of Arts and Sciences / Department of Computer Science.
In this thesis, we study a new approach to accelerate shortest path queries in large social networks. Shortest path computation is one of the most fundamental operations for managing and analyzing large social networks. Existing techniques are mainly aimed at large but sparse road networks, so they are not effective to handle social networks, which have quite different characteristics: non-spatial, non-weighted, scale-free and exhibiting small-world properties. The most distinct feature is the existence of core hubs, making shortest path computation surprisingly challenging. Specifically, we introduce a novel technique centered around hubs, referred to as the Hub-Accelerator framework, to compute the k-degree shortest path (finding the shortest path between two vertices if their distance is within k). This technique enable us to significantly reduce the search space by greatly limiting the expansion scope of hubs (using the novel distance-preserving Hub-Network concept). Experimental evaluation demonstrates that our approach is more effective than state-of-the-art exact and approximate shortest path methods.
Ruoming Jin (Advisor)
Feodor Dragan (Committee Member)
L. Gwenn Volkert (Committee Member)
62 p.
Computer Science

Recommended Citations

Citations

  • You, B. (2014). Hub-Network for Distance Computation in Large Social Networks [Master's thesis, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1412601464

    APA Style (7th edition)

  • You, Bo. Hub-Network for Distance Computation in Large Social Networks. 2014. Kent State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=kent1412601464.

    MLA Style (8th edition)

  • You, Bo. "Hub-Network for Distance Computation in Large Social Networks." Master's thesis, Kent State University, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=kent1412601464

    Chicago Manual of Style (17th edition)

kent1412601464
410
© 2014, some rights reserved.Creative Commons License Hub-Network for Distance Computation in Large Social Networks by Bo You is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by Kent State University and OhioLINK.