Catalogo degli algoritmi di Spanner Graph

Anteprima — Algoritmi di Spanner Graph

Questa funzionalità è soggetta ai "Termini dell'offerta pre-GA" nella sezione dei Termini di servizio generali dei Termini specifici dei servizi. Le funzionalità pre-GA sono disponibili "così come sono" e potrebbero avere un supporto limitato. Per ulteriori informazioni, consulta le descrizioni della fase di lancio.

Nota: questa funzionalità è disponibile con le versioni Enterprise ed Enterprise Plus di Spanner. Per saperne di più, consulta Panoramica delle versioni di Spanner.

Spanner Graph, in stretta collaborazione con Google Research Graph Mining, offre una suite di algoritmi che coprono le esigenze di analisi dei grafi per i seguenti casi d'uso:

• Centralità
• Clustering
• Somiglianza
• Ricerca del percorso

Centralità

Gli algoritmi di centralità classificano i nodi in base alla loro importanza strutturale all'interno di un grafico. Può aiutarti a identificare account fraudolenti nel settore fintech, influencer nei grafi sociali, router critici nelle reti di telecomunicazioni e altro ancora.

PageRank

PageRank assegna un punteggio ai nodi in base all'importanza. Un nodo è considerato più importante se molti altri nodi importanti rimandano a questo. L'algoritmo simula un percorso casuale attraverso il grafico. I nodi visitati più spesso in questo percorso vengono considerati più importanti. Per i dettagli sull'algoritmo, consulta PageRank.

Firma della funzione

PageRank(input_parameters) YIELD node, score

Parametri di input

Tutti i parametri di input comuni e:

Nome	Tipo	Obbligatorio	Predefinito	Descrizione
source_nodes	Array di nodi del grafico	No	(nessuno)	Se presente, l'origine del PageRank personalizzato.
damping_factor	FLOAT64	No	0,85	La probabilità che, in una determinata iterazione, l'algoritmo scelga di attraversare uno degli archi in uscita del nodo corrente. Deve essere compreso nell'intervallo [0, 1).
max_iterations	INT64	No	10	Il numero massimo di iterazioni dell'algoritmo. Deve essere positivo. Un numero maggiore di iterazioni tende a produrre risultati più precisi a scapito di un runtime più lungo.
approx_precision	FLOAT64	No	1e-2	Soglia di precisione dell'approssimazione per l'algoritmo. Deve essere un valore non negativo. Valori più piccoli tendono a produrre risultati più precisi a scapito di un tempo di esecuzione più lungo.

Output

Funzione yields:

Nome	Tipo	Descrizione
nodo	GRAPH_ELEMENT (nodo)	Un nodo nel grafico.
punteggio	FLOAT64	Il punteggio PageRank del nodo.

Esempio

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 misura la frequenza con cui un nodo si trova sui percorsi più brevi tra altre coppie di nodi. I nodi con un'elevata centralità di intermediazione spesso fungono da ponti critici che collegano diverse parti del grafico. Per i dettagli sull'algoritmo, consulta Centralità di intermediazione.

Firma della funzione

BetweennessCentrality(input_parameters) YIELD node, score

Parametri di input

Tutti i parametri di input comuni e:

Nome	Tipo	Obbligatorio	Predefinito	Descrizione
num_source_nodes	INT64	No	(nessuno)	Se impostato, deve essere positivo e specifica quanti nodi di origine l'algoritmo deve selezionare per calcolare le centralità di interposizione approssimative. Se non è impostato o è impostato su un numero maggiore del numero di nodi nel grafico, tutti i nodi vengono utilizzati come nodi di origine, ovvero l'algoritmo calcola le centralità di betweenness esatte. Valori più alti portano ad approssimazioni migliori, ma anche a tempi di esecuzione più lunghi.

Output

Funzione yields:

Nome	Tipo	Descrizione
nodo	GRAPH_ELEMENT (nodo)	Un nodo nel grafico.
punteggio	FLOAT64	Il punteggio di centralità del nodo.

Esempio

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 misura la vicinanza di un nodo a tutti gli altri nodi del grafico. I nodi con una centralità di vicinanza elevata possono raggiungere altri nodi tramite percorsi più brevi. Per i dettagli sull'algoritmo, consulta Centralità di vicinanza.

Firma della funzione

ClosenessCentrality(input_parameters) YIELD node, score

Parametri di input

Tutti i parametri di input comuni e:

Nome	Tipo	Obbligatorio	Predefinito	Descrizione
modalità	STRING	No	ESATTA	La modalità dell'algoritmo. I valori supportati sono EXACT e HYBRID.
use_wasserman_faust	BOOL	No	FALSE	Se false, calcola le centralità di vicinanza standard. Se true, calcola le centralità di vicinanza di Wasserman-Faust.
epsilon	FLOAT64	No	0,1	Utilizzato solo per l'algoritmo HYBRID. Deve essere compreso nell'intervallo (0,0, 1,0). Valori più piccoli indicano generalmente una precisione maggiore. In genere, valori più elevati consentono all'algoritmo di essere eseguito più velocemente.
sample_size	INT64	No	0	Utilizzato solo per l'algoritmo HYBRID. Il numero di nodi pivot da utilizzare per calcolare in modo approssimativo i valori di centralità. Non deve essere un valore negativo. Se non impostato o se impostato su zero, viene utilizzato un valore predefinito di min(100 * ln(N), N), dove N è il numero di nodi del grafo di input.

Output

Funzione yields:

Nome	Tipo	Descrizione
nodo	GRAPH_ELEMENT (nodo)	Un nodo nel grafico.
punteggio	FLOAT64	Il punteggio di centralità di vicinanza del nodo.

Esempio

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

Gli algoritmi di clustering raggruppano i nodi in cluster (noti anche come community) in modo che i nodi all'interno di ciascun cluster siano più densamente connessi tra loro rispetto ai nodi di altri cluster. È utile per rilevare potenziali frodi nel settore fintech, identificare le segmentazioni dei clienti nel settore retail e altro ancora.

WeaklyConnectedComponents

WeaklyConnectedComponents trova insiemi di nodi disgiunti in modo che ogni nodo di un insieme sia raggiungibile da qualsiasi altro nodo dello stesso insieme, ma non dai nodi di altri insiemi. Per i dettagli sull'algoritmo, consulta Componenti connessi.

Firma della funzione

WeaklyConnectedComponents(input_parameters) YIELD node, cluster

Parametri di input

Tutti i parametri di input comuni.

Output

Funzione yields:

Nome	Tipo	Descrizione
nodo	GRAPH_ELEMENT (nodo)	Un nodo nel grafico.
cluster	INT64	L'ID del componente connesso/cluster a cui appartiene il nodo. Nell'intervallo [0, N), dove N è il numero di nodi nel grafico.

Esempio

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 suddivide il grafico in cluster ottimizzando la modularità, una misura di qualità della densità delle connessioni all'interno dei cluster rispetto a quanto ci si aspetterebbe in una rete casuale. Per i dettagli dell'algoritmo, consulta Clustering per modularità.

Firma della funzione

ModularityClustering(input_parameters) YIELD node, cluster

Parametri di input

Tutti i parametri di input comuni e:

Nome	Tipo	Obbligatorio	Predefinito	Descrizione
resolution	FLOAT64	No	1.0	Controlla la granularità del clustering. Deve essere finito e non negativo. Valori di risoluzione più piccoli tendono a generare cluster più grandi. I valori tipici sono compresi nell'intervallo [0,5, 5]. Quando la risoluzione è pari a zero, l'algoritmo (con un numero sufficiente di iterazioni) trova i componenti collegati del grafico (ignorando i bordi con peso pari a zero).
max_iterations	INT64	No	10	Numero massimo di iterazioni esterne dell'algoritmo. Deve essere positivo. Valori più elevati tendono a generare raggruppamenti di qualità superiore, ma con un tempo di esecuzione più lungo.
max_inner_iterations	INT64	No	10	Numero massimo di iterazioni interne dell'algoritmo. Deve essere positivo. Valori più elevati tendono a generare raggruppamenti di qualità superiore, ma con un tempo di esecuzione più lungo.

Output

Funzione yields:

Nome	Tipo	Descrizione
nodo	GRAPH_ELEMENT (nodo)	Un nodo nel grafico.
cluster	INT64	L'ID della community/del cluster a cui appartiene il nodo. Nell'intervallo [0, N), dove N è il numero di nodi nel grafico.

Esempio

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 partiziona i nodi in base alla loro somiglianza o dissomiglianza a coppie, con l'obiettivo di raggruppare i nodi simili e separare quelli dissimili. Per i dettagli dell'algoritmo, consulta la sezione Clustering di correlazione.

Firma della funzione

CorrelationClustering(input_parameters) YIELD node, cluster

Parametri di input

Tutti i parametri di input comuni e:

Nome	Tipo	Obbligatorio	Predefinito	Descrizione
resolution	FLOAT64	Sì	(nessuno)	Controlla la granularità del clustering. Deve essere definito esplicitamente dal client. Deve essere finito e non negativo. Valori più piccoli tendono a generare cluster più grandi. Quando la risoluzione è pari a zero e tutti i pesi degli archi sono positivi, l'algoritmo (con un numero sufficiente di iterazioni) trova i componenti collegati del grafo.
max_iterations	INT64	No	10	Numero massimo di iterazioni esterne dell'algoritmo. Deve essere positivo. Valori più elevati tendono a generare raggruppamenti di qualità superiore, ma con un tempo di esecuzione più lungo.
max_inner_iterations	INT64	No	10	Numero massimo di iterazioni interne dell'algoritmo. Deve essere positivo. Valori più elevati tendono a generare raggruppamenti di qualità superiore, ma con un tempo di esecuzione più lungo.

Output

Funzione yields:

Nome	Tipo	Descrizione
nodo	GRAPH_ELEMENT (nodo)	Un nodo nel grafico.
cluster	INT64	L'ID della community/del cluster a cui appartiene il nodo. Nell'intervallo [0, N), dove N è il numero di nodi nel grafico.

Esempio

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 assegna i nodi ai cluster utilizzando una tecnica di propagazione delle etichette, a partire da un'etichettatura iniziale che può utilizzare le etichette seed fornite nell'input. Man mano che i nodi adottano in modo iterativo l'etichetta condivisa dalla maggior parte dei loro vicini, i gruppi densamente connessi convergono verso un'etichetta di consenso, formando delle community. Per i dettagli sull'algoritmo, consulta la sezione sulla propagazione delle etichette.

Firma della funzione

LabelPropagation(input_parameters) YIELD node, cluster

Parametri di input

Tutti i parametri di input comuni e:

Nome	Tipo	Obbligatorio	Predefinito	Descrizione
seed_label_property	STRING	No	(nessuno)	Il nome della proprietà del nodo per l'etichetta di seed.
max_iterations	INT64	No	10	Il numero massimo di iterazioni di propagazione delle etichette eseguite dall'algoritmo. Deve essere un numero finito e positivo.

Output

Funzione yields:

Nome	Tipo	Descrizione
nodo	GRAPH_ELEMENT (nodo)	Un nodo nel grafico.
cluster	INT64	L'ID del cluster/dell'etichetta propagato del nodo.

Esempio

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 le community dense potenzialmente sovrapposte che soddisfano una soglia di densità minima, in modo che ogni cricca (un gruppo di nodi in cui ogni nodo è connesso a tutti gli altri nodi) sia contenuta in almeno un cluster. Per i dettagli sull'algoritmo, consulta la sezione Aggregatore di cricche.

Firma della funzione

CliqueFinding(input_parameters) YIELD node, clique

Nota: a differenza della maggior parte degli algoritmi, possono essere presenti più righe per lo stesso nodo, poiché un nodo può far parte di più clique.

Parametri di input

Tutti i parametri di input comuni e:

Nome	Tipo	Obbligatorio	Predefinito	Descrizione
min_density	FLOAT64	No	0,9	La densità minima dei cluster da restituire. Deve essere compreso tra [0, 1].

Output

Funzione yields:

Nome	Tipo	Descrizione
nodo	GRAPH_ELEMENT (nodo)	Un nodo nel grafico.
clique	INT64	L'ID del gruppo a cui appartiene il nodo.

Esempio

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;

Similarità

Gli algoritmi di similarità quantificano la somiglianza tra coppie di nodi in base alla struttura dei loro vicini. Questo è utile per dedurre i bordi mancanti tra i nodi per la risoluzione delle entità, i suggerimenti e altro ancora.

Spanner Graph supporta le seguenti somiglianze tra coppie di nodi, in cui i punteggi di somiglianza vengono calcolati in base ai vicini dei nodi.

• JaccardSimilarity: in base al rapporto tra i vicini comuni e i vicini totali
• CosineSimilarity: In base ai pesi degli archi dei vicini comuni
• CommonNeighborsSimilarity: in base al numero di vicini condivisi
• TotalNeighborsSimilarity: in base al numero di vicini di almeno uno dei due nodi

Per i dettagli sull'algoritmo, consulta Somiglianza dei nodi a coppie.

Questi quattro algoritmi condividono gli stessi argomenti e la stessa struttura di output.

Firma della funzione

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

Parametri di input

Tutti i parametri di input comuni e:

Nome	Tipo	Obbligatorio	Predefinito	Descrizione
source_nodes	Array di nodi del grafico	Sì	N/D	I nodi di origine per il calcolo della somiglianza pairwise.
target_nodes	Array di nodi del grafico	Sì	N/D	I nodi di destinazione per il calcolo della somiglianza a coppie.

Output

Funzione yields:

Nome	Tipo	Descrizione
source_node	GRAPH_ELEMENT (nodo)	Il nodo di origine utilizzato nel calcolo della somiglianza.
target_node	GRAPH_ELEMENT (nodo)	Il nodo di destinazione utilizzato nel calcolo della somiglianza.
similarity	FLOAT64	Il punteggio di somiglianza calcolato tra il nodo di origine e quello di destinazione.

Esempio

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;

Ricerca del percorso

Gli algoritmi di ricerca del percorso calcolano i percorsi ottimali tra i nodi. È utile per identificare il percorso più economico nelle catene di fornitura, valutare le vulnerabilità nella cybersicurezza e altro ancora.

ShortestPath

ShortestPath calcola i percorsi più brevi tra un determinato insieme di nodi di origine e un determinato insieme di nodi di destinazione. Per i dettagli dell'algoritmo, consulta i percorsi più brevi many-to-many.

Firma della funzione

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

Parametri di input

Tutti i parametri di input comuni e:

Nome	Tipo	Obbligatorio	Predefinito	Descrizione
source_nodes	Array di nodi del grafico	Sì	N/D	I nodi di origine per il calcolo del percorso più breve.
target_nodes	Array di nodi del grafico	Sì	N/D	I nodi di destinazione per il calcolo del percorso più breve.

Output

Funzione yields:

Nome	Tipo	Descrizione
source_node	GRAPH_ELEMENT (nodo)	Il nodo di origine del percorso.
target_node	GRAPH_ELEMENT (nodo)	Il nodo di destinazione del percorso.
percorso	GRAPH_PATH	Il percorso più breve trovato.
costo	FLOAT64	Il costo del percorso più breve.

Esempio

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;

Passaggi successivi

• Esegui algoritmi Spanner Graph.
• Requisiti dello schema dell'algoritmo Spanner Graph e compatibilità delle funzionalità.
• Best practice per l'algoritmo Spanner Graph.