Catálogo de algoritmos do Spanner Graph

O Spanner Graph, em colaboração com a Google Research Graph Mining, oferece um conjunto de algoritmos que atendem às necessidades de análise de grafos para os seguintes casos de uso:

Centralidade

Os algoritmos de centralidade classificam os nós de acordo com a importância estrutural deles em um gráfico. Ele pode ajudar a identificar contas fraudulentas em fintechs, influenciadores em gráficos sociais, roteadores críticos em redes de telecomunicações e muito mais.

PageRank

O PageRank classifica os nós por importância. Um nó é considerado mais importante se muitos outros nós importantes se vincularem a ele. O algoritmo simula uma caminhada aleatória pelo gráfico. Os nós visitados com mais frequência nessa caminhada são considerados mais importantes. Consulte o PageRank para mais detalhes sobre o algoritmo.

Assinatura de função

PageRank(input_parameters) YIELD node, score

Parâmetros de entrada

Todos os parâmetros de entrada comuns e:

Nome Tipo Obrigatório Padrão Descrição
source_nodes Matriz de nós de gráfico Não (nenhum) Se presente, a origem do PageRank personalizado.
damping_factor double Não 0,85 A probabilidade de que, em qualquer iteração, o algoritmo escolha percorrer uma das arestas de saída do nó atual. Precisa estar no intervalo [0, 1).
max_iterations int Não 10 O número máximo de iterações do algoritmo. Precisa ser positivo. Um número maior de iterações tende a produzir resultados mais precisos, mas com um tempo de execução mais longo.
approx_precision double Não 1e-2 Limite de precisão de aproximação para o algoritmo. Não pode ser negativo. Valores menores tendem a produzir resultados mais precisos, mas com um tempo de execução maior.

Saída

A função gera:

Nome Tipo Descrição
nó GRAPH_ELEMENT (nó) Um nó no gráfico.
score FLOAT64 A pontuação de PageRank do nó.

Exemplo

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 mede a frequência com que um nó está nos caminhos mais curtos entre outros pares de nós. Os nós com alta centralidade de intermediação geralmente atuam como pontes críticas que conectam diferentes partes do gráfico. Consulte centralidade de intermediária para mais detalhes sobre o algoritmo.

Assinatura de função

BetweennessCentrality(input_parameters) YIELD node, centrality

Parâmetros de entrada

Todos os parâmetros de entrada comuns e:

Nome Tipo Obrigatório Padrão Descrição
num_source_nodes INT64 Não (nenhum) Se definido, precisa ser positivo e especifica quantos nós de origem o algoritmo deve selecionar para calcular as centralidades de intermediariedade aproximadas. Se não for definido ou for definido como um número maior que o número de nós no gráfico, todos os nós serão usados como nós de origem. Ou seja, o algoritmo calcula centralidades de intermediariedade exatas. Valores mais altos levam a aproximações melhores, mas também a tempos de execução maiores.

Saída

A função gera:

Nome Tipo Descrição
nó GRAPH_ELEMENT (nó) Um nó no gráfico.
centralidade FLOAT64 A pontuação de centralidade do nó.

Exemplo

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 mede a proximidade de um nó com todos os outros nós no gráfico. Os nós com alta centralidade de proximidade podem alcançar outros nós por caminhos mais curtos. Consulte centralidade de proximidade para mais detalhes sobre o algoritmo.

Assinatura de função

ClosenessCentrality(input_parameters) YIELD node, centrality

Parâmetros de entrada

Todos os parâmetros de entrada comuns e:

Nome Tipo Obrigatório Padrão Descrição
modo STRING Não EXACT O modo do algoritmo. Os valores aceitos são EXACT e HYBRID.
use_wasserman_faust BOOL Não FALSO Se for "false", calcule as centralidades de proximidade padrão. Se for "true", calcula as centralidades de proximidade de Wasserman-Faust.
epsilon FLOAT64 Não 0,1 Usado apenas para o algoritmo "HYBRID". Precisa estar no intervalo (0,0, 1,0). Valores menores geralmente significam maior precisão. Valores maiores geralmente permitem que o algoritmo seja executado mais rápido.
sample_size INT64 Não 0 Usado apenas para o algoritmo "HYBRID". O número de nós de pivô a serem usados para calcular aproximadamente os valores de centralidade. Não podem ser negativas. Se não for definido ou for zero, será usado um valor padrão de min(100 * ln(N), N), em que N é a contagem de nós do gráfico de entrada.

Saída

A função gera:

Nome Tipo Descrição
nó GRAPH_ELEMENT (nó) Um nó no gráfico.
centralidade FLOAT64 A pontuação de centralidade de proximidade do nó.

Exemplo

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;

Clustering

Os algoritmos de clustering agrupam nós em clusters (também conhecidos como comunidades) de modo que os nós em cada cluster estejam mais densamente conectados entre si do que com os nós em outros clusters. Isso é útil para detectar possíveis grupos de fraude em fintechs, identificar segmentações de clientes no varejo e muito mais.

WeaklyConnectedComponents

WeaklyConnectedComponents encontra conjuntos disjuntos de nós para que cada nó em um conjunto seja acessível de qualquer outro nó no mesmo conjunto, mas não de nós em outros conjuntos. Consulte componentes conectados para mais detalhes sobre o algoritmo.

Assinatura de função

WeaklyConnectedComponents(input_parameters) YIELD node, cluster

Parâmetros de entrada

Todos os parâmetros de entrada comuns.

Saída

A função gera:

Nome Tipo Descrição
nó GRAPH_ELEMENT (nó) Um nó no gráfico.
cluster INT64 O ID do componente/cluster conectado a que o nó pertence. No intervalo [0, N), em que N é o número de nós no gráfico.

Exemplo

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

O ModularityClustering divide o gráfico em clusters otimizando a modularidade, uma medida de qualidade da densidade de conexões dentro dos clusters em comparação com o que seria esperado em uma rede aleatória. Consulte clustering de modularidade para detalhes do algoritmo.

Assinatura de função

ModularityClustering(input_parameters) YIELD node, cluster

Parâmetros de entrada

Todos os parâmetros de entrada comuns e:

Nome Tipo Obrigatório Padrão Descrição
resolução double Não 1.0 Controla a granularidade do agrupamento. Precisa ser finito e não negativo. Valores de resolução menores tendem a levar a clusters maiores. Os valores típicos estão no intervalo [0,5, 5]. Quando a resolução é zero, o algoritmo (com um número suficiente de iterações) encontra os componentes conectados do gráfico, ignorando as arestas com peso zero.
max_iterations int Não 10 Número máximo de iterações externas do algoritmo. Precisa ser positivo. Valores maiores tendem a gerar agrupamentos de maior qualidade, mas com um tempo de execução mais longo.
max_inner_iterations int Não 10 Número máximo de iterações internas do algoritmo. Precisa ser positivo. Valores maiores tendem a gerar agrupamentos de maior qualidade, mas com um tempo de execução mais longo.

Saída

A função gera:

Nome Tipo Descrição
nó GRAPH_ELEMENT (nó) Um nó no gráfico.
cluster INT64 O ID da comunidade/cluster a que o nó pertence. No intervalo [0, N), em que N é o número de nós no gráfico.

Exemplo

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 particiona nós com base na semelhança ou dissimilaridade aos pares, com o objetivo de agrupar nós semelhantes e separar os diferentes. Consulte clustering por correlação para detalhes do algoritmo.

Assinatura de função

CorrelationClustering(input_parameters) YIELD node, cluster

Parâmetros de entrada

Todos os parâmetros de entrada comuns e:

Nome Tipo Obrigatório Padrão Descrição
resolução double Sim (nenhum) Controla a granularidade do agrupamento. Precisa ser definido explicitamente pelo cliente. Precisa ser finito e não negativo. Valores menores tendem a gerar clusters maiores. Quando a resolução é zero e todos os pesos das arestas são positivos, o algoritmo (com um número suficiente de iterações) encontra os componentes conectados do gráfico.
max_iterations int Não 10 Número máximo de iterações externas do algoritmo. Precisa ser positivo. Valores maiores tendem a gerar agrupamentos de maior qualidade, mas com um tempo de execução mais longo.
max_inner_iterations int Não 10 Número máximo de iterações internas do algoritmo. Precisa ser positivo. Valores maiores tendem a gerar agrupamentos de maior qualidade, mas com um tempo de execução mais longo.

Saída

A função gera:

Nome Tipo Descrição
nó GRAPH_ELEMENT (nó) Um nó no gráfico.
cluster INT64 O ID da comunidade/cluster a que o nó pertence. No intervalo [0, N), em que N é o número de nós no gráfico.

Exemplo

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 atribui nós a clusters usando uma técnica de propagação de rótulos, começando com uma rotulagem inicial que pode usar rótulos de semente fornecidos na entrada. À medida que os nós adotam iterativamente o marcador compartilhado pela maioria dos vizinhos, grupos densamente conectados convergem para um marcador de consenso, formando comunidades. Consulte propagação de rótulos para detalhes do algoritmo.

Assinatura de função

LabelPropagation(input_parameters) YIELD node, cluster

Parâmetros de entrada

Todos os parâmetros de entrada comuns e:

Nome Tipo Obrigatório Padrão Descrição
seed_label_property string Não (nenhum) O nome da propriedade do nó para o rótulo de seed.
max_iterations int Não 10 O número máximo de iterações de propagação de rótulos que o algoritmo realiza. Precisa ser finito e positivo.

Saída

A função gera:

Nome Tipo Descrição
nó GRAPH_ELEMENT (nó) Um nó no gráfico.
cluster INT64 O ID do cluster/rótulo propagado do nó.

Exemplo

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 identifica comunidades densas potencialmente sobrepostas que atendem a um limite mínimo de densidade, de modo que cada clique (um grupo de nós em que cada nó está conectado a todos os outros) esteja contido em pelo menos um cluster. Consulte o agregador de cliques para mais detalhes sobre o algoritmo.

Assinatura de função

CliqueFinding(input_parameters) YIELD node, clique

Observação:ao contrário da maioria dos algoritmos, pode haver várias linhas para o mesmo nó, já que um nó pode fazer parte de várias cliques.

Parâmetros de entrada

Todos os parâmetros de entrada comuns e:

Nome Tipo Obrigatório Padrão Descrição
min_density double Não 0,9 A densidade mínima dos clusters a serem retornados. Precisa estar entre [0, 1].

Saída

A função gera:

Nome Tipo Descrição
nó GRAPH_ELEMENT (nó) Um nó no gráfico.
clique INT64 O ID do clique a que o nó pertence.

Exemplo

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;

Semelhança

Os algoritmos de similaridade quantificam a semelhança entre pares de nós com base na estrutura das vizinhanças deles. Isso é útil para inferir arestas ausentes entre nós para resolução de entidades, recomendação e muito mais.

O Spanner Graph oferece suporte às seguintes similaridades de nós aos pares, em que as pontuações de similaridade são calculadas com base nas vizinhanças dos nós.

  • JaccardSimilarity: com base na proporção de vizinhos comuns em relação ao total de vizinhos
  • CosineSimilarity: com base nas ponderações de arestas de vizinhos comuns
  • CommonNeighborsSimilarity: com base no número de vizinhos compartilhados
  • TotalNeighborsSimilarity: com base no número de vizinhos de pelo menos um dos dois nós

Consulte similaridade de nós aos pares para detalhes do algoritmo.

Esses quatro algoritmos compartilham os mesmos argumentos e estrutura de saída.

Assinatura de função

[JaccardSimilarity|CosineSimilarity|CommonNeighborsSimilarity|TotalNeighborsSimilarity](input_parameters) YIELD source_node, target_node, similarity

Parâmetros de entrada

Todos os parâmetros de entrada comuns e:

Nome Tipo Obrigatório Padrão Descrição
source_nodes Matriz de nós Sim N/A
target_nodes Matriz de nós Sim N/A

Saída

A função gera:

Nome Tipo Descrição
source_node GRAPH_ELEMENT (nó) O nó de origem usado no cálculo de similaridade.
target_node GRAPH_ELEMENT (nó) O nó de destino usado no cálculo de similaridade.
similaridade FLOAT64 A pontuação de similaridade calculada entre o nó de origem e o de destino.

Exemplo

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;

Localização de caminho

Os algoritmos de descoberta de caminhos calculam rotas ideais entre nós. Isso é útil para identificar a rota mais barata em cadeias de suprimentos, avaliar a vulnerabilidade em cibersegurança e muito mais.

ShortestPath

ShortestPath calcula os caminhos mais curtos entre um conjunto de nós de origem e um conjunto de nós de destino. Consulte caminhos mais curtos de muitos para muitos para mais detalhes sobre o algoritmo.

Assinatura de função

ShortestPath(input_parameters) YIELD source_node, target_node, path, cost

Parâmetros de entrada

Todos os parâmetros de entrada comuns e:

Nome Tipo Obrigatório Padrão Descrição
source_nodes Matriz de nós Sim N/A
target_nodes Matriz de nós Sim N/A

Saída

A função gera:

Nome Tipo Descrição
source_node GRAPH_ELEMENT (nó) O nó de origem do caminho.
target_node GRAPH_ELEMENT (nó) O nó de destino do caminho.
path GRAPH_PATH O caminho mais curto encontrado.
custo FLOAT64 O custo do caminho mais curto.

Exemplo

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;

A seguir