a local algorithm for finding dense bipartite-like subgraphs

ISCAS OpenIR

	a local algorithm for finding dense bipartite-like subgraphs
	Peng Pan
	2012
Conference Name	18th Annual International Computing and Combinatorics Conference, COCOON 2012
Source	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages	145-156
Conference Date	August 20, 2012 - August 22, 2012
Conference Place	Sydney, NSW, Australia
Indexed Type	EI
ISSN	0302-9743
Department	(1) State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences China; (2) School of Information Science and Engineering Graduate University of China Academy of Sciences China
English Abstract	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(s²(Δ + 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(s²(Δ + logs)), where Δ is the maximum degree of G, independent of the size of G. © 2012 Springer-Verlag.
Keyword	Combinatorial Mathematics
Sponsorship	Google; National ICT Australia
Language	英语
Content Type	会议论文
URI	http://ir.iscas.ac.cn/handle/311060/15758
Collection	中国科学院软件研究所
Recommended Citation GB/T 7714	Peng Pan. a local algorithm for finding dense bipartite-like subgraphs[C],2012:145-156.

Files in This Item:
There are no files associated with this item.

If you have any objections to this item, please fill out the form below and the administrator will contact you as soon as possible.
Content:
Email：	*
Institution:
Verification Code:	Refresh

Any comments and suggestions are welcomed.
Title:	*
Content:
Email：	*
Verification Code:	Refresh

中国科学院软件研究所机构知识库