A Local Algorithm for Finding Dense Bipartite-Like Subgraphs

摘要

We give a local algorithm to extract dense bipartite-like subgraphs which characterize cyber-communities in the Web [13]. We use the bipartiteness ratio of a set as the quality measure that was introduced by Trevisan [20]. Our algorithm, denoted as FindDenseBipartite(v, s,θ), takes as input a starting vertex v, a volume target s and a bipartite-ness ratio parameter θ and outputs an induced subgraph of G. It is guaranteed to have the following approximation performance: for any subgraph S with bipartiteness ratio θ, there exists a subset S_θ (⊂) S such that vol(S_θ) ≥ vol(S)/9 and that if the starting vertex v ∈ S_θ and s ≥ vol(S), the algorithm FindDenseBipartite(v, s,θ) outputs a subgraph (X,Y) with bipartiteness ratio O(1/2 θ). The running time of the algorithm is O(s~2(Δ + log s)), where Δ is the maximum degree of G, independent of the size of G.