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

16.6 組込みアルゴリズムの実行

グラフ・サーバー(PGX)には、一連の組込みアルゴリズムが含まれており、Java APIとして使用できます。

次の表に、使用可能なアルゴリズムの概要をカテゴリ別に示します。これらのアルゴリズムは、Analystクラスを介して起動できます。

ノート:

詳細は、GitHubのサポートされている組込みアルゴリズムを参照してください。

表16-11 組込みアルゴリズムの概要

カテゴリ アルゴリズム
クラシック・グラフ・アルゴリズム プリム法
コミュニティ検出 コンダクタンス最小化(SomanおよびNarangアルゴリズム)、Infomap、ラベル伝播、Louvain、LouvainDirected、スピーカ・リスナー・ラベル伝播
接続されたコンポーネント 強力に接続されたコンポーネント、弱く接続されたコンポーネント(WCC)
リンク予測 Whom To Follow (WTF)アルゴリズム
行列因数分解 行列因数分解
その他 グラフ・トラバース・アルゴリズム
パス検索 フィルタされたパス上のすべての頂点およびエッジ、ベルマン–フォード法、双方向ダイクストラ法、距離指標計算、高次頂点計算、ダイクストラ法、列挙単純パス、高速パス検索、最大フロー・パス、最大フロー・パス(エッジ方向を無視)、フィルタされた高速パス検索、ホップ距離アルゴリズム
ランキングとウォーキング ArticleRankアルゴリズム、近接中心性アルゴリズム、次数中心性アルゴリズム、固有ベクトル中心性、調和中心性、Hyperlink-Induced Topic Search (HITS)、PageRankアルゴリズム、Random Walk with Restart、Stochastic Approach for Link-Structure Analysis (SALSA)アルゴリズム、頂点媒介中心性アルゴリズム
構造評価 Adamic-Adarアルゴリズム、Bipartite Check、クラスタ係数アルゴリズム、コンダクタンス、循環検出アルゴリズム、次数分布アルゴリズム、離心性アルゴリズム、K-コア、モジュール性、パーティション・コンダクタンス、到達可能性アルゴリズム、Topological Orderingアルゴリズム、トライアングル・カウンティング・アルゴリズム

次のトピックでは、例としてトライアングル・カウンティングおよびPageRank分析を使用したグラフ・サーバー(PGX)の使用について説明します。

親トピック: グラフ分析を使用したアプリケーションの開発

16.6.1 グラフ・サーバー(PGX)での組込みアルゴリズムについて

グラフ・サーバー(PGX)には、一連の組込みアルゴリズムが含まれており、Java APIとして使用できます。APIの詳細は、製品のドキュメント・ライブラリに同梱されているJavadocに記載されています。特に、サポートされているインメモリー・アナリスト・メソッドのリストについては、BuiltinAlgorithmsインタフェースのメソッド・サマリーを参照してください。

たとえば、PageRankプロシージャの署名は次のとおりです。

/**
   * Classic pagerank algorithm. Time complexity: O(E * K) with E = number of edges, K is a given constant (max
   * iterations)
   *
   * @param graph
   *          graph
   * @param e
   *          maximum error for terminating the iteration
   * @param d
   *          damping factor
   * @param max
   *          maximum number of iterations
   * @return Vertex Property holding the result as a double
   */
  public <ID extends Comparable<ID>> VertexProperty<ID, Double> pagerank(PgxGraph graph, double e, double d, int max);

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

16.6.2 トライアングル・カウンティング・アルゴリズムの実行

トライアングル・カウンティングの場合、countTriangles()のsortByDegreeブール・パラメータを使用して、グラフを最初に角度でソートする(true)かソートしない(false)かを制御できます。trueの場合、さらに多くのメモリーが使用されますが、アルゴリズムの実行は高速になります。ただし、グラフが非常に大きい場合、この最適化をオフにしてメモリー不足を回避することができます。 

opg4j> analyst.countTriangles(graph, true)
==> 1
import oracle.pgx.api.*;
 
Analyst analyst = session.createAnalyst();
long triangles = analyst.countTriangles(graph, true);

このアルゴリズムでは、サンプル・グラフ内の1つのトライアングルを検出します。

ヒント:

グラフ・シェルを使用する場合、ロギング・レベルを変更すると、実行中のログ出力の量を増加できます。:h :loglevelを指定した:loglevelコマンドの実行に関する情報を参照してください。

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

16.6.3 PageRankアルゴリズムの実行

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

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

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

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

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

この例では、PageRank値が最も高い上位3つの頂点を取得します。タイプdoubleの一時頂点プロパティを使用して、計算したPageRank値を保持します。PageRankアルゴリズムでは入力パラメータに次のデフォルト値を使用します。エラー許容値 = 0.001、減衰係数 = 0.85および最大反復数 = 100です。 

opg4j> rank = analyst.pagerank(graph, 0.001, 0.85, 100);
==> ...
opg4j> rank.getTopKValues(3)
==> 128=0.1402019732468347
==> 333=0.12002296283541904
==> 99=0.09708583862990475

import java.util.Map.Entry;
import oracle.pgx.api.*;
 
Analyst analyst = session.createAnalyst();
VertexProperty<Integer, Double> rank = analyst.pagerank(graph, 0.001, 0.85, 100);
for (Entry<Integer, Double> entry : rank.getTopKValues(3)) {
 System.out.println(entry.getKey() + "=" + entry.getValue());
}

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

16.6.4 実行中のアルゴリズムの進行状況の取得

グラフ・アルゴリズムの進行状況は単調に増加するカウンタの値に基づきます。カウンタの値はアルゴリズムの実行中に定期的に増加します。AlgorithmProgress Java APIを使用してアルゴリズムの進行状況を追跡し、様々な時点のカウンタ値とカウンタの最終予測値とを比較して、アルゴリズムの進行状況を確認できます。

AlgorithmProgressオブジェクトは、特定の時点でのアルゴリズム実行の進行状況を表します。これには、次の2つの属性が含まれています:

  • numberOfStepsCompleted: このカウンタは、現在までに実行されたステップ数を表します。
  • numberOfStepsEstimatedForCompletion: この値は、完了までに必要とされるステップの合計数の見積りです。

    次に示す組込みアルゴリズムでは、numberOfStepsEstimatedForCompletionにデフォルトの正の値が指定されます。

    • PageRank
    • 近似PageRank
    • パーソナライズされたPageRank
    • パーソナライズされたPageRank (頂点のセットに対する)
    • パーソナライズされた加重PageRank
    • パーソナライズされた加重PageRank (頂点のセットに対する)
    • 加重PageRank
    • 次数中心性
    • 入次数中心性
    • 出次数中心性

numberOfStepsEstimatedForCompletionの値を提供しないアルゴリズムの場合、進行状況をパーセントとして見積もることはできません。このような場合、アクセスできるのはカウンタの値(numberOfStepsCompleted)のみです。

ただし、カスタムPGXグラフ・アルゴリズムにはnumberOfStepsEstimatedForCompletion値を設定できます。詳細は、「実行中のカスタムPGXグラフ・アルゴリズムの進行状況の追跡」を参照してください。

次は、組込みのPageRankアルゴリズムを使用する例です。AlgorithmProgress Java APIを使用して実行中の組込みアルゴリズムの進行状況を取得するステップを示しています。 

opg4j> var graph = session.readGraphByName("BANK_TXN_GRAPH", GraphSource.PG_PGQL)
g ==> PgxGraph[name=BANK_TXN_GRAPH,N=1000,E=4993,created=1712307339271]
opg4j>  var future = analyst.pagerankAsync(graph)
future ==> oracle.pgx.api.PgxFuture@1dfe5dd1[Not completed]
opg4j> var futureProgress = future.getProgress()
futureProgress ==> oracle.pgx.api.DefaultFutureProgress@6d7bb5cc
opg4j> var algorithmProgress = futureProgress.asAlgorithmExecutionProgress()
PgxGraph graph = session.readGraphByName("BANK_TXN_GRAPH", GraphSource.PG_PGQL);
PgxFuture<?> future = analyst.pagerank.runAsync(graph);
FutureProgress futureProgress = future.getProgress();
Optional<AlgorithmProgress> algorithmProgress = futureProgress.asAlgorithmExecutionProgress();

次のコードは、実行中のアルゴリズムの進行状況をパーセンテージとして見積もる方法を示しています。

opg4j> if (algorithmProgress.isPresent()) {
...>   var progress = algorithmProgress.get();
...>   var completedSteps = progress.getNumberOfStepsCompleted();
...>   var numberOfStepsEstimatedForCompletion = progress.getNumberOfStepsEstimatedForCompletion();
...>   var progressPercentage = completedSteps * 100 / numberOfStepsEstimatedForCompletion;
...>   System.out.println(completedSteps);
...>   System.out.println(numberOfStepsEstimatedForCompletion);
...>   System.out.println(progressPercentage);
...> }
if (algorithmProgress.isPresent()) {
  AlgorithmProgress progress = algorithmProgress.get();
  long completedSteps = progress.getNumberOfStepsCompleted();
  Long numberOfStepsEstimatedForCompletion = progress.getNumberOfStepsEstimatedForCompletion();
  long progressPercentage = completedSteps * 100 / numberOfStepsEstimatedForCompletion;
  System.out.println(completedSteps); 
  System.out.println(numberOfStepsEstimatedForCompletion); 
  System.out.println(progressPercentage); 
};

前述のコードは、現時点での進行状況を示しています。しばらくしてから実行中のアルゴリズムの進行状況(たとえば、1min)を取得すると、progressPercentageの値が大きくなっていることを確認できます。

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