Catálogo de algoritmos do Spanner Graph

Prévia — Algoritmos do Spanner Graph

Este recurso está sujeito aos Termos das Soluções Pré-GA na seção Termos Gerais de Serviço dos Termos Específicos de Serviço. Os recursos pré-GA estão disponíveis "no estado em que se encontram" e podem ter suporte limitado. Para mais informações, consulte as descrições da fase de lançamento.

Observação: esse recurso está disponível nas edições Enterprise e Enterprise Plus do Spanner. Para mais informações, consulte o resumo das edições do Spanner.

O Spanner Graph, em estreita colaboração com o 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
• Clustering
• Semelhança
• Descoberta de caminho

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

PageRank pontua os nós por importância. Um nó é considerado mais importante se muitos outros nós importantes estiverem vinculados 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 saber detalhes do 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	FLOAT64	Não	0,85	A probabilidade de que, em qualquer iteração, o algoritmo escolha atravessar uma das arestas de saída do nó atual. Precisa estar no intervalo [0, 1).
max_iterations	INT64	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	FLOAT64	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 mais longo.

Saída

A função gera:

Nome	Tipo	Descrição
nó	GRAPH_ELEMENT (nó)	Um nó no gráfico.
score	FLOAT64	A pontuação do 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 grafo. Consulte centralidade de intermediário para detalhes do algoritmo.

Assinatura de função

BetweennessCentrality(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
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.
score	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, score
RETURN node.id, score;

ClosenessCentrality

ClosenessCentrality mede a proximidade de um nó em relação a 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 detalhes do algoritmo.

Assinatura de função

ClosenessCentrality(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
modo	STRING	Não	EXATA	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 true, calcule as centralidades de proximidade de Wasserman-Faust.
épsilon	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 dinâmicos 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.
score	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, score
RETURN node.id, score;

Clustering

Os algoritmos de clustering agrupam nós em clusters (também conhecidos como comunidades) de forma que os nós em cada cluster sejam mais densamente conectados entre si do que com 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 de nós separados, de modo 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 detalhes do 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 ao qual o nó pertence. No intervalo de [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

ModularityClustering particiona 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	FLOAT64	Não	1.0	Controla a granularidade do clustering. Precisa ser finito e não negativo. Valores de resolução menores tendem a gerar 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	INT64	Não	10	Número máximo de iterações externas do algoritmo. Precisa ser positivo. Valores maiores tendem a gerar clusters de maior qualidade, mas o tempo de execução é maior.
max_inner_iterations	INT64	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 de [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

O 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 de 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	FLOAT64	Sim	(nenhum)	Controla a granularidade do clustering. 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 de aresta são positivos, o algoritmo (com um número suficiente de iterações) encontra os componentes conectados do gráfico.
max_iterations	INT64	Não	10	Número máximo de iterações externas do algoritmo. Precisa ser positivo. Valores maiores tendem a gerar clusters de maior qualidade, mas o tempo de execução é maior.
max_inner_iterations	INT64	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 de [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

O 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 rótulo compartilhado pela maioria dos vizinhos, os grupos densamente conectados convergem para um rótulo 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 semente.
max_iterations	INT64	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 que podem se sobrepor e que atendem a um limiar mínimo de densidade, de modo que cada clique (um grupo de nós em que cada nó está conectado a todos os outros nós) 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	FLOAT64	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 ao qual 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 é compatível com as seguintes semelhanças de nós em pares, em que as pontuações de semelhança 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 nos pesos das 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 em 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 de gráfico	Sim	N/A	Os nós de origem para o cálculo de similaridade em pares.
target_nodes	Matriz de nós do gráfico	Sim	N/A	Os nós de destino para o cálculo de similaridade em pares.

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;

Path Finding

Os algoritmos de busca de caminhos calculam as rotas ideais entre os nós. Isso é útil para identificar a rota mais barata em cadeias de suprimentos, avaliar a vulnerabilidade em segurança cibernética e muito mais.

ShortestPath

ShortestPath calcula os caminhos mais curtos entre um determinado conjunto de nós de origem e um determinado 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 de gráfico	Sim	N/A	Os nós de origem para o cálculo do caminho mais curto.
target_nodes	Matriz de nós do gráfico	Sim	N/A	Os nós de destino para o cálculo do caminho mais curto.

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

• Executar algoritmos do Spanner Graph.
• Requisitos de esquema de algoritmo do Spanner Graph e compatibilidade de recursos.
• Práticas recomendadas para algoritmos do Spanner Graph.