1. プロパティ・グラフのグラフ開発者ガイド
  2. グラフ・サーバー(PGX)の使用
  3. グラフ分析を使用したアプリケーションの開発
  4. 組込みアルゴリズムの実行
  5. 中心性アルゴリズム

16.6.3 中心性アルゴリズム

中心性アルゴリズムは、グラフ内のノードの重要性または影響を評価するために使用されます。

これらのアルゴリズムは、ローカル性とフォーカスに基づいて、3つのカテゴリに広く分類できます。

表16-12 中心性アルゴリズムの分類

カテゴリ 説明 アルゴリズムの例
ローカル・メジャー これらのアルゴリズムは、ノードの即時接続に基づいてノードの重要性を評価し、簡単で計算効率の高いインサイトを提供します。 次数中心性
グローバル・パスベースのメジャー これらのアルゴリズムは、ノード全体の接続性とグラフ全体の最短パスに基づいてノードを評価します。 近接中心性、調和中心性、中間中心性
グローバルな影響ベースのメジャー これらのアルゴリズムは、ノードの直接接続と間接接続に基づいてノードの影響を評価し、複雑なグラフ内の階層的な重要性と影響に関する詳細なインサイトを提供します。 固有ベクトル中心性、Random Walk with Restart(RWR)、PageRank、ArticleRank、Hyperlink-Induced Topic Search(HITS)、Stochastic Approach for Link-Structure Analysis (SALSA)

中心性アルゴリズムの詳細は、次のトピックを参照してください。

  • 次数中心性
    次数中心性アルゴリズムは、各ノードがグラフ内に持つ直接接続の数を測定し、グラフ内の影響レベルまたは重要度を即時に示します。
  • 近接中心性
    近接中心性アルゴリズムは、他のすべてのノードにすばやく到達できるノードを識別し、効率的な通信機能や情報の拡散機能を強調表示します。
  • 調和中心性
    調和中心性アルゴリズムは、切断されたグラフをより適切に考慮するために近接中心性を改善します。
  • 頂点媒介中心性アルゴリズム
    頂点媒介中心性アルゴリズムは、重要なブリッジとして機能するノードを識別し、グラフ内の情報またはリソースのフローを制御します。
  • PageRank
    PageRankは各頂点に数値の重みを割り当て、グラフ内の相対的な重要性を測定します。

親トピック: 組込みアルゴリズムの実行

16.6.3.1 次数中心性

次数中心性アルゴリズムは、各ノードがグラフ内に持つ直接接続の数を測定し、グラフ内の影響レベルまたは重要度を即時に示します。

このアルゴリズムは、次のシナリオで適用できます:

  • 直接接続に基づいてノードの重要性に関するローカル・インサイトを迅速に取得する場合。
  • 即時の影響やアクティビティ・レベルを理解する場合。
  • ソーシャル・ネットワーキング分析(多くの友人やフォロワを持つユーザーの識別など)。
  • 財務トランザクション分析(トランザクション数が最も多いアカウントの検出など)。
  • ほとんどの人と直接接触している人の特定による、病気の蔓延の調査。

次の次数中心性アルゴリズムのバリアントがサポートされています:

  • 次数中心性: グラフ内の各頂点の入力エッジと出力エッジの合計数を返します。
  • 入次数中心性: グラフ内の各頂点の入力エッジの合計数を返します。
  • 出次数中心性: グラフ内の各頂点の出力エッジの合計数を返します。
これらのアルゴリズムを実行するための対応するAPIの詳細は、JavadocおよびPython APIリファレンスを参照してください。

例16-2 入次数中心性アルゴリズムの実行

次の例では、入力トランザクションの最大数を持つ上位10のアカウントを識別するために、BANK_GRAPHの次数中心性アルゴリズムを実行します。 

opg4j> var graph = session.readGraphByName("BANK_GRAPH",GraphSource.PG_PGQL)
graph ==> PgxGraph[name=BANK_GRAPH,N=1000,E=4996,created=1643308582055]
opg4j> var a = session.createAnalyst()
a ==> NamedArgumentAnalyst[session=4c054326-600d-47d3-ab40-36b41fa0e339]
opg4j> a.inDegreeCentrality(graph)
$3 ==> VertexProperty[name=in_degree,type=integer,graph=BANK_GRAPH_PGQL]
opg4j> graph.queryPgql("SELECT DISTINCT m.id, m.in_degree FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.in_degree DESC LIMIT 10").print()
+-----------------+
| id  | in_degree |
+-----------------+
| 387 | 39        |
| 934 | 39        |
| 135 | 36        |
| 534 | 32        |
| 380 | 31        |
| 330 | 30        |
| 406 | 28        |
| 746 | 28        |
| 259 | 26        |
| 352 | 26        |
+-----------------+
$5 ==> PgqlResultSetImpl[graph=BANK_GRAPH_PGQL,numResults=10]
PgxGraph graph = session.readGraphByName("BANK_GRAPH",GraphSource.PG_PGQL);
Analyst a = session.createAnalyst();
a.inDegreeCentrality(graph);
PgqlResultSet rs = graph.queryPgql("SELECT DISTINCT m.id, m.in_degree FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.in_degree DESC LIMIT 10");
rs.print();
>>> graph = session.read_graph_by_name('BANK_GRAPH', 'pg_pgql')
>>> a = session.create_analyst()
>>> a.in_degree_centrality(graph)
VertexProperty(name: in_degree, type: integer, graph: BANK_GRAPH_PGQL)
>>> graph.query_pgql("SELECT DISTINCT m.id, m.in_degree FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.in_degree DESC LIMIT 10").print()
+-----------------+
| id  | in_degree |
+-----------------+
| 387 | 39        |
| 934 | 39        |
| 135 | 36        |
| 534 | 32        |
| 380 | 31        |
| 330 | 30        |
| 406 | 28        |
| 746 | 28        |
| 259 | 26        |
| 352 | 26        |
+-----------------+

親トピック: 中心性アルゴリズム

16.6.3.2 近接中心性

近接中心性アルゴリズムは、他のすべてのノードにすばやく到達できるノードを識別し、効率的な通信機能や情報の拡散機能を強調表示します。

このアルゴリズムは、次のシナリオで適用できます:

  • グラフの全体的な構造の中心となるノードを決定し、効率的な情報フローまたは影響の分散を容易にする場合。
  • たとえば、ソーシャル・ネットワーク分析で、情報をネットワーク全体にすばやく広めることができるインフルエンサを特定する場合。
  • たとえば、財務トランザクション分析で、近接中心性が高いアカウントは迅速な資金移動を促進する可能性があるため、マネー・ロンダリングなどの不正行為を厳密に監視するために、このアカウントを潜在的な候補にする場合。
  • たとえば、病気の蔓延を調査する際に、ネットワークの中心的な立場にあるために、病気を他の多くの人にすばやく広める可能性のある個人を特定する場合。

近接中心性では、次の2つのバリアントがサポートされています:

  • 近接中心性(単位長): ノードvの近接中心性は、vから始まる可能な最短パスからのすべての距離の合計の逆数です。したがって、vの中心値が大きいほど、グラフ内の他のすべての頂点に近い値になります。
  • 近接中心性(重み付き): これは、グラフ内のすべての頂点について、頂点vから始まる可能な最短パスからのすべての距離の合計の逆数の計算時に、エッジからの重みを考慮します。エッジの重みは、0より大きい正の値である必要があります。
これらのアルゴリズムを実行するための対応するAPIの詳細は、JavadocおよびPython APIリファレンスを参照してください。

例16-3 次数中心性アルゴリズムの実行

次の例では、BANK_GRAPHで近接中心性アルゴリズムを実行して、他のアカウントとのより高いレベルの接続を持つ上位5つのアカウントを識別します。 

opg4j> var graph = session.readGraphByName("BANK_GRAPH",GraphSource.PG_PGQL)
graph ==> PgxGraph[name=BANK_GRAPH,N=1000,E=4996,created=1643308582055]
opg4j> var a = session.createAnalyst()
a ==> NamedArgumentAnalyst[session=4c054326-600d-47d3-ab40-36b41fa0e339]
opg4j> a.closenessCentralityUnitLength(graph)
$6 ==> VertexProperty[name=closeness,type=double,graph=BANK_GRAPH_PGQL]
opg4j> graph.queryPgql("SELECT DISTINCT m.id, m.closeness FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.closeness DESC LIMIT 5").print()
+-----------------------------+
| id  | closeness             |
+-----------------------------+
| 934 | 3.866976024748647E-4  |
| 135 | 3.8595137012736397E-4 |
| 387 | 3.8476337052712584E-4 |
| 406 | 3.8284839203675346E-4 |
| 330 | 3.7425149700598805E-4 |
+-----------------------------+
$7 ==> PgqlResultSetImpl[graph=BANK_GRAPH_PGQL,numResults=5]
PgxGraph graph = session.readGraphByName("BANK_GRAPH",GraphSource.PG_PGQL);
Analyst a = session.createAnalyst();
a.closenessCentralityUnitLength(graph);
PgqlResultSet rs = graph.queryPgql("SELECT DISTINCT m.id, m.closeness FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.closeness DESC LIMIT 5");
rs.print();
>>> graph = session.read_graph_by_name('BANK_GRAPH', 'pg_pgql')
>>> a = session.create_analyst()
>>> a.closeness_centrality(graph)
VertexProperty(name: closeness, type: double, graph: BANK_GRAPH_PGQL)
>>> graph.query_pgql("SELECT DISTINCT m.id, m.closeness FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.closeness DESC LIMIT 5").print()
+-----------------------------+
| id  | closeness             |
+-----------------------------+
| 934 | 3.866976024748647E-4  |
| 135 | 3.8595137012736397E-4 |
| 387 | 3.8476337052712584E-4 |
| 406 | 3.8284839203675346E-4 |
| 330 | 3.7425149700598805E-4 |
+-----------------------------+

親トピック: 中心性アルゴリズム

16.6.3.3 調和中心性

調和中心性アルゴリズムは、切断されたグラフをより適切に考慮するために近接中心性を改善します。

このアルゴリズムは、切断されたグラフの次のシナリオで適用できます:

  • グラフの全体的な構造の中心となるノードを決定し、効率的な情報フローまたは影響の分散を容易にする場合。
  • たとえば、ソーシャル・ネットワーク分析で、情報をネットワーク全体にすばやく広めることができるインフルエンサを特定する場合。
  • たとえば、財務トランザクション分析で、近接中心性が高いアカウントは迅速な資金移動を促進する可能性があるため、マネー・ロンダリングなどの不正行為を厳密に監視するために、このアカウントを潜在的な候補にする場合。
  • たとえば、病気の蔓延を調査する際に、ネットワークの中心的な立場にあるために、病気を他の多くの人にすばやく広める可能性のある個人を特定する場合。
これらのアルゴリズムを実行するための対応するAPIの詳細は、JavadocおよびPython APIリファレンスを参照してください。

例16-4 調和中心性アルゴリズムの実行

次の例では、BANK_GRAPHの各頂点アカウントの調和中心性値を測定し、他のアカウントとのより高いレベルの接続を持つ上位5つのアカウントを出力します。 

opg4j> var graph = session.readGraphByName("BANK_GRAPH",GraphSource.PG_PGQL)
graph ==> PgxGraph[name=BANK_GRAPH,N=1000,E=4996,created=1643308582055]
opg4j> var a = session.createAnalyst()
a ==> NamedArgumentAnalyst[session=4c054326-600d-47d3-ab40-36b41fa0e339]
opg4j> a.harmonicCentrality(graph)
VertexProperty[name=hc,type=double,graph=BANK_GRAPH_PGQL]
opg4j> graph.queryPgql("SELECT DISTINCT m.id, m.hc FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.hc DESC LIMIT 5").print()
+--------------------------+
| id  | hc                 |
+--------------------------+
| 34  | 193.53134920634574 |
| 770 | 193.5238095238061  |
| 778 | 193.41904761904416 |
| 262 | 193.32936507936165 |
| 243 | 192.78293650793313 |
+--------------------------+
$9 ==> PgqlResultSetImpl[graph=BANK_GRAPH_PGQL,numResults=5]
PgxGraph graph = session.readGraphByName("BANK_GRAPH",GraphSource.PG_PGQL);
Analyst a = session.createAnalyst();
a.harmonicCentrality(graph);
PgqlResultSet rs = g1.queryPgql("SELECT DISTINCT m.id, m.hc FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.hc DESC LIMIT 5");
rs.print();
>>> graph = session.read_graph_by_name('BANK_GRAPH', 'pg_pgql')
>>> a = session.create_analyst()
>>> a.harmonic_centrality(graph)
VertexProperty(name: harmonic_centrality, type: double, graph: BANK_GRAPH_PGQL)
>>> graph.query_pgql("SELECT DISTINCT m.id, m.harmonic_centrality FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.harmonic_centrality DESC LIMIT 5").print()
+---------------------------+
| id  | harmonic_centrality |
+---------------------------+
| 34  | 193.3884920634886   |
| 262 | 193.32936507936165  |
| 56  | 193.10158730158386  |
| 544 | 192.87738095237754  |
| 408 | 192.73452380952043  |
+---------------------------+

親トピック: 中心性アルゴリズム

16.6.3.4 頂点媒介中心性

頂点媒介中心性アルゴリズムは、重要なブリッジとして機能するノードを識別し、グラフ内の情報またはリソースのフローを制御します。

このアルゴリズムは、次のシナリオで適用できます:

  • グラフ内の相互作用を仲介するために戦略的に配置されているノードを識別する場合。
  • たとえば、ソーシャル・ネットワーク分析で、様々なグループまたはコミュニティ間のコネクタとして機能するユーザーを強調表示する場合。
  • たとえば、財務トランザクション分析で、財務ネットワークのその他の接続されていない部分間のトランザクションを容易にするアカウントを検出する場合。
  • たとえば、病気の蔓延を調査する際に、異なる社会集団間のブリッジとして機能する個人を識別し、全人口にわたって病気の蔓延を制御する場合。

頂点媒介中心性では、次の3つのバリアントがサポートされています:

  • 頂点媒介中心性: グラフ内の頂点vの媒介中心性は、vがsおよびtと異なるように、グラフ内の可能なすべての頂点sおよびtのペアを接続するすべての可能な最短パスからvを通過する最短パスの割合の合計です。このアルゴリズムは、接続されたグラフに適用されます。
  • 乱数シードを使用した近似頂点媒介中心性: この媒介中心性のバリアントは、グラフ内のすべての頂点を使用して正確な値を計算するのではなく、グラフのBFS横断の開始点としてk個のランダム頂点を使用して、頂点の中心性の近似値を求めます。
  • シードからの近似頂点媒介中心性: この媒介中心性のバリアントは、グラフ内のすべての頂点を使用して正確な値を計算するのではなく、グラフのBFS横断の開始点として特定のシーケンスからの頂点を使用して、頂点の中心性の近似値を求めます。
これらのアルゴリズムを実行するための対応するAPIの詳細は、JavadocおよびPython APIリファレンスを参照してください。

例16-5 媒介中心性アルゴリズムの実行

次の例では、グラフg1で重要なブリッジとして機能する上位5つのアカウントを識別します。 

opg4j> var graph = session.readGraphByName("BANK_GRAPH",GraphSource.PG_PGQL)
graph ==> PgxGraph[name=BANK_GRAPH,N=1000,E=4996,created=1643308582055]
opg4j> var a = session.createAnalyst()
a ==> NamedArgumentAnalyst[session=4c054326-600d-47d3-ab40-36b41fa0e339]
opg4j> a.vertexBetweennessCentrality(graph)
$10 ==> VertexProperty[name=betweenness,type=double,graph=BANK_GRAPH_PGQL]
opg4j> graph.queryPgql("SELECT DISTINCT m.id, m.betweenness FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.betweenness DESC LIMIT 5").print()
+--------------------------+
| id  | betweenness        |
+--------------------------+
| 387 | 18913.34886094081  |
| 352 | 16625.818593102595 |
| 135 | 15190.461087012543 |
| 934 | 14642.317059371073 |
| 222 | 13688.935057639192 |
+--------------------------+
$11 ==> PgqlResultSetImpl[graph=BANK_GRAPH_PGQL,numResults=5]
PgxGraph graph = session.readGraphByName("BANK_GRAPH",GraphSource.PG_PGQL);
Analyst a = session.createAnalyst();
a.vertexBetweennessCentrality(graph);
PgqlResultSet rs = g1.queryPgql("SELECT DISTINCT m.id, m.betweenness FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.betweenness DESC LIMIT 5");
rs.print();
>>> graph = session.read_graph_by_name('BANK_GRAPH', 'pg_pgql')
>>> a = session.create_analyst()
>>> a.vertex_betweenness_centrality(graph)
VertexProperty(name: betweenness, type: double, graph: BANK_GRAPH_PGQL)
>>> graph.query_pgql("SELECT DISTINCT m.id, m.betweenness FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.betweenness DESC LIMIT 5").print()
+--------------------------+
| id  | betweenness        |
+--------------------------+
| 387 | 18913.34886094081  |
| 352 | 16625.818593102595 |
| 135 | 15190.461087012543 |
| 934 | 14642.317059371073 |
| 222 | 13688.935057639192 |
+--------------------------+

親トピック: 中心性アルゴリズム

16.6.3.5 PageRank

PageRankは各頂点に数値の重みを割り当て、グラフ内の相対的な重要性を測定します。

このアルゴリズムは、次のシナリオで適用できます:

  • 他のノードに直接的および間接的に影響を与えるノードを識別する場合。
  • 固有ベクトル中心性のかわりに、基礎となるプロセスにランダム性が含まれる場合(ランダムな参照など)。
  • たとえば、ソーシャル・ネットワーク分析で、グラフ内で直接的および間接的な影響力を持つインフルエンサを見つける場合。
  • たとえば、病気の蔓延の分析で、病気の蔓延における個人のリスクを評価する場合。

PageRankは、グラフ内のそれぞれの頂点(ノード)について0から1の間のランク値を計算し、その値をdoubleプロパティに格納します。このため、アルゴリズムによって、出力に対してタイプdoubleの頂点プロパティが作成されます。

グラフ・サーバー(PGX)には、頂点プロパティとエッジ・プロパティの2つのタイプがあります。

  • 永続プロパティ: データ・ソースからグラフとともにロードされ固定されたディスク上のデータのインメモリー・コピーであるため、永続となるプロパティ。永続プロパティは読取り専用のため変更できず、セッション間で共有されます。

  • 一時プロパティ: 値が書き込めるのは一時プロパティのみで、これらはセッションに対してプライベートです。一時プロパティを作成するには、PgxGraphオブジェクトでcreateVertexPropertyおよびcreateEdgePropertyをコールするか、プロパティ・オブジェクトでclone()を使用して既存のプロパティをコピーします。

    一時プロパティには、アルゴリズムによる計算結果が保持されます。たとえば、PageRankアルゴリズムでは、グラフ内の頂点ごとに0から1の間のランク値を計算し、これらの値をpg_rankという一時プロパティに格納します。一時プロパティは、アナリスト・オブジェクトが破棄されると破棄されます。

次のPageRankアルゴリズムのバリアントがサポートされています:

  • クラシックPageRank: グラフ内の入力エッジによって作成されたネットワークを使用して、頂点のランキング・スコアを計算します。有向グラフを対象としていますが、無向グラフは、往復のエッジを持つ有向グラフに変換(つまり、元のエッジを保持し、反対方向に進む2番目のエッジを作成)することによっても処理できます。
  • 近似PageRank: 累積頂点エラーを見るのではなく、許容エラー値がグラフ内の各頂点と比較されるため、正規化なしで、より緩和された収束基準を使用して、クラシック・アルゴリズムと同様の方法で頂点のランキング・スコアを計算します。したがって、このバリアントはクラシック・アルゴリズムより速く収束しますが、ランキング値はクラシック実装ほど正確でない場合があります。
  • 重み付きPageRank: クラシックPageRankアルゴリズムと同様ですが、各エッジに重み値を割り当てることができます。この重みによって、ソース頂点から現在のエッジを経由して宛先頂点まで流れるPageRankスコアの割合が決まります。
これらのアルゴリズムを実行するための対応するAPIの詳細は、JavadocおよびPython APIリファレンスを参照してください。

例16-6 PageRankアルゴリズムの実行

次の例では、BANK_GRAPHでPageRankアルゴリズムを実行して、PageRank値が最も高い上位5つのアカウントを識別します。PageRankアルゴリズムでは入力パラメータに次のデフォルト値を使用します。エラー許容値 = 0.001、減衰係数 = 0.85および最大反復数 = 100です。 

opg4j> var graph = session.readGraphByName("BANK_GRAPH",GraphSource.PG_PGQL)
graph ==> PgxGraph[name=BANK_GRAPH,N=1000,E=4996,created=1643308582055]
opg4j> var a = session.createAnalyst()
a ==> NamedArgumentAnalyst[session=4c054326-600d-47d3-ab40-36b41fa0e339]
opg4j> a.pagerank(graph, 0.001, 0.85, 100)
$12 ==> VertexProperty[name=pagerank,type=double,graph=BANK_GRAPH_PGQL]
opg4j> graph.queryPgql("SELECT DISTINCT m.id, m.pagerank FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.pagerank DESC LIMIT 5").print()
+-----------------------------+
| id  | pagerank              |
+-----------------------------+
| 387 | 0.0073028362522059255 |
| 406 | 0.0067344306145590786 |
| 135 | 0.006725965475577352  |
| 934 | 0.0066413407648344865 |
| 397 | 0.0057016075312134595 |
+-----------------------------+
$13 ==> PgqlResultSetImpl[graph=BANK_GRAPH_PGQL,numResults=5]
PgxGraph graph = session.readGraphByName("BANK_GRAPH",GraphSource.PG_PGQL);
Analyst a = session.createAnalyst();
a.pagerank(graph, 0.001, 0.85, 100);
PgqlResultSet rs = g1.queryPgql("SELECT DISTINCT m.id, m.pagerank FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.pagerank DESC LIMIT 5");
rs.print();
>>> graph = session.read_graph_by_name('BANK_GRAPH', 'pg_pgql')
>>> a = session.create_analyst()
>>> a.pagerank(graph, 0.001, 0.85, 100)
VertexProperty(name: pagerank, type: double, graph: BANK_GRAPH_PGQL)
>>> graph.query_pgql("SELECT DISTINCT m.id, m.pagerank FROM MATCH (m:accounts) -[e:transfers]-> (n:accounts) ORDER BY m.pagerank DESC LIMIT 5").print()
+-----------------------------+
| id  | pagerank              |
+-----------------------------+
| 387 | 0.0073028362522059255 |
| 406 | 0.0067344306145590786 |
| 135 | 0.006725965475577352  |
| 934 | 0.0066413407648344865 |
| 397 | 0.0057016075312134595 |
+-----------------------------+

親トピック: 中心性アルゴリズム