高密度部分ハイパーグラフのための新しい動的アルゴリズム【JST・京大機械翻訳】

Bera Suman K.; Bhattacharya Sayan; Choudhari Jayesh; Ghosh Prantar

プレプリント

J-GLOBAL ID：202202213981196269 整理番号：22P0333394

高密度部分ハイパーグラフのための新しい動的アルゴリズム【JST・京大機械翻訳】

A New Dynamic Algorithm for Densest Subhypergraphs

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (4件)： , , ,
資料名：
発行年： 2022年04月17日プレプリントサーバーでの情報更新日： 2022年04月17日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

高密度部分グラフの計算は,ソーシャルネットワークにおける電子商取引からコミュニティ検出までの多様なアプリケーションを持つグラフマイニングにおける基本的問題である。これらのアプリケーションの多くにおいて,基礎となるコンテキストは,時間とともに進化する重み付きハイパーグラフとして,より良くモデル化される。これは,入力が更新のシーケンス(ハイパーエッジ挿入/欠失)を介して変化するので,{em動的設定}における重み付きハイパーグラフの最密サブハイパーグラフを維持する問題を動機づける。以前に,この問題に対する唯一の既知アルゴリズムは,Hu et al.[HWC17]によるものであった。このアルゴリズムは,非加重ハイパーグラフのみに動作し,(1+ε)r ̄2の近似比とO(ポリ(r,logn)の更新時間)を持ち,ここで,rは,すべての更新を通して入力の最大ランクを示した。入力ハイパーグラフが重み付けされた場合でも,この問題に対する新しいアルゴリズムを得た。著者らのアルゴリズムは,rに無関係である(1+ε)とO(poly(r,logn)の類似の更新時間)のかなり改善された(近最適)近似比を有した。それは,加重単純グラフの特殊ケースに対してさえ,第一(1+ε)近似アルゴリズムである。理論解析を補完するために,大規模,実世界データセットに関する動的アルゴリズムによる実験を行った。著者らのアルゴリズムは,精度と効率の両方に関して,最先端の[HWC17]の状態を凌駕する。【JST・京大機械翻訳】

, , , , , , ,
, , , , , , , 【Automatic Indexing@JST】

グラフ理論基礎

前のページに戻る