| 摘要 | 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 bipartiteness 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(√θ). The running time of the algorithm is O(s2(Δ + logs)), where Δ is the maximum degree of G, independent of the size of G. © 2012 Springer-Verlag.; 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 bipartiteness 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(√θ). The running time of the algorithm is O(s2(Δ + logs)), where Δ is the maximum degree of G, independent of the size of G. © 2012 Springer-Verlag. |
修改评论