コミュニティ検索

ネットワーク内のコミュニティの発見、つまりコミュニティ検出/発見は、ネットワーク科学における基本的な問題であり、過去数十年にわたり大きな注目を集めてきました。近年、ビッグデータに関する膨大な研究により、クエリノードを含む可能性が最も高いコミュニティを見つけることを目的とした、関連するものの異なる問題であるコミュニティ検索が、学術界と産業界の両方から大きな注目を集めています。これは、クエリに依存するコミュニティ検出問題の変種です。コミュニティ検索の詳細な調査は、参考文献^{[ 1 ]で見つけることができます。これは、}最近の研究 ^{[ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [8][ 9] [ 10 ] [ 11 ]をすべてレビューしています。}

SIGKDD'2010で発表されたコミュニティ検索に関する最初の研究^{[ 2 ]}で指摘されているように、既存のコミュニティ検出/発見手法の多くは、クエリノードを参照せずにグラフを事前に分割する必要がある静的なコミュニティ検出問題を対象としています。一方、コミュニティ検索は、クエリ頂点を含む可能性が最も高いコミュニティに焦点を当てることが多いです。コミュニティ検出/発見に対するコミュニティ検索の主な利点は以下のとおりです。

（１）高いパーソナライゼーション。^{[ 3 ] [ 9 ] [ 10 ]}コミュニティ検出/発見では、サブグラフがコミュニティとして適格かどうかを判断するために、多くの場合、同じグローバル基準が使用されます。つまり、基準は固定され、事前に決定されています。しかし実際には、異なる頂点のコミュニティは非常に異なる特性を持つ可能性があります。さらに、コミュニティ検索では、クエリのユーザーがよりパーソナライズされたクエリ条件を指定できます。加えて、パーソナライズされたクエリ条件により、コミュニティを容易に解釈できます。

例えば、最近の研究^{[ 9 ]}では、ノードがキーワードなどの属性に関連付けられている属性付きグラフに焦点を当て、強い構造とキーワードの凝集性の両方を示す属性付きコミュニティと呼ばれるコミュニティを見つけようとしています。クエリのユーザーは、クエリノードとその他のクエリ条件を指定できます。(1) 期待されるコミュニティの最小次数である値k、(2) 期待されるコミュニティの意味を制御するキーワードのセット。返されるコミュニティは、すべてのコミュニティメンバーが共有するキーワードによって容易に解釈できます。詳細は^{[ 11 ]を参照してください。}

（２）高い効率性。近年のソーシャルネットワークの著しい成長に伴い、非常に大規模なグラフが数多く存在します。例えば、FacebookやTwitterのユーザー数は数十億人規模になることも珍しくありません。コミュニティ検出／発見は、ソーシャルネットワーク全体からすべてのコミュニティを検出することが多いため、非常にコストがかかり、時間もかかります。一方、コミュニティ検索はサブグラフ上で動作することが多く、はるかに効率的です。さらに、ソーシャルネットワーク全体からすべてのコミュニティを検出する必要がない場合も少なくありません。レコメンデーションやソーシャルメディア市場などの実際のアプリケーションでは、人々はすべてのコミュニティではなく、本当に興味のあるコミュニティに焦点を当てることが多いのです。

最近の研究^{[ 4 ] [ 9 ]}では、数百万規模のグラフの場合、コミュニティ検索は明確なコミュニティを見つけるのに1秒未満しかかからないことが多く、これは既存の多くのコミュニティ検出/発見方法よりもはるかに高速であることが示されています。これはまた、コミュニティ検索が大規模グラフからコミュニティを見つけるのに適していることを示唆しています。

（３）動的に変化するグラフのサポート。^[３]現実世界のグラフは、ほとんどの場合、時間の経過とともに変化します。コミュニティ検出では、コミュニティを見つけるために同じグローバル基準を使用することが多いため、グラフ内のノードやエッジの更新に敏感ではありません。言い換えれば、検出されたコミュニティは、短期間で鮮度を失う可能性があります。一方、コミュニティ検索は、クエリ要求に基づいてオンラインでコミュニティを検索できるため、これを容易に処理できます。

コミュニティ検索では、コミュニティの結束度を定式化するために、よく定義された基本的なグラフ指標がよく使用されます。一般的に使用される指標は 、 k-core (最小次数)、^{[ 2 ] [ 4 ] [ 6 ] [ 7 ] [ 9 ]} k-truss (メトリック)、^{[ 5 ] [ 8 ]} k-edge-connected、^{[ 12 ] [ 13 ]などです。これらの指標の中で、k-core メトリックが最も人気があり、 [ 1 ]}で調査されているように、最近の多くの研究で使用されています。