A Framework of Transforming Vertex Deletion Algorithm to Edge Deletion Algorith

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.