Spanner Graph は、Google Research Graph Mining との緊密な連携により、次のユースケースのグラフ分析ニーズに対応するアルゴリズム スイートを提供しています。
中心性
中心性アルゴリズムは、グラフ内の構造上の重要度に基づいてノードをランク付けします。これにより、フィンテックの不正なアカウント、ソーシャル グラフのインフルエンサー、通信ネットワークの重要なルーターなどを特定できます。
PageRank
PageRank は、重要度によってノードをスコア付けします。他の重要なノードが多数リンクしているノードは、より重要と見なされます。このアルゴリズムは、グラフをランダムに移動するシミュレーションを行います。このウォークでより頻繁にアクセスされるノードは、より重要と見なされます。アルゴリズムの詳細については、ページランクをご覧ください。
関数の署名
PageRank(input_parameters) YIELD node, score
入力パラメータ
すべての共通入力パラメータと、次のパラメータ。
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| source_nodes | グラフノードの配列 | いいえ | （なし） | 存在する場合、パーソナライズされた PageRank のソース。 |
| damping_factor | FLOAT64 | いいえ | 0.85 | 特定の反復で、アルゴリズムが現在のノードの発信エッジの 1 つをトラバースする確率。[0, 1] の範囲内にしてください。 |
| max_iterations | INT64 | いいえ | 10 | アルゴリズムの反復処理の最大数。正の数でなければなりません。反復回数が多いほど、実行時間が長くなる代わりに、より正確な結果が得られる傾向があります。 |
| approx_precision | FLOAT64 | いいえ | 1e-2 | アルゴリズムの近似精度のしきい値。負の値は使用できません。値が小さいほど、実行時間が長くなる代わりに、より正確な結果が得られる傾向があります。 |
出力
関数の出力:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | GRAPH_ELEMENT（ノード） | グラフ内のノード。 |
| スコア | FLOAT64 | ノードの PageRank スコア。 |
例
EXPORT DATA OPTIONS (
uri = "gs://my-bucket-name/my-output.csv",
format = "csv"
) AS
GRAPH FinGraph
CALL PageRank(
node_labels => ['Account'], edge_labels => ['Transfers'],
source_nodes => ARRAY {
MATCH (n:Account {id:7})
RETURN n
}
) YIELD node, score
RETURN node.id, score;
BetweennessCentrality
BetweennessCentrality は、ノードが他のノードペア間の最短パス上に存在する頻度を測定します。媒介中心性が高いノードは、グラフのさまざまな部分を接続する重要なブリッジとして機能することがよくあります。アルゴリズムの詳細については、媒介中心性をご覧ください。
関数の署名
BetweennessCentrality(input_parameters) YIELD node, score
入力パラメータ
すべての一般的な入力パラメータと次のパラメータ:
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| num_source_nodes | INT64 | いいえ | （なし） | 設定する場合は正の値を指定する必要があります。この値は、近似媒介中心性を計算するためにアルゴリズムが選択するソースノードの数を指定します。設定されていない場合、またはグラフ内のノード数よりも大きい数値に設定されている場合、すべてのノードがソースノードとして使用されます。つまり、アルゴリズムは正確な媒介中心性を計算します。値が大きいほど近似値は向上しますが、実行時間も長くなります。 |
出力
関数の出力:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | GRAPH_ELEMENT（ノード） | グラフ内のノード。 |
| スコア | FLOAT64 | ノードの中心性スコア。 |
例
EXPORT DATA OPTIONS (
uri = "gs://my-bucket-name/my-output.csv",
format = "csv"
) AS
GRAPH FinGraph
CALL BetweennessCentrality(
node_labels => ['Account'], edge_labels => ['Transfers'], num_source_nodes => 5
) YIELD node, score
RETURN node.id, score;
ClosenessCentrality
ClosenessCentrality は、ノードがグラフ内の他のすべてのノードにどれだけ近いかを測定します。近接中心性が高いノードは、より短いパスで他のノードに到達できます。アルゴリズムの詳細については、近接中心性をご覧ください。
関数の署名
ClosenessCentrality(input_parameters) YIELD node, score
入力パラメータ
すべての共通入力パラメータと、次のパラメータ。
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| モード | STRING | いいえ | 完全一致 | アルゴリズム モード。サポートされる値は EXACT と HYBRID です。 |
| use_wasserman_faust | BOOL | いいえ | FALSE | false の場合、標準の近接中心性を計算します。true の場合、Wasserman-Faust 近接中心性を計算します。 |
| イプシロン | FLOAT64 | いいえ | 0.1 | HYBRID アルゴリズムでのみ使用されます。(0.0, 1.0) の範囲内にしてください。一般に、値が小さいほど精度が高くなります。一般に、値が大きいほどアルゴリズムの実行速度が速くなります。 |
| sample_size | INT64 | いいえ | 0 | HYBRID アルゴリズムにのみ使用されます。中心性の値を概算で計算するために使用するピボット ノードの数。負の値は使用できません。設定されていないかゼロの場合、デフォルト値の min(100 * ln(N), N) が使用されます。ここで、N は入力グラフのノード数です。 |
出力
関数の出力:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | GRAPH_ELEMENT（ノード） | グラフ内のノード。 |
| スコア | FLOAT64 | ノードの近接中心性スコア。 |
例
EXPORT DATA OPTIONS (
uri = "gs://my-bucket-name/my-output.csv",
format = "csv"
) AS
GRAPH FinGraph
CALL ClosenessCentrality(
node_labels => ['Account'], edge_labels => ['Transfers'],
mode => 'EXACT'
) YIELD node, score
RETURN node.id, score;
クラスタリング
クラスタリング アルゴリズムは、各クラスタ内のノードが他のクラスタ内のノードよりも密に接続されるように、ノードをクラスタ（コミュニティとも呼ばれます）にグループ化します。これは、フィンテックでの潜在的な不正行為グループの検出、小売での顧客セグメンテーションの特定などに役立ちます。
WeaklyConnectedComponents
WeaklyConnectedComponents は、セット内のすべてのノードが同じセット内の他のノードから到達可能で、他のセット内のノードからは到達できないように、互いに素なノードのセットを検索します。アルゴリズムの詳細については、連結成分をご覧ください。
関数の署名
WeaklyConnectedComponents(input_parameters) YIELD node, cluster
入力パラメータ
出力
関数の出力:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | GRAPH_ELEMENT（ノード） | グラフ内のノード。 |
| クラスタ | INT64 | ノードが属する接続コンポーネント/クラスタの ID。[0, N) の範囲。ここで、N はグラフ内のノード数です。 |
例
EXPORT DATA OPTIONS (
uri = "gs://my-bucket-name/wcc-output.csv",
format = "csv"
) AS
GRAPH FinGraph
CALL WeaklyConnectedComponents(
node_labels => ['Account'], edge_labels => ['Transfers']
) YIELD node, cluster
RETURN node.id, cluster;
ModularityClustering
ModularityClustering は、ランダム ネットワークで想定される接続密度と比較して、クラスタ内の接続密度を測る品質指標であるモジュラリティを最適化することで、グラフをクラスタに分割します。アルゴリズムの詳細については、モジュール性クラスタリングをご覧ください。
関数の署名
ModularityClustering(input_parameters) YIELD node, cluster
入力パラメータ
すべての共通入力パラメータと、次のパラメータ。
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| resolution | FLOAT64 | いいえ | 1.0 | クラスタリングの粒度を制御します。有限で非負の値にする必要があります。解像度の値が小さいほど、クラスタが大きくなる傾向があります。一般的な値は [0.5, 5] の範囲内です。解像度が 0 の場合、アルゴリズムは（十分な反復回数で）グラフの連結成分を検出します（重みが 0 のエッジは無視されます）。 |
| max_iterations | INT64 | いいえ | 10 | アルゴリズムの外部反復処理の最大数。正の値を指定してください。 値が大きいほど、実行時間が長くなりますが、クラスタリングの品質が高くなる傾向があります。 |
| max_inner_iterations | INT64 | いいえ | 10 | アルゴリズムの内部反復処理の最大数。正の値を指定してください。 値が大きいほど、クラスタリングの品質は高くなりますが、実行時間が長くなります。 |
出力
関数の出力:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | GRAPH_ELEMENT（ノード） | グラフ内のノード。 |
| クラスタ | INT64 | ノードが属するコミュニティ/クラスタの ID。[0, N) の範囲。ここで、N はグラフ内のノード数です。 |
例
EXPORT DATA OPTIONS (
uri = "gs://my-bucket-name/modularity-output.csv",
format = "csv"
) AS
GRAPH FinGraph
CALL ModularityClustering(
node_labels => ['Account'], edge_labels => ['Transfers'],
resolution => 1.0, max_iterations => 10
) YIELD node, cluster
RETURN node.id, cluster;
CorrelationClustering
CorrelationClustering は、ペアワイズの類似性または非類似性に基づいてノードをパーティショニングします。これは、類似したノードをグループ化し、類似していないノードを分離することを目的としています。アルゴリズムの詳細については、相関クラスタリングをご覧ください。
関数の署名
CorrelationClustering(input_parameters) YIELD node, cluster
入力パラメータ
すべての一般的な入力パラメータと次のパラメータ:
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| resolution | FLOAT64 | ○ | （なし） | クラスタリングの粒度を制御します。クライアントが明示的に定義する必要があります。有限で非負の値にする必要があります。値が小さいほど、クラスタが大きくなる傾向があります。解像度が 0 で、すべてのエッジの重みが正の場合、アルゴリズムは（十分な回数の反復処理で）グラフの連結成分を見つけます。 |
| max_iterations | INT64 | いいえ | 10 | アルゴリズムの外部反復処理の最大数。正の値を指定してください。 値が大きいほど、実行時間が長くなりますが、クラスタリングの品質が高くなる傾向があります。 |
| max_inner_iterations | INT64 | いいえ | 10 | アルゴリズムの内部反復処理の最大数。正の値を指定してください。 値が大きいほど、クラスタリングの品質は高くなりますが、実行時間が長くなります。 |
出力
関数の出力:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | GRAPH_ELEMENT（ノード） | グラフ内のノード。 |
| クラスタ | INT64 | ノードが属するコミュニティ/クラスタの ID。[0, N) の範囲。ここで、N はグラフ内のノード数です。 |
例
EXPORT DATA OPTIONS (
uri = "gs://my-bucket-name/correlation-output.csv",
format = "csv"
) AS
GRAPH FinGraph
CALL CorrelationClustering(
node_labels => ['Account'], edge_labels => ['Transfers'],
resolution => 0.5
) YIELD node, cluster
RETURN node.id, cluster;
LabelPropagation
LabelPropagation は、ラベル伝播手法を使用して、入力で提供されたシードラベルを使用する初期ラベル付けから開始して、ノードをクラスタに割り当てます。ノードが近傍の多数派が共有するラベルを繰り返し採用すると、密に接続されたグループが合意ラベルに収束し、コミュニティが形成されます。アルゴリズムの詳細については、ラベル伝播をご覧ください。
関数の署名
LabelPropagation(input_parameters) YIELD node, cluster
入力パラメータ
すべての一般的な入力パラメータと次のパラメータ:
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| seed_label_property | STRING | いいえ | （なし） | シードラベルのノード プロパティ名。 |
| max_iterations | INT64 | いいえ | 10 | アルゴリズムが実行するラベル伝播の最大反復回数。有限の正の値を指定してください。 |
出力
関数の出力:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | GRAPH_ELEMENT（ノード） | グラフ内のノード。 |
| クラスタ | INT64 | ノードの伝播されたクラスタ/ラベル ID。 |
例
EXPORT DATA OPTIONS (
uri = "gs://my-bucket-name/lp-output.csv",
format = "csv"
) AS
GRAPH FinGraph
CALL LabelPropagation(
node_labels => ['Account'], edge_labels => ['Transfers'],
max_iterations => 10
) YIELD node, cluster
RETURN node.id, cluster;
CliqueFinding
CliqueFinding は、最小密度しきい値を満たす、重複する可能性のある高密度コミュニティを識別します。これにより、すべてのクリーク（各ノードが他のすべてのノードに接続されているノードのグループ）が少なくとも 1 つのクラスタに含まれます。アルゴリズムの詳細については、clique アグリゲータをご覧ください。
関数の署名
CliqueFinding(input_parameters) YIELD node, clique
注: ほとんどのアルゴリズムとは異なり、ノードが複数のクリークの一部になる可能性があるため、同じノードに複数の行が存在する場合があります。
入力パラメータ
すべての共通入力パラメータと、次のパラメータ。
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| min_density | FLOAT64 | いいえ | 0.9 | 返されるクラスタの最小密度。[0, 1] の範囲内で指定する必要があります。 |
出力
関数の出力:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | GRAPH_ELEMENT（ノード） | グラフ内のノード。 |
| クリーク | INT64 | ノードが属するクリークの ID。 |
例
EXPORT DATA OPTIONS (
uri = "gs://my-bucket-name/clique-output.csv",
format = "csv"
) AS
GRAPH FinGraph
CALL CliqueFinding(
node_labels => ['Account'], edge_labels => ['Transfers'],
min_density => 0.9
) YIELD node, clique
RETURN node.id, clique;
類似
類似性アルゴリズムは、近傍の構造に基づいてノードのペアの類似性を定量化します。これは、エンティティ解決や推奨事項などでノード間の欠落したエッジを推論する場合に役立ちます。
Spanner Graph は、ノードの近傍に基づいて類似度スコアが計算される、次のペアワイズ ノード類似度をサポートしています。
JaccardSimilarity: 共通の近傍と合計近傍の比率に基づくCosineSimilarity: 共通の近傍のエッジの重みに基づくCommonNeighborsSimilarity: 共有ネイバーの数に基づくTotalNeighborsSimilarity: 2 つのノードの少なくとも 1 つの近傍の数に基づく
アルゴリズムの詳細については、ペアワイズ ノード類似度をご覧ください。
これら 4 つのアルゴリズムは、同じ引数と出力構造を共有します。
関数の署名
[JaccardSimilarity|CosineSimilarity|CommonNeighborsSimilarity|TotalNeighborsSimilarity](input_parameters)
YIELD source_node, target_node, similarity
入力パラメータ
すべての共通入力パラメータと、次のパラメータ。
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| source_nodes | グラフノードの配列 | ○ | なし | ペアワイズ類似度計算のソースノード。 |
| target_nodes | グラフノードの配列 | ○ | なし | ペアワイズ類似度計算のターゲット ノード。 |
出力
関数の出力:
| 名前 | タイプ | 説明 |
|---|---|---|
| source_node | GRAPH_ELEMENT（ノード） | 類似度の計算に使用されるソースノード。 |
| target_node | GRAPH_ELEMENT（ノード） | 類似性計算で使用されるターゲット ノード。 |
| 類似性 | FLOAT64 | 移行元ノードと移行先ノード間で計算された類似性スコア。 |
例
EXPORT DATA OPTIONS (
uri = "gs://my-bucket-name/jaccard-output.csv",
format = "csv"
) AS
GRAPH FinGraph
CALL JaccardSimilarity(
source_nodes => ARRAY {
MATCH (n:Account {id: 7})
RETURN n
},
target_nodes => ARRAY {
MATCH (n:Account)
WHERE n.id != 7
RETURN n
}
) YIELD source_node, target_node, similarity
RETURN source_node.id AS source_id, target_node.id AS target_id, similarity;
経路検索
パス検索アルゴリズムは、ノード間の最適なルートを計算します。これは、サプライ チェーンで最も安価なルートを特定したり、サイバーセキュリティの脆弱性を評価したりする場合に役立ちます。
ShortestPath
ShortestPath は、指定された一連のソースノードと指定された一連のターゲット ノード間の最短パスを計算します。アルゴリズムの詳細については、多対多の最短パスをご覧ください。
関数の署名
ShortestPath(input_parameters) YIELD source_node, target_node, path, cost
入力パラメータ
すべての一般的な入力パラメータと次のパラメータ:
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| source_nodes | グラフノードの配列 | ○ | なし | 最短経路計算のソースノード。 |
| target_nodes | グラフノードの配列 | ○ | なし | 最短経路計算のターゲット ノード。 |
出力
関数の出力:
| 名前 | タイプ | 説明 |
|---|---|---|
| source_node | GRAPH_ELEMENT（ノード） | パスのソースノード。 |
| target_node | GRAPH_ELEMENT（ノード） | パスのターゲット ノード。 |
| パス | GRAPH_PATH | 見つかった最短パス。 |
| 費用 | FLOAT64 | 最短経路の費用。 |
例
EXPORT DATA OPTIONS (
uri = "gs://my-bucket-name/shortest-path-output.csv",
format = "csv"
) AS
GRAPH FinGraph
CALL ShortestPath(
source_nodes => ARRAY {
MATCH (n:Account {id: 7})
RETURN n
},
target_nodes => ARRAY {
MATCH (n:Account {id: 16})
RETURN n
}
) YIELD source_node, target_node, path, cost
RETURN source_node.id AS source_id, target_node.id AS target_id, PATH_LENGTH(path) AS length, cost;