Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


26825.pdf (8.84 MB)

ETD Abstract Container

Abstract Header

A Framework of Transforming Vertex Deletion Algorithm to Edge Deletion Algorithm

Wang, Nan
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1504878748832156

Abstract Details

2017, PhD, University of Cincinnati, Engineering and Applied Science: Computer Science and Engineering.
Graph vertex and edge deletion algorithms are normally studied separately. We develop a framework to link them by transferring any existing vertex deletion algorithms to a set of new edge deletion algorithms. It is done by creating new measure for each edge in the view its endpoints, vertices. Each vertex measures its incident edges in its neighborhood graph by using a chosen vertex deletion algorithm. If a vertex is deleted in the neighborhood graph, the edge between the vertex and the host vertex is marked removable. At the end, each edge is marked twice for its removability by its two endpoints. An edge measure function combines those two removability marks and creates a new measure for each edge. A new edge deletion algorithm is created by deleting edges from the original graph basing on the newly generated edge measures. We extend above concept and operations recursively into neighborhood graphs. It makes the framework a recursive process. We further study a series of stopping criteria for the recursion process. Eventually, the framework is expressed as a recursive algorithm with parameters of edge measure function and stopping criteria. By changing those parameters, the framework can transfer a vertex deletion algorithm to multiple edge deletion algorithms. This creates the flexibility for different research purposes. As examples, we apply the framework to a few vertex deletion algorithms and generate a few sets of edge deletion algorithms. Some resulting edge deletion algorithms prove to be very efficient community discovery algorithms, especially, with the vertex deletion algorithm that is proposed by this research. We call the algorithm Follow the Crowd. We thoroughly study the performance of its generated edge deletion algorithms as community discovery algorithms.
Yizong Cheng, Ph.D. (Committee Chair)
Fred Annexstein, Ph.D. (Committee Member)
Chia Han, Ph.D. (Committee Member)
Wen-Ben Jone, Ph.D. (Committee Member)
Anca Ralescu, Ph.D. (Committee Member)
159 p.
Computer Science
Graph; Vetex Deletion; Edge Deletion; Neighborhood; Graph Clustering; Graph Sparsification

Recommended Citations

Citations

  • Wang, N. (2017). A Framework of Transforming Vertex Deletion Algorithm to Edge Deletion Algorithm [Doctoral dissertation, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1504878748832156

    APA Style (7th edition)

  • Wang, Nan. A Framework of Transforming Vertex Deletion Algorithm to Edge Deletion Algorithm. 2017. University of Cincinnati, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1504878748832156.

    MLA Style (8th edition)

  • Wang, Nan. "A Framework of Transforming Vertex Deletion Algorithm to Edge Deletion Algorithm." Doctoral dissertation, University of Cincinnati, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1504878748832156

    Chicago Manual of Style (17th edition)

ucin1504878748832156
269
© 2017, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.