Spanner Graph 與 Google 研究 Graph Mining 密切合作，提供一套演算法，可滿足下列用途的圖形分析需求：
中心性
中心性演算法會根據節點在圖中的結構重要性進行排名。可協助您找出金融科技中的詐欺帳戶、社交關係圖中的影響者、電信網路中的重要路由器等。
PageRank
PageRank 會依重要性為節點評分。如果許多其他重要節點都連結至某個節點，該節點的重要性就會提高。演算法會模擬圖中的隨機漫步。在這項隨機漫步中，造訪頻率較高的節點會視為較重要。如要瞭解演算法詳情，請參閱網頁排名。
函式簽章
PageRank(input_parameters) YIELD node, score
輸入參數
所有常見輸入參數，以及：
| 名稱 | 類型 | 必填 | 預設 | 說明 |
|---|---|---|---|---|
| source_nodes | 圖表節點陣列 | 否 | (無) | 如有，則為個人化 PageRank 的來源。 |
| damping_factor | FLOAT64 | 否 | 0.85 | 在任何特定疊代中，演算法選擇周遊目前節點其中一個傳出邊緣的機率。必須介於 [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 | 演算法模式。支援的值為 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, 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] 之間。當解析度為零時，演算法 (經過足夠的疊代次數) 會找出圖表的連線元件 (忽略權重為零的邊緣)。 |
| 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 | 是 | (無) | 控制分群的精細程度。必須由用戶端明確定義。必須為有限且非負數。值越小，叢集通常越大。如果解析度為零，且所有邊緣權重均為正值，演算法 (經過足夠的疊代次數) 會找出圖表的連結元件。 |
| 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 會找出可能重疊且符合最低密度門檻的密集社群，確保每個 clique (一組節點，其中每個節點都與其他節點相連) 至少包含在一個叢集中。如要瞭解演算法詳情，請參閱集團匯總工具。
函式簽章
CliqueFinding(input_parameters) YIELD node, clique
注意：與大多數演算法不同，同一個節點可能會有多個資料列，因為節點可能屬於多個集團。
輸入參數
所有常見輸入參數，以及：
| 名稱 | 類型 | 必填 | 預設 | 說明 |
|---|---|---|---|---|
| min_density | FLOAT64 | 否 | 0.9 | 要傳回的叢集密度下限。必須介於 [0, 1] 之間。 |
輸出內容
函式產生：
| 名稱 | 類型 | 說明 |
|---|---|---|
| 節點 | GRAPH_ELEMENT (節點) | 圖表中的節點。 |
| clique | INT64 | 節點所屬的 clique 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;