a local algorithm for finding dense subgraphs
A local graph algorithm is one that searches for an approximation of the best solution near a specified starting vertex, and has a running time independent of the size of the graph. Recently, local algorithms have been developed for graph partitioning and clustering. In this paper, we present a local algorithm for finding dense subgraphs of bipartite graphs, according to the measure of density proposed by Kannan and Vinay. The algorithm takes as input a bipartite graph with a specified starting vertex, and attempts to find a dense subgraph near that vertex. We prove the following local approximation guarantee for the algorithm. For any subgraph S with k vertices and density ?, there is a large set of starting vertices within S for which the algorithm produces a subgraph with density ?(?/log ?), where ? is the maximum degree. The running time of the algorithm is O (? k 2 ), independent of the number of vertices in the graph.
local algorithms dense subgraphs spectral graph theory