Spanner Graph는 Google 연구팀 Graph Mining과 긴밀하게 협력하여 다음 사용 사례의 그래프 분석 요구사항을 충족하는 알고리즘 모음을 제공합니다.
중심점
중심성 알고리즘은 그래프 내에서 구조적 중요도에 따라 노드의 순위를 지정합니다. 핀테크의 사기 계정, 소셜 그래프의 인플루언서, 통신 네트워크의 중요 라우터 등을 식별하는 데 도움이 됩니다.
PageRank
PageRank는 중요도에 따라 노드에 점수를 매깁니다. 다른 중요한 노드가 많이 연결되어 있는 노드는 더 중요한 것으로 간주됩니다. 이 알고리즘은 그래프를 통한 무작위 탐색을 시뮬레이션합니다. 이 도보에서 더 자주 방문하는 노드가 더 중요한 것으로 간주됩니다. 알고리즘에 관한 자세한 내용은 페이지 순위를 참고하세요.
함수 서명
PageRank(input_parameters) YIELD node, score
입력 매개변수
모든 일반 입력 매개변수 및 다음 항목
| 이름 | 유형 | 필수 | 기본값 | 설명 |
|---|---|---|---|---|
| source_nodes | 그래프 노드 배열 | 아니요 | (없음) | 있는 경우 개인화된 PageRank의 소스입니다. |
| damping_factor | double | 아니요 | 0.85 | 지정된 반복에서 알고리즘이 현재 노드의 나가는 가장자리 중 하나를 통과하도록 선택할 확률입니다. 범위는 [0, 1)이어야 합니다. |
| max_iterations | int | 아니요 | 10 | 알고리즘의 최대 반복 횟수입니다. 양수여야 합니다. 반복 횟수가 많을수록 런타임이 길어지지만 결과가 더 정확해지는 경향이 있습니다. |
| approx_precision | double | 아니요 | 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
입력 매개변수
모든 일반 입력 매개변수 및 다음 항목
| 이름 | 유형 | 필수 | 기본값 | 설명 |
|---|---|---|---|---|
| 모드 | 문자열 | 아니요 | 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` 알고리즘에만 사용됩니다. 중심성 값을 대략적으로 계산하는 데 사용할 피벗 노드 수입니다. Must be non-negative.
설정되지 않았거나 0인 경우 기본값 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
입력 매개변수
모든 일반 입력 매개변수 및 다음 항목
| 이름 | 유형 | 필수 | 기본값 | 설명 |
|---|---|---|---|---|
| resolution | double | 아니요 | 1.0 | 클러스터링의 세부사항을 제어합니다. 유한하고 음수가 아니어야 합니다. 해상도 값이 작을수록 클러스터가 커지는 경향이 있습니다. 일반적인 값은 [0.5, 5] 범위에 있습니다. 해상도가 0이면 알고리즘(반복 횟수가 충분한 경우)이 가중치가 0인 가장자리를 무시하고 그래프의 연결된 구성요소를 찾습니다. |
| max_iterations | int | 아니요 | 10 | 알고리즘의 최대 외부 반복 횟수입니다. 양수여야 합니다. 값이 클수록 런타임이 길어지지만 클러스터링 품질이 높아지는 경향이 있습니다. |
| max_inner_iterations | int | 아니요 | 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 | double | 예 | (없음) | 클러스터링의 세부사항을 제어합니다. 클라이언트가 명시적으로 정의해야 합니다. 유한하고 음수가 아니어야 합니다. 값이 작을수록 클러스터가 커지는 경향이 있습니다. 해상도가 0이고 모든 가장자리 가중치가 양수인 경우 알고리즘은 충분한 수의 반복으로 그래프의 연결된 구성요소를 찾습니다. |
| max_iterations | int | 아니요 | 10 | 알고리즘의 최대 외부 반복 횟수입니다. 양수여야 합니다. 값이 클수록 런타임이 길어지지만 클러스터링 품질이 높아지는 경향이 있습니다. |
| max_inner_iterations | int | 아니요 | 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 | int | 아니요 | 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 aggregator를 참고하세요.
함수 서명
CliqueFinding(input_parameters) YIELD node, clique
참고: 대부분의 알고리즘과 달리 노드가 여러 클리크에 속할 수 있으므로 동일한 노드에 여러 행이 있을 수 있습니다.
입력 매개변수
모든 일반 입력 매개변수 및 다음 항목
| 이름 | 유형 | 필수 | 기본값 | 설명 |
|---|---|---|---|---|
| min_density | double | 아니요 | 0.9 | 반환할 클러스터의 최소 밀도입니다. [0, 1] 범위에 있어야 합니다. |
출력
함수 생성:
| 이름 | 유형 | 설명 |
|---|---|---|
| 노드 | GRAPH_ELEMENT (노드) | 그래프의 노드입니다. |
| clique | 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 | 찾은 최단 경로입니다. |
| cost | 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;