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

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

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

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

ノート:

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

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

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

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

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

16.5.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.5.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.5.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());
}

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