リンク チャートのコミュニティの検出

ナレッジ グラフに基づくリンク チャートを使用してコミュニティを検出し、互いに密接に接続しているエンティティと他のコミュニティのエンティティと緩く接続しているエンティティを検索することができます。 コミュニティは、ナレッジ グラフ全体に含まれるコンテンツではなく、リンク チャートに現在存在するエンティティに基づいて検出されます。

コミュニティ検出アルゴリズムにより、他の解析方法では発見できない可能性がある密接に関連するエンティティのグループを視覚化できます。 ソーシャル ネットワーク、科学的協力や研究パターン、共有接続に基づく知人の可能性が高い個人などの影響力のあるグループをコミュニティで示すことができます。

コミュニティには、1 つのエンティティをメンバーとして持つことができます。 また、解析では、ネットワークの残りの部分から孤立しているエンティティを特定することもできます。

以下では、コミュニティの計算方法、方法パラメーターのカスタマイズ方法、結果の探索方法について説明します。

コミュニティ検出方法

ナレッジ グラフに基づくリンク チャートでは、Louvain、Girvan-Newman、二重連結、弱連結、強連結、ラベル伝播の 6 つのコミュニティ検出方法を利用できます。 コミュニティ テーブル ビュー コミュニティ検出[検出方法] ドロップダウン リストから方法を選択します。 一度に使用できる方法は 1 つだけです。

Louvain

Louvain コミュニティ検出方法は、大規模なネットワークでコミュニティを検出する階層クラスタリング アルゴリズムです。 この方法はコミュニティ内のエンティティがどの程度の密度で接続されているかを評価し、その結果とランダム化されたネットワーク内でエンティティが接続される程度とを比較します。 これはコミュニティ テーブルを開くときのデフォルトの方法です。

コミュニティ内のリレーションシップがランダム ネットワーク内のリレーションシップより密度が高い場合、モジュラリティは正です。 コミュニティ内でのリレーションシップの密度が高くなるにつれ、モジュラリティが増加します。

最初にこの方法では、モジュラリティを最適化することによって、小さなコミュニティを検出します。 モジュラリティは、どのようにノードがコミュニティに分割されているかの品質を示す尺度です。 コミュニティ内のリレーションシップがランダム ネットワーク内のリレーションシップよりも密度が高い場合、モジュラリティは正であり、エンティティはコミュニティ内に配置されます。 コミュニティ内のリレーションシップの密度が高くなるほど、モジュラリティ スコアは高くなります。

このプロセスは反復的に繰り返され、ランダムなコミュニティの割り当てを使用して、サイズを増やしたコミュニティを評価します。

Girvan-Newman

Girvan-Newman コミュニティ検出方法は、コミュニティを相互に接続するリレーションシップの媒介のレベルを考慮してコミュニティを特定します。 最短パスはグラフ内のすべてのエンティティ間で計算され、媒介中心性はすべての通過したリレーションシップに対して計算されます。 個別のコミュニティに接続するリレーションシップは、あるコミュニティから別のコミュニティに最も頻繁に通過する必要があるため、媒介中心性が最も高くなります。

媒介中心性が最も高いリレーションシップが削除され、そのプロセスが繰り返されます。 中心のリレーションシップが削除されると、コミュニティは一層明確になります。 リレーションシップは、残りのリレーションシップの媒介中心性がすべて同じになるまで、繰り返し削除されます。

非常に大きなリンク チャートでは、このプロセスに長い時間がかかることがあります。

二重連結

二重連結方法は、相互に接続するネットワーク エンティティ内のコミュニティを検索します。 リレーションシップで接続された 2 つのエンティティは同じコミュニティに属しています。 あるエンティティから別のエンティティへのリレーションシップが可能な場合で、コミュニティ内のリレーションシップの 1 つを削除してもこれが当てはまる場合、その他のエンティティは同じコミュニティに属しています。 各エンティティは、複数のコミュニティに属することができます。

3 つのコミュニティが相互接続されているリンク チャート

この例では、C は、各コミュニティ内のエンティティとのリレーションシップがあるため、3 つすべてのコミュニティに属しています。 エンティティ A、B、C は 1 つのコミュニティを形成しています。それぞれが相互に接続され、エンティティ間のリレーションシップの 1 つが削除された場合に相互に接続されたままであるからです。 C と D、C と E、または C と F のリレーションシップが削除されると、D、E、F はそれぞれ A と B に接続しなくなるため、A、B、C のコミュニティに属していません。

弱連結

弱連結コミュニティは、すべてのエンティティがパスによって相互に接続されているコミュニティです。 リンク チャート内にあるエンティティ間のリレーションシップの方向は考慮されません。つまり、リンク チャートは無向グラフとして評価されます。

2 つの弱連結コミュニティを含むリンク チャート

この例には、2 つの弱連結コミュニティがあります。 A、B、C、D、E、F が 1 つのコミュニティを形成し、X、Y、Z が別のコミュニティを形成しています。 それぞれのコミュニティには、すべてのエンティティを接続するリレーションシップがあります。 X、Y、Z コミュニティを A、B、C、D、E、F コミュニティに接続するリレーションシップはありません。

何らかの方法でグラフ内のすべてのエンティティが他のエンティティと接続されている場合、グラフ全体は弱連結されています。

強連結

強連結コミュニティは、リレーションシップの方向が考慮される場合にコミュニティ内のすべてのエンティティが相互に接続されているコミュニティです。 つまり、リンク チャートは有向グラフとして評価されます。

これは、コミュニティ内の任意の場所を始点に、各リレーションシップの方向に従ってパスを追跡すると、コミュニティ内のすべてのエンティティに到達できることを意味します。

複数の強連結コミュニティを含むリンク チャート

この例では、いずれかのコミュニティの任意のエンティティから有向リレーションシップをたどると他のすべてのエンティティに到達できるため、X、Y、Z コミュニティと A、B、C、D コミュニティは強接続されています。

E と F は、他のエンティティとは強接続されておらず、独自のコミュニティです。 A、B、C、D コミュニティから F に到達できますが、F から大きい方のコミュニティには到達できません。 同様に、E から A、B、C、D コミュニティに到達できますが、大きい方のコミュニティから E には到達できません。

ラベル伝播

ラベル伝播方法は、情報がグラフを移動する方法に基づいてコミュニティを決定するアルゴリズムです。 最初に、エンティティにラベルが割り当てられます。 次に、ランダムに選択されたエンティティがその近傍を評価し、ほとんどの近傍が使用するラベルを決定します。 エンティティはそのラベルを、ほとんどの近傍が持つラベルと一致するように更新します。 エンティティが近傍を評価し、ラベルを更新するプロセスは何度も繰り返されます。

複数回の反復処理後、ラベルは密接に接続されたコミュニティ内で優位になり、接続が少ないグラフ内の他の領域と交差する問題が発生する傾向があります。 反復処理が行われるほど、ラベルは密接に接続されたコミュニティから弱連結コミュニティに交差する可能性が高くなります。 ほとんどの近傍が持つラベルがすべてのノードに割り当てられると、指定した反復回数の処理が完了していない場合でもアルゴリズムは終了します。

ラベル伝播方法では、解析の実行に使用されるオプションに応じて、使用されるたびに異なるコミュニティのセットが生成される可能性があります。 アルゴリズムが使用する乱数ジェネレーターの初期化に使用されるシード数、生成されるソリューションの数、各ソリューションの生成に使用されるアルゴリズムの反復回数を変更できます。

コミュニティ テーブルは、複数回の実行により生成されたすべてのソリューションの集約を示します。 Solution フィールドを使用して、コミュニティ テーブルを並べ替えることにより、各実行の結果を表示できます。 デフォルトでは、20 個のソリューションが生成されます。 最初の実行の結果はパーティション 0 に関連付けられ、20 回目の実行の結果はテーブルのパーティション 19 に関連付けられます。

ラベル伝播方法のいくつかのパラメーターを決定できる設定を使用できます。 コミュニティ テーブルの上部にあるツールバーの [オプション] ボタンをクリックして、[ラベル伝播] 見出しをクリックします。

コミュニティ テーブルを開く

リンク チャートに含まれるエンティティのコミュニティは、デフォルトで Louvain 方法を使用して決定され、コミュニティ テーブル コミュニティ検出 に記載されます。 別の方法を使用してコミュニティを評価するには、[検出方法] ドロップダウン リストを使用します。 テーブル内のすべての行が更新され、新しいコミュニティの結果のプロパティが表示されます。

テーブルにはコミュニティごとに 1 つの行があります。 各コミュニティのプロパティは、テーブルのさまざまなフィールドに表示されます。

  • Solution- [ソリューション列の表示] オプションがオンの場合のみ、ラベル伝播方法で表示されます。このオプションはデフォルトでオンになっています。 このフィールドには、ラベル伝播方法で生成された各ソリューション ID が表示されます。
  • Community- ラベル伝播を除くすべてのコミュニティ検出方法で、このフィールドには、コミュニティの ID が表示され、テーブル内の行の並べ替えにデフォルトで使用されます。 ラベル伝播方法の場合、この方法により生成される 1 つのソリューション内のコミュニティを識別する値がこの列に表示されます。
  • Count- コミュニティ内のエンティティの数。
  • Entity- コミュニティ内の各エンティティの表示名。 デフォルトで、最初の 5 つのエンティティが表示されます。 コミュニティにエンティティが 5 つ以上含まれている場合、リストの下部にある [+ 増やす] をクリックすると追加のエンティティを表示できます。 エンティティの表示を減らすには、[- 減らす] をクリックします。
  • Type- コミュニティ内の各エンティティのエンティティ タイプ。 デフォルトで、最初の 5 つのエンティティ タイプが表示されます。 多くのエンティティがリストに表示されると、それに対応するエンティティ タイプも Type 列に表示されます。 追加のエンティティ タイプを表示するにはタイプ リストの下部にある [+ 増やす] をクリックします。 エンティティ タイプの表示を減らすには、[- 減らす] をクリックします。

リンク チャート内のエンティティのコミュニティを表示するには、次の手順を実行します。

  1. リボンの [リンク チャート] タブの [解析] グループで、[コミュニティ] コミュニティ検出 をクリックします。

    コミュニティ テーブル コミュニティ検出 が開きます。 コミュニティ テーブル ビューのタブに表示される名前で、コミュニティが計算されたリンク チャートが識別されます。 デフォルトでは、Louvain 方法が使用されます。 テーブルの行は、デフォルトで Community フィールドを使用して並べ替えられます。

    コミュニティ テーブルには、リンク チャートに含まれる密接に関連するエンティティのグループが示されます。

  2. [検出方法] ドロップダウン リストをクリックして、コミュニティを評価する別の方法をクリックします。

    リンク チャート内のコミュニティが再評価され、テーブルの行が更新されて結果が表示されます。

ドキュメントを含める

デフォルトでは、ドキュメント エンティティがリンク チャートに存在する場合でも、コミュニティが検出されるときに考慮されませんが、ドキュメント エンティティを計算に含めることができます。 たとえば、特定のエンティティに接続されたドキュメントがそのコミュニティに属しているかどうかを判断できます。

  1. コミュニティ テーブルの上部にあるツールバーで、[ドキュメントを含める] チェックボックスをオンまたはオフにします。
    • オン - コミュニティを検出する際にドキュメント エンティティを含めます。 選択した方法に応じて、ドキュメントが考慮され、それぞれのコミュニティに含められます。

    • オフ - コミュニティを検出する際にドキュメント エンティティを除外します。 ドキュメントは考慮されず、コミュニティに含められません。 これがデフォルトです。

コミュニティ テーブルが自動的に更新され、この設定への変更が反映されます。 ドキュメント エンティティがテーブルに追加またはテーブルから削除され、コミュニティが自動的に再計算されます。

リンク チャートのコミュニティの特定

コミュニティ テーブルの行を 1 行以上選択すると、その行で定義されたコミュニティ内のすべてのエンティティが、テーブルの Entity フィールドおよび関連するリンク チャートで選択されます。 テーブル内の行を選択するには、行番号または CommunityCountSolution フィールドの値をクリックします。

Entity フィールドの個別のエンティティを 1 つ以上クリックすると、そのエンティティを選択できます。 同様に、リンク チャート内のエンティティを選択すると、対応するコミュニティ テーブル内の Entity フィールドでもそのエンティティが選択されます。 ラベル伝播検出方法の場合は、エンティティはコミュニティ テーブルの複数の行に表示され、表示しているすべての行で選択されます。

Type フィールドのエンティティ タイプをクリックすると、コミュニティに含まれるそのタイプのエンティティをすべて選択できます。

  1. コミュニティ テーブルの行をクリックして、そのコミュニティ内のエンティティを選択します。

    Entity フィールドとリンク チャートで、対応するエンティティが選択されます。

    コミュニティ テーブルとリンク チャートで、コミュニティ内のエンティティが選択されます。

  2. Type フィールドのタイプをクリックして、コミュニティに含まれるそのタイプのエンティティをすべて選択します。

    Entity フィールドとリンク チャートで、対応するエンティティが選択されます。

    コミュニティ テーブルとリンク チャートで、コミュニティ内にある指定したタイプのエンティティが選択されます。

  3. Entity フィールドのエンティティをクリックして選択します。

    Entity フィールドとリンク チャートで、エンティティが選択されます。

    コミュニティ テーブルとリンク チャートで、指定したエンティティが選択されます。

  4. コミュニティ内のすべてのエンティティとタイプを表示するには、Entity フィールドのエンティティのリストの下部、または Type フィールドのタイプのリストの下部にある [+ 増やす] をクリックします。
  5. コミュニティ内のエンティティとタイプの表示を減らすには、Entity フィールドのエンティティのリストの下部、または Type フィールドのタイプのリストの下部にある [- 減らす] をクリックします。

コミュニティ テーブルでのエンティティの検索

対象エンティティがどのコミュニティに含まれているかわかりにくいことがあります。 コミュニティ テーブル ビューで、エンティティを検索して選択できます。

  1. コミュニティ テーブルの上部にあるツールバーで検索テキスト ボックス内をクリックします。
  2. リンク チャート内のエンティティの表示名を入力します。

    コミュニティ テーブルの行が自動的にフィルター処理され、表示名が入力した名前と一致するエンティティだけが表示されます。 フィルター処理されたエンティティを示す行だけがテーブルに表示されます。

    検索テキスト ボックスにエンティティの表示名を入力して、コミュニティ テーブル内のエンティティを検索します。

  3. 対象のエンティティを含むコミュニティを選択します。
  4. 検索テキスト ボックスの [削除] ボタン 削除 をクリックして、検索を消去し、コミュニティ テーブルのすべての行を表示します。

    コミュニティ内のすべてのエンティティが表示され、選択されたままの状態になります。 テーブルにすべてのコミュニティが表示されています。

コミュニティ テーブルに表示されるエンティティのタイプをフィルター

デフォルトで、コミュニティ テーブルには、リンク チャートのすべてのエンティティが含まれています。 リンク チャートが大きいと、テーブルに表示される情報が多すぎて処理できなくなる可能性があります。 テーブルに表示されるタイプをフィルター処理して、各コミュニティの特定のエンティティ タイプだけを表示できます。

  1. コミュニティ テーブルの上部にあるツールバーで、[タイプ] ボタン タイプのフィルター をクリックします。

    該当のタイプのエンティティがリンク チャートに存在しない場合でも、ナレッジ グラフ内のすべてのエンティティ タイプを含むドロップダウン リストが表示されます。 デフォルトでは、すべてのエンティティ タイプがオンになっています。

  2. ドロップダウン リストで、コミュニティ テーブルに表示するエンティティ タイプをオンにします。 コミュニティ テーブルに表示しないエンティティ タイプはオフにします。 リストに表示されていない場合は、そのエンティティ タイプの名前を入力します。エンティティ タイプのリストが自動的にフィルター処理され、フィルター処理されたリストでエンティティ タイプをオン/オフできます。

    選択したエンティティ タイプの総数がツールバーの [タイプ] ボタンの横に表示されます。

コミュニティ テーブル内のエンティティが自動的に更新されます。 オンにしたエンティティ タイプに関連付けられたエンティティがテーブルに表示されます。 オフにしたエンティティ タイプに関連付けられたエンティティがテーブルから削除されます。

コミュニティの再計算

リンク チャートのコミュニティ テーブルを最初に開くとき、コミュニティが検出され、コミュニティが最新であることを示すメッセージがテーブルの下部に表示されます。

リンク チャートでエンティティとリレーションシップを追加または削除した後、以前に検出されたコミュニティはリンク チャートのコンテンツを反映しなくなることがあります。 コミュニティ テーブルの下部に、コミュニティが最新でないことを示すメッセージが表示されます。

  1. コミュニティ テーブル ビューの下部にある [更新] ボタン 更新 をクリックします。

    すべての行がコミュニティ テーブルから削除され、新しいコミュニティが再計算されます。

テーブルの下部にあるメッセージは、コミュニティが最新であることを示しています。

ラベル伝播オプションの設定

ラベル伝播方法では、リンク チャートのコミュニティを検出するプロセスを制御できます。

この方法が生成するソリューションの数および各ソリューションを得るために使用される反復回数を決めることができます。 また、アルゴリズムで使用される乱数ジェネレーターを初期化するためのシード数も指定できます。 異なるシード値を使用すると、異なるソリューションが生成されます。

[オプション] パネルで設定を選択したら、コミュニティ テーブルを更新してコミュニティを再計算します。

  1. コミュニティ テーブルの上部にあるツールバーで、[オプション] ボタン オプション をクリックします。

    [オプション] パネルが表示されます。

  2. [オプション] パネルで、[ラベル伝播] 見出しをクリックして、使用可能な設定を表示します。
  3. [乱数ジェネレーターのシード] テキスト ボックスに値を入力します。

    デフォルト設定は 0 です。

  4. リンク チャートのコミュニティのセットを生成するためにアルゴリズムを実行する回数を [ソリューションの数] テキスト ボックスに入力します。

    デフォルト設定は 1 です。

    [ソリューションの数] が 1 のとき、リンク チャートのコミュニティのセットが 1 つ生成されます。 これらのコミュニティは、Solution フィールドの値 0 に関連付けられます。 [ソリューションの数] が 10 のとき、リンク チャートのコミュニティのセットが 10 個生成されます。10 回目の実行のコミュニティは、Solution フィールドの値 9 に関連付けられます。

  5. [反復回数] テキスト ボックスに、ラベル伝播アルゴリズムにより生成される 1 つのソリューションの最終的なコミュニティの決定に使用する最大反復数を入力します。

    デフォルト設定は 1,000 です。

  6. [ソリューション列の表示] チェックボックスを使用して、各実行またはアルゴリズムによりソリューションを計算するために、検出されたコミュニティを並べ替えるかどうかを選択できます。
    • オン - Solution フィールドを表示します。 これがデフォルトです。
    • オフ - Solution フィールドを表示しません。
  7. コミュニティ テーブルの右下隅にある更新ボタン 更新 をクリックして、更新された結果を表示します。