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
입력 매개변수
모든 일반 입력 매개변수 및 다음 항목
| 이름 | 유형 | 필수 | 기본값 | 설명 |
|---|---|---|---|---|
| 모드 | 문자열 | 아니요 | 일치검색 | 알고리즘 모드입니다. 지원되는 값은 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, 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 | 문자열 | 아니요 | (없음) | 시드 라벨의 노드 속성 이름입니다. |
| 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는 모든 클리크 (각 노드가 다른 모든 노드에 연결된 노드 그룹)가 하나 이상의 클러스터에 포함되도록 최소 밀도 기준점을 충족하는 잠재적으로 중복되는 밀도 높은 커뮤니티를 식별합니다. 알고리즘 세부정보는 클릭 집계기를 참조하세요.
함수 서명
CliqueFinding(input_parameters) YIELD node, clique
참고: 대부분의 알고리즘과 달리 노드가 여러 클리크에 속할 수 있으므로 동일한 노드에 여러 행이 있을 수 있습니다.
입력 매개변수
모든 일반 입력 매개변수 및 다음 항목
| 이름 | 유형 | 필수 | 기본값 | 설명 |
|---|---|---|---|---|
| min_density | FLOAT64 | 아니요 | 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;