中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 软件研究所
  3. 软件所图书馆
  4. 会议论文
a local algorithm for finding dense bipartite-like subgraphs

文献类型：会议论文

作者Peng Pan
出版日期2012
会议名称18th Annual International Computing and Combinatorics Conference, COCOON 2012
会议日期August 20, 2012 - August 22, 2012
会议地点Sydney, NSW, Australia
关键词Combinatorial mathematics
页码145-156
中文摘要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.
收录类别EI
会议主办者Google; National ICT Australia
会议录Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
语种英语
ISSN号0302-9743
源URL[http://ir.iscas.ac.cn/handle/311060/15758]  
专题软件研究所_软件所图书馆_会议论文
推荐引用方式
GB/T 7714		 Peng Pan. a local algorithm for finding dense bipartite-like subgraphs[C]. 见:18th Annual International Computing and Combinatorics Conference, COCOON 2012. Sydney, NSW, Australia. August 20, 2012 - August 22, 2012.

入库方式： OAI收割

来源：软件研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。