Spanner Graph は、Google Research Graph Mining と緊密に連携して、次のユースケースのグラフ分析ニーズに対応するアルゴリズム スイートを提供します。
中心性
中心性アルゴリズムは、グラフ内の構造上の重要度に基づいてノードをランク付けします。これにより、フィンテックの不正なアカウント、ソーシャル グラフのインフルエンサー、通信ネットワークの重要なルーターなどを特定できます。
PageRank
PageRank は、重要度に基づいてノードをスコアリングします。他の重要なノードからリンクされているノードは、より重要であると見なされます。このアルゴリズムは、グラフ内のランダム ウォークをシミュレートします。このウォークでより頻繁にアクセスされるノードは、より重要と見なされます。アルゴリズムの詳細については、ページランクをご覧ください。
関数の署名
PageRank(input_parameters) YIELD node, score
入力パラメータ
すべての共通入力パラメータと次のパラメータ:
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| source_nodes | グラフノードの配列 | × | （なし） | 存在する場合、パーソナライズされた PageRank のソース。 |
| damping_factor | double | × | 0.85 | 特定のイテレーションで、アルゴリズムが現在のノードの発信エッジの 1 つをトラバースする確率。[0, 1) の範囲内にしてください。 |
| max_iterations | int | × | 10 | アルゴリズムの最大反復回数。正の値を指定する必要があります。反復回数が多いほど、実行時間が長くなりますが、結果の精度は高くなります。 |
| approx_precision | double | × | 1e-2 | アルゴリズムの近似精度しきい値。負の値は使用できません。値が小さいほど、実行時間が長くなる代わりに、より正確な結果が得られる傾向があります。 |
出力
関数の yield:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | 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, centrality
入力パラメータ
すべての共通入力パラメータと次のパラメータ:
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| num_source_nodes | INT64 | × | （なし） | 設定する場合は正の数にする必要があり、近似中心性の計算でアルゴリズムが選択するソースノードの数を指定します。設定されていない場合、またはグラフ内のノード数よりも大きい数値に設定されている場合、すべてのノードがソースノードとして使用されます。つまり、アルゴリズムは正確な媒介中心性を計算します。値が大きいほど近似値の精度は高くなりますが、実行時間も長くなります。 |
出力
関数の yield:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | 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, centrality
RETURN node.id, centrality;
ClosenessCentrality
ClosenessCentrality は、グラフ内の他のすべてのノードに対するノードの近さを測定します。近接中心性の高いノードは、より短いパスで他のノードに到達できます。アルゴリズムの詳細については、中心性をご覧ください。
関数の署名
ClosenessCentrality(input_parameters) YIELD node, centrality
入力パラメータ
すべての共通入力パラメータと次のパラメータ:
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| モード | STRING | × | EXACT | アルゴリズム モード。サポートされる値は 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 は入力グラフのノード数です。 |
出力
関数の yield:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | 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, centrality
RETURN node.id, centrality;
クラスタリング
クラスタリング アルゴリズムは、各クラスタ内のノードが他のクラスタ内のノードよりも相互に密接に接続されるように、ノードをクラスタ（コミュニティとも呼ばれます）にグループ化します。これは、フィンテックで潜在的な不正グループを検出したり、小売業で顧客セグメンテーションを特定したりするのに役立ちます。
WeaklyConnectedComponents
WeaklyConnectedComponents は、セット内のすべてのノードが同じセット内の他のノードから到達可能であり、他のセット内のノードからは到達できないような、ノードの互いに素なセットを見つけます。アルゴリズムの詳細については、接続されたコンポーネントをご覧ください。
関数の署名
WeaklyConnectedComponents(input_parameters) YIELD node, cluster
入力パラメータ
すべての一般的な入力パラメータ。
出力
関数の yield:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | 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 | double | × | 1.0 | クラスタリングの粒度を制御します。有限で非負の値にする必要があります。解像度の値が小さいほど、クラスタが大きくなる傾向があります。一般的な値は [0.5, 5] の範囲内です。解像度がゼロの場合、アルゴリズム（十分な数の反復処理）はグラフの連結成分を検出します（重みがゼロのエッジは無視されます）。 |
| max_iterations | int | × | 10 | アルゴリズムの外部反復の最大数。正の値を指定する必要があります。値が大きいほど、実行時間が長くなる代わりに、クラスタリングの品質が高くなる傾向があります。 |
| max_inner_iterations | int | × | 10 | アルゴリズムの内部反復処理の最大数。正の値を指定する必要があります。値が大きいほど、実行時間が長くなる代わりに、クラスタリングの品質が高くなる傾向があります。 |
出力
関数の yield:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | 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 | double | ○ | （なし） | クラスタリングの粒度を制御します。クライアントによって明示的に定義される必要があります。有限で非負の値にする必要があります。値が小さいほど、クラスタが大きくなる傾向があります。解像度がゼロで、すべてのエッジの重みが正の場合、アルゴリズム（十分な数の反復処理）はグラフの連結成分を見つけます。 |
| max_iterations | int | × | 10 | アルゴリズムの外部反復の最大数。正の値を指定する必要があります。値が大きいほど、実行時間が長くなる代わりに、クラスタリングの品質が高くなる傾向があります。 |
| max_inner_iterations | int | × | 10 | アルゴリズムの内部反復処理の最大数。正の値を指定する必要があります。値が大きいほど、実行時間が長くなる代わりに、クラスタリングの品質が高くなる傾向があります。 |
出力
関数の yield:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | 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 | 文字列 | × | （なし） | シードラベルのノード プロパティ名。 |
| max_iterations | int | × | 10 | アルゴリズムが実行するラベル伝播の最大反復回数。有限で正の値にする必要があります。 |
出力
関数の yield:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | 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 つのクラスタに含まれるようにします。アルゴリズムの詳細については、クリーク アグリゲータをご覧ください。
関数の署名
CliqueFinding(input_parameters) YIELD node, clique
注: ほとんどのアルゴリズムとは異なり、ノードは多くのクリークの一部である可能性があるため、同じノードに対して複数の行が存在する可能性があります。
入力パラメータ
すべての共通入力パラメータと次のパラメータ:
| 名前 | 型 | 必須 | デフォルト | 説明 |
|---|---|---|---|---|
| min_density | double | × | 0.9 | 返されるクラスタの最小密度。[0, 1] の範囲内にする必要があります。 |
出力
関数の yield:
| 名前 | タイプ | 説明 |
|---|---|---|
| ノード | 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 | ノードの配列 | ○ | なし |
出力
関数の yield:
| 名前 | タイプ | 説明 |
|---|---|---|
| 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 | ノードの配列 | ○ | なし |
出力
関数の yield:
| 名前 | タイプ | 説明 |
|---|---|---|
| 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;