グラフ理論とリンク チャートの概念

ナレッジ グラフのコンテンツを含むリンク チャートを操作または解析する際に使用する方法を決める場合、およびその方法の結果を評価する場合、グラフ理論に関連するいくつかの概念を理解するのに役立ちます。

リンク チャートのコンテンツはグラフとして管理されます。 グラフ理論の説明では、ノードとエッジに言及することがよくあります。 グラフにおけるノードは、ナレッジ グラフにおけるエンティティに相当します。 グラフにおけるエッジは、ナレッジ グラフにおけるリレーションシップに相当します。

エンティティの次数または減次数の計算

エンティティの次数は、そのエンティティが属するリレーションシップの数として計算されます。 エンティティの次数はリンク チャートを考慮して計算されます。 つまり、エンティティの次数を計算するために、リンク チャートに存在するリレーションシップだけが使用されます。

エンティティの次数とは異なり、エンティティの減次数は、そのエンティティが関連するエンティティの数として計算されます。 次のシナリオについて考えてみましょう。

2 つのエンティティ間に複数のリレーションシップが存在します。たとえば、エンティティ Employee A が、WorksFor リレーションシップと TeamLeader リレーションシップによって、別のエンティティ Employee B と接続されています。 Employee A の次数は 2 になります。 しかし、Employee A の減次数は 1 になります。 次の図で、この例の図について、A というラベルが付いたリレーションシップを見てみましょう。

リレーションシップ グループ - 前の例では、Employee A と Employee B の間で WorksFor リレーションシップと TeamLeader リレーションシップがグループ化されているとします。 次数と減次数の計算では、リレーションシップ グループは存在しないかのように扱われます。 Employee A の次数を求める場合は、グループ内の各リレーションシップが個別に考慮されるため、次数が 2 になります。 しかし、減次数の場合、リレーションシップ グループは Employee A と Employee B を接続しているだけなので、減次数が 1 になります。 次の図で、この例の図について、Group (2) および Group (4) というラベルが付いたリレーションシップ グループを見てみましょう。

再帰リレーションシップ - あるエンティティがリレーションシップの関連元と関連先の両方である場合に再帰リレーションシップが存在します。 たとえば、Employee C がプロジェクト リーダーであるだけでなくそのプロジェクトで働いていると、自身が TeamLeader になります。 エンティティが出力リレーションシップと入力リレーションシップに属しているため、Employee C の次数は 2 になります。 しかし、エンティティが他のエンティティと関連付けられていないため、Employee C の減次数は 0 になります。 次の図で、この例の図について、B というラベルが付いたリレーションシップを見てみましょう。

1 つのリレーションシップが 2 つのエンティティを結んでいる一般的なリレーションシップの場合、エンティティの次数とその減次数は同じになります。 たとえば、エンティティ Employee A が、WorksFor リレーションシップによって Employee B と接続され、TeamLeader リレーションシップによって Employee C と接続されています。 Employee B は 2 つのリレーションシップに属し、2 つのエンティティに関連付けられているため、Employee A の次数は 2 になり、減次数も 2 になります。 Employee B と C がリンク チャート上でグループ化され、それにより 2 つのリレーションシップもグループ化されている場合、Employee A の次数と減次数は変わりません。Employee B と C は 2 つの個別のリレーションシップに属したままであり、2 つの個別のエンティティに関連付けられたままであるためです。

次の図は、サンプル リンク チャートの各エンティティの減次数 (R:x) と次数 (D:y) を示しています。 ピンク色のエンティティは減次数 1 (R:1)、青色のエンティティは減次数 2 (R:2)、緑色のエンティティは次数 3 以上 (R:x) です。

サンプル リンク チャートのエンティティの減次数と次数

エンティティの次数または減次数の使用

一部のリンク チャートの操作は、処理されるエンティティの次数または減次数に基づいています。 エンティティの次数は、次の「中心性スコア」を計算する際に考慮されます。

  • 次数
  • 内向き次数
  • 外向き次数

エンティティの減次数は、次の方法がリンク チャートで使用される場合に考慮されます。

  • オーガニック レイアウト」 - オーガニック レイアウトを適用してエンティティとリレーションシップを視覚化する方法を変更すると、減次数が 1、2、または 3 のエンティティが後処理されます。
  • 切詰め操作」 - 切詰め方法はリンク チャートからリーフ エンティティを削除するために使用されます。 リーフ エンティティは、減次数が 1 のエンティティとして定義されます。

同じナレッジ グラフ エンティティは、これらのエンティティに関連付けられた異なるリレーションシップが含まれている場合、リンク チャートに追加することができます。 各リンク チャートでは、基礎となるナレッジ グラフではなく、リンク チャートに固有のエンティティの次数と減次数が計算されます。