グラフの密度
k-coreが気になるのでDensity-friendly graph decomposition ( https://users.ics.aalto.fi/gionis/friendly.pdf )を読む。超訳
Abstract
最新のグラフマイニングツールでは、k-core分析によりグラフを階層構造に分解するのは標準的な操作です。
k-core分解は次数の分布によってグラフを分析する、単純ですが効率的な方法です。
中心にむかって連結性が増加するように、グラフ内の領域を識別し、構成を明らかにします。
k-core分析は頂点の次数に依存しますが、k-coreは自然な密度特性を満たしません。簡単に言えば、最も中央のk-coreが、必ずしも最も密度の高いサブグラフであるとは限りません。
k-coreとグラフの密度のこの不一致が我々の研究の土台です。
サブグラフが局所的に密集している(locally-dense)ということを定義することから始め、私たちの定義にはk-coreと同様にグラフのネストされたチェーン分解が必要であることを示します。
この分解の結果、密度が増加する順に構成されます。
グラフ G=(V,E)に対するこのような局所的に密な分解は多項式時間で計算できることを示します。
正確な分解アルゴリズムの実行時間はO(|V|^2|E|)ですが、実際にはかなり速い。さらに、局所的に最適な最適分解に第2因子近似を提供する線形アルゴリズムも開発しました。
またk-core分解が第2因子近似であることを示します。
しかし、我々の実験評価によって示されるように、実際にはk-coreは局所的に密なサブグラフとは構造が異なり、理論によって予測されるように、k-coreは必ずしもグラフ密度とよく一致するとは限りません。
INTRODUCTION
高密度サブグラフとコミュニティを見つけることは、グラフマイニングで最もよく研究されている問題の1つです。
高密度サブグラフを識別する技術は、生物学からウェブマイニング、社会および情報ネットワークの分析まで多数の応用分野で使用されている。
高密度サブグラフを発見するために提案された多くの概念の中でk-coreは、その定義の単純さと線形時間で識別できるために特に魅力的です。
グラフのk-coreは、すべての頂点がそのサブグラフ内の少なくともk個の他の頂点に接続されている最大部分グラフとして定義されます。
k-core分解は、サブグラフのネストされたシーケンスを形成するという素晴らしい特性があり、グラフを分析するのに有用なツールになります。
グラフのk-core分解が、内側コアの頂点の度数が高いサブグラフの連鎖を与えるという事実は、内側コアが特定の意味では、外側コアよりも密度が高く接続されていることを期待させますが、この記述は真実ではありません。この論文では上記が真である、すなわち分解の内側の部分グラフが外側のグラフよりも密度が高いグラフ分解を得る方法を示します。
密度を定量化するために、densest-subgraph問題で使用される古典的な概念を採用します。密度は、サブグラフのエッジと頂点の比として定義されます。
この密度の定義は、平均次数を2で割ったものとして見ることもできます。
我々の動機づけは、この密度の定義に従ってk-coreが順序付けされていないことである。
次の例は、最も内側のコアが必ずしも最も密なサブグラフではないことを示しています。実際、頂点を追加または削除することで密度を上げることができます。
例1 6つの頂点と9つの辺からなる図1のグラフG1(画像は略) を考えてみましょう。
グラフ全体の密度は9/6 = 1.5です。
このグラフには、3つのkコアがあります。C1としてマークされた3コア、C2としてマークされた2コア、および1コアであり、グラフ全体に対応し、C3としてマークされています。
コアC1は密度6/4 = 1.5（6つのエッジと4つの頂点を含む）を有し、コアC2は密度8/5 = 1.6（8つのエッジと5つの頂点を含む）を有する。
言い換えれば、C1は内部コアであるにもかかわらずC2よりも密度が低い。
図1に示すG2(画像は略)について考えてみましょう。
このグラフには、単一のコア、つまり2コアがあり、グラフ全体が含まれています。
このコアの密度は11/8 = 1.375に等しい。しかし、サブグラフB1は7つのエッジと5つの頂点を含み、密度7/5 = 1.4を与え、これは唯一のコアの密度よりも高い。
この例では、より密度の高い代替のグラフ分解を定義するよう動機づけています。このグラフような分解を局所的分解と呼びます。
私たちは次を満たすような分解に興味があります。
（i）内側サブグラフの密度が外側サブグラフの密度よりも高く、
（ii）最も内側のサブグラフは最も細いサブグラフに対応し、
（iii）分解を効率的に計算または近似することができる。
局所的に密集した部分グラフを定義することで目標を達成します。本質的には、頂点を追加したり削除して密度を上げることはできません。
これらの部分グラフは、外側の部分グラフに行くにつれて密度が減少し、最も内側の部分グラフが実際には最も細い部分グラフであるような階層に配置されることを示す。
この階層を発見するための2つの効率的なアルゴリズムを提供します。
最初のアルゴリズムは、Goldberg [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章で議論した論文を締めくくる。
