このグラフには、3つのkコアがあります。C1としてマークされた3コア、C2としてマークされた2コア、および1コアであり、グラフ全体に対応し、C3としてマークされています。1.6(8つのエッジと5つの頂点を含む)を有する。言い換えれば、C1は内部コアであるにもかかわらずC2よりも密度が低い。図1に示すG2(画像は略)について考えてみましょう。このグラフには、単一のコア、つまり2コアがあり、グラフ全体が含まれています。1.4を与え、これは唯一のコアの密度よりも高い。この例では、より密度の高い代替のグラフ分解を定義するよう動機づけています。このグラフような分解を局所的分解と呼びます。私たちは次を満たすような分解に興味があります。(i)内側サブグラフの密度が外側サブグラフの密度よりも高く、(ii)最も内側のサブグラフは最も細いサブグラフに対応し、(iii)分解を効率的に計算または近似することができる。局所的に密集した部分グラフを定義することで目標を達成します。本質的には、頂点を追加したり削除して密度を上げることはできません。これらの部分グラフは、外側の部分グラフに行くにつれて密度が減少し、最も内側の部分グラフが実際には最も細い部分グラフであるような階層に配置されることを示す。この階層を発見するための2つの効率的なアルゴリズムを提供します。[15]によって与えられた最も密なサブグラフを発見するための正確なアルゴリズムを拡張する。このアルゴリズムは、パラメータαに依存する特定のグラフ上の最小カット問題を解くことに基づいている。Goldbergは、ある値α(バイナリサーチで見つかる)に対して、最小カットは最も細いサブグラフを回復することを示した。我々の貢献の1つは、ゴールドバーグのアルゴリズムをより明らかにし、同様の構成がαを変化させることによってすべての局所的に密な部分グラフを発見することを可能にすることである。我々の第2のアルゴリズムは、密集した部分グラフを近似するためのCharikarによる線形時間アルゴリズムを拡張する[13]。このアルゴリズムは、最初に最小次数の頂点を繰り返し削除することによって頂点を順序付けし、次にその順序を考慮して最も細いサブグラフを選択する。この考え方は、同じ順序を使用して、順序を考慮した最初の最も細いサブグラフを見つけ、最初のサブグラフを含む2番目に細かいサブグラフを繰り返し検索するなどして拡張します。このアルゴリズムは線形時間で実行可能であり、第2因子近似保証を達成することを示す。Charikarのアルゴリズムとk-core分解を発見するためのアルゴリズムは非常に似ています。それらは両方とも、最小次数の頂点を削除することによって頂点を順序付けます。この接続が深いことを示し、k-core分解が局所的に密な分解のための第2因子近似を提供することを示す。実際にはk-coreは局所的に密なサブグラフとは構造が異なり、k-coreは必ずしもグラフ密度とよく一致するとは限らないことを理論的に示します。論文の残りは次のように編成されている。第2節では予備的表記法を用いる。3章で局所的な部分グラフを紹介し、セクション4の部分グラフを発見するための現在のアルゴリズム、セクション5のkコア分解への接続について説明します。6章で関連する作業を提示し、7章で実験を提示する。最後に、8章で議論した論文を締めくくる。12:11グラフの密度Tweet広告を非表示にする関連記事2018-02-26俺のFPTの理解FPTにおいては幅とパラメータが存在する。Vacation月別アーカイブはてなブログをはじめよう!tinsep19さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。