超訳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が順序付けされていないことである。次の例は、最も内側のコアが必ずしも最も密なサブグラフではないことを示しています。実際、頂点を追加または削除することで密度を上げることができます。