Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Dissertation_Yubao_160112.pdf (5.73 MB)

ETD Abstract Container

Abstract Header

Efficient and Effective Local Algorithms for Analyzing Massive Graphs

Wu, Yubao
http://rave.ohiolink.edu/etdc/view?acc_num=case1454451336

Abstract Details

2016, Doctor of Philosophy, Case Western Reserve University, EECS - Computer and Information Sciences.
Graph is a ubiquitous data structure that can model many real-world problems. There are several important problems in graph analysis, such as ranking, community detection and densest subgraph detection. The global versions of these problems have been extensively studied. Recently, the graphs are becoming larger and larger and may contain billions of nodes. The large scale of graphs makes it prohibitive to apply the existing global algorithms. In many circumstances, the entire graph is unavailable, such as the Twitter social network. On the other hand, in many applications, the user is only interested in the local patterns. Thus, the local versions of these problems and algorithms have attracted intense research interests. Ideally, the local algorithms are preferred for solving these problems efficiently without searching the entire graph. In this dissertation, we focus on the local pattern mining problems and related local search algorithms. We study the top-k proximity query problem, the local community detection problem, and the densest connected subgraph problem in dual networks. For the top-k proximity query problem, we devise an efficient and unified local search algorithm, which can be applied for a variety of random walk based proximity measures. For the local community detection problem, we discover that the existing local community detection methods suffer from a serious free rider effect, and develop the query biased node weighting scheme to mitigate the free rider effect. The densest connected subgraph problem is motivated from real applications and is a natural extension of the densest subgraph problem from a single network to dual networks. For each problem, we perform comprehensive experiments to evaluate the effectiveness and efficiency of the proposed method on large real and synthetic networks. The results demonstrate that, for each problem, the proposed method outperforms the state-of-the-art methods in terms of effectiveness and efficiency.
Xiang Zhang (Advisor)
Zhu Xiaofeng (Committee Member)
Li Jing (Committee Member)
Meral Ozsoyoglu (Committee Member)
201 p.
Bioinformatics; Computer Science
community detection; random walk; top-k query; densest subgraph; dual networks

Recommended Citations

Citations

  • Wu, Y. (2016). Efficient and Effective Local Algorithms for Analyzing Massive Graphs [Doctoral dissertation, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1454451336

    APA Style (7th edition)

  • Wu, Yubao. Efficient and Effective Local Algorithms for Analyzing Massive Graphs. 2016. Case Western Reserve University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1454451336.

    MLA Style (8th edition)

  • Wu, Yubao. "Efficient and Effective Local Algorithms for Analyzing Massive Graphs." Doctoral dissertation, Case Western Reserve University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=case1454451336

    Chicago Manual of Style (17th edition)

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