Spanner Graph 與 Google 研究 Graph Mining 密切合作，提供一系列演算法，可滿足下列用途的圖形分析需求：
中心度
中心度演算法會根據節點在圖表中的結構重要性進行排名。 有助於識別金融科技中的詐欺帳戶、社交關係圖中的網紅、電信網路中的重要路由器等。
PageRank
PageRank 依重要性為節點評分。如果許多其他重要節點都連結至某個節點，該節點就會被視為更重要。演算法會模擬圖形中的隨機漫步。如果節點在這次走訪中較常被造訪，就會被視為較重要。如要瞭解演算法詳情，請參閱網頁排名。
函式簽章
PageRank(input_parameters) YIELD node, score
輸入參數
所有常見輸入參數，以及：
| 名稱 | 類型 | 必填 | 預設 | 說明 |
|---|---|---|---|---|
| source_nodes | 圖表節點陣列 | 否 | (無) | 如有，則為個人化 PageRank 的來源。 |
| damping_factor | 雙精度值 | 否 | 0.85 | 在任何疊代中，演算法選擇遍歷目前節點其中一個外向邊的機率。必須介於 [0, 1) 的範圍之間。 |
| max_iterations | 整數 | 否 | 10 | 演算法的疊代次數上限。必須為正數。 疊代次數越多，結果越精確，但執行時間會較長。 |
| approx_precision | 雙精度值 | 否 | 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, centrality
輸入參數
所有常見輸入參數和：
| 名稱 | 類型 | 必填 | 預設 | 說明 |
|---|---|---|---|---|
| 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, 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 緊密中心度。 |
| epsilon | 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, centrality
RETURN node.id, centrality;
分群
叢集演算法會將節點分組為叢集 (也稱為社群)，讓每個叢集內的節點彼此間的連結密度，高於與其他叢集內節點的連結密度。這項技術有助於偵測金融科技領域的潛在詐欺集團、識別零售業的顧客區隔等等。
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
輸入參數
所有常見輸入參數，以及：
| 名稱 | 類型 | 必填 | 預設 | 說明 |
|---|---|---|---|---|
| 解決方式 | 雙精度值 | 否 | 1.0 | 控制叢集化的精細程度。必須為有限值且不得為負數。解析度值越小，叢集越大。 一般值介於 [0.5, 5] 之間。如果解析度為零，演算法 (經過足夠的疊代次數) 會找出圖譜的連通元件 (忽略權重為零的邊緣)。 |
| max_iterations | 整數 | 否 | 10 | 演算法外部疊代次數上限。必須為正數。 值越大，叢集品質通常越高，但執行時間會較長。 |
| max_inner_iterations | 整數 | 否 | 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
輸入參數
所有常見輸入參數，以及：
| 名稱 | 類型 | 必填 | 預設 | 說明 |
|---|---|---|---|---|
| 解決方式 | 雙精度值 | 是 | (無) | 控制叢集化的精細程度。必須由用戶端明確定義。必須為有限的非負數。值越小，叢集越大。如果解析度為零，且所有邊緣權重都是正數，演算法 (經過足夠的疊代次數) 會找出圖表的連線元件。 |
| max_iterations | 整數 | 否 | 10 | 演算法外部疊代次數上限。必須為正數。 值越大，叢集品質通常越高，但執行時間會較長。 |
| max_inner_iterations | 整數 | 否 | 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 | 字串 | 否 | (無) | 種子標籤的節點屬性名稱。 |
| max_iterations | 整數 | 否 | 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 識別出符合最低密度門檻的潛在重疊密集社群，確保每個集團 (節點群組，其中每個節點都連線至其他節點) 至少包含在一個叢集中。如要瞭解演算法詳細資料，請參閱「集團匯總器」。
函式簽章
CliqueFinding(input_parameters) YIELD node, clique
注意：與大多數演算法不同，同一個節點可能有多個資料列，因為節點可能屬於多個集團。
輸入參數
所有常見輸入參數，以及：
| 名稱 | 類型 | 必填 | 預設 | 說明 |
|---|---|---|---|---|
| min_density | 雙精度值 | 否 | 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：根據至少一個節點的鄰居數量
如需演算法詳細資料，請參閱成對節點相似度。
這四個演算法共用相同的引數和輸出結構。
函式簽章
[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;