グラフアルゴリズム

第6章 コミュニティ検出アルゴリズム コミュニティ検出アルゴリズム

この作品はAIを使って翻訳されている。ご意見、ご感想をお待ちしている：[e-mail]

コミュニティの形成はあらゆる種類のネットワークで一般的であり、それを発見することは、グループの振る舞いや創発現象を評価するために不可欠である。 コミュニティを発見する際の一般的な原則は、そのメンバーがグループ外のノードよりもグループ内でより多くの関係を持つということである。 これらの関連セットを特定することで、ノードのクラスター、孤立グループ、ネットワーク構造が明らかになる。 この情報は、仲間グループの共通の振る舞いや嗜好を推測したり、レジリエンスを推定したり、入れ子関係を見つけたり、他の分析のためのデータを準備したりするのに役立つ。 コミュニティ発見アルゴリズムはまた、一般的な検査のためのネットワーク可視化を作成するためにもよく使用される。

最も代表的なコミュニティ検出アルゴリズムについて詳しく説明する：

• 三角形カウントとクラスタリング係数による全体的な関係密度の評価

• 連結クラスター発見のための強連結成分と弱連結成分

• ノード・ラベルに基づいてグループを素早く推測するためのラベル伝播

• ルーバン グループ化の質と階層を見るためのモジュール性

アルゴリズムがどのように機能するかを説明し、Apache SparkとNeo4jでの例を示す。アルゴリズムが1つのプラットフォームでしか利用できない場合は、1つの例のみを示す。これらのアルゴリズムでは、重み付きリレーションシップを使用している。重み付きリレーションシップは、通常、異なるリレーションシップの重要性を把握するために使用されるからである。

図6-1は、ここで取り上げたコミュニティ検出アルゴリズム間の違いの概要を示し、表6-1は、各アルゴリズムが何を計算するのか、使用例とともにクイックリファレンスを提供する。

図6-1. 代表的なコミュニティ検出アルゴリズム

注

コミュニティ検出アルゴリズムは、クラスタリングやパーティショニング・アルゴリズムとも呼ばれる。コミュニティ検出アルゴリズムは、クラスタリングやパーティショニング・アルゴリズムとも呼ばれる。 各セクションでは、特定のアルゴリズムに関する文献で最も著名な用語を使用する。

表6-1. コミュニティ検出アルゴリズムの概要

アルゴリズムの種類	何をするのか	使用例	スパークの例	Neo4jの例
三角形カウントとクラスタリング係数	三角形を形成するノードの数と、ノードがどの程度集まりやすいかを測定する。	グループの安定性を推定し、ネットワークが緊密に結びついたクラスターを持つグラフに見られる「スモールワールド」の振る舞いを示すかどうかを判定する。	はい	はい
強く結びついたコンポーネント	各ノードが、同じグループ内の他のすべてのノードから、関係の方向に従って到達可能であるグループを発見する。	所属団体や類似商品に基づいて商品を推薦する	はい	はい
コネクテッド・コンポーネント	各ノードが、関係の方向に関係なく、同じグループ内の他のすべてのノードから到達可能であるグループを発見する。	他のアルゴリズムで高速グルーピングを行い、島を特定する ...