Catalogo degli algoritmi di Spanner Graph

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à

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 esso. L'algoritmo simula una passeggiata casuale nel grafo. I nodi visitati più spesso in questo percorso vengono considerati più importanti. Consulta la pagina PageRank per i dettagli dell'algoritmo.

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, origine del PageRank personalizzato.
damping_factor double No 0,85 La probabilità che, in una determinata iterazione, l'algoritmo scelga di attraversare uno dei bordi in uscita del nodo corrente. Deve essere compreso nell'intervallo [0, 1).
max_iterations int No 10 Il numero massimo di iterazioni dell'algoritmo. Deve essere positivo. Un numero maggiore di iterazioni tende a produrre risultati più precisi a costo di un runtime più lungo.
approx_precision double No 1e-2 Soglia di precisione dell'approssimazione per l'algoritmo. Deve essere non negativo. Valori più piccoli tendono a produrre risultati più precisi a costo di un runtime più lungo.

Output

Funzione restituisce:

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 dell'algoritmo, consulta la sezione Centralità di intermediazione.

Firma della funzione

BetweennessCentrality(input_parameters) YIELD node, centrality

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 il numero di nodi di origine che l'algoritmo deve selezionare per calcolare le centralità di intermediazione 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 intermediazione esatte. Valori più alti portano ad approssimazioni migliori, ma anche a tempi di esecuzione più lunghi.

Output

Funzione restituisce:

Nome Tipo Descrizione
nodo GRAPH_ELEMENT (nodo) Un nodo nel grafico.
centralità 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, centrality
RETURN node.id, centrality;

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 dell'algoritmo, consulta la centralità di vicinanza.

Firma della funzione

ClosenessCentrality(input_parameters) YIELD node, centrality

Parametri di input

Tutti i parametri di input comuni e:

Nome Tipo Obbligatorio Predefinito Descrizione
modalità STRING No EXACT La modalità dell'algoritmo. I valori supportati sono EXACT e HYBRID.
use_wasserman_faust BOOL No FALSE Se il valore è "false", calcola le centralità di vicinanza standard. Se `true`, calcola le centralità di chiusura 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 in genere una maggiore precisione. Valori più grandi in genere consentono all'algoritmo di essere eseguito più rapidamente.
sample_size INT64 No 0 Utilizzato solo per l'algoritmo "HYBRID". Il numero di nodi pivot da utilizzare per calcolare approssimativamente i valori di centralità. Non deve essere un valore negativo. Se non è impostato o è zero, viene utilizzato un valore predefinito pari a min(100 * ln(N), N), dove N è il numero di nodi del grafico di input.

Output

Funzione restituisce:

Nome Tipo Descrizione
nodo GRAPH_ELEMENT (nodo) Un nodo nel grafico.
centralità 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, centrality
RETURN node.id, centrality;

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 disgiunti di nodi 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 informazioni dettagliate 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 restituisce:

Nome Tipo Descrizione
nodo GRAPH_ELEMENT (nodo) Un nodo nel grafico.
cluster INT64 L'ID del componente/cluster connesso 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
risoluzione double 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 è zero, l'algoritmo (con un numero sufficiente di iterazioni) trova i componenti connessi del grafico (ignorando gli archi il cui peso è zero).
max_iterations int No 10 Numero massimo di iterazioni esterne dell'algoritmo. Deve essere positivo. Valori più grandi tendono a generare cluster di qualità superiore a scapito di un runtime più lungo.
max_inner_iterations int No 10 Numero massimo di iterazioni interne dell'algoritmo. Deve essere positivo. Valori più grandi tendono a generare cluster di qualità superiore a scapito di un runtime più lungo.

Output

Funzione restituisce:

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
risoluzione double Sì (nessuno) Controlla la granularità del clustering. Deve essere definito esplicitamente dal cliente. Deve essere finito e non negativo. Valori più piccoli tendono a generare cluster più grandi. Quando la risoluzione è zero e tutti i pesi dei bordi sono positivi, l'algoritmo (con un numero sufficiente di iterazioni) trova i componenti connessi del grafico.
max_iterations int No 10 Numero massimo di iterazioni esterne dell'algoritmo. Deve essere positivo. Valori più grandi tendono a generare cluster di qualità superiore a scapito di un runtime più lungo.
max_inner_iterations int No 10 Numero massimo di iterazioni interne dell'algoritmo. Deve essere positivo. Valori più grandi tendono a generare cluster di qualità superiore a scapito di un runtime più lungo.

Output

Funzione restituisce:

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 su un'etichetta di consenso, formando comunità. Consulta la propagazione delle etichette per i dettagli dell'algoritmo.

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 iniziale.
max_iterations int No 10 Il numero massimo di iterazioni di propagazione delle etichette eseguite dall'algoritmo. Deve essere finito e positivo.

Output

Funzione restituisce:

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 dell'algoritmo, consulta Aggregatore di cricche.

Firma della funzione

CliqueFinding(input_parameters) YIELD node, clique

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

Parametri di input

Tutti i parametri di input comuni e:

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

Output

Funzione restituisce:

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 vicinati. Questa funzionalità è utile per dedurre i bordi mancanti tra i nodi per la risoluzione delle entità, i consigli e altro ancora.

Spanner Graph supporta le seguenti similarità tra coppie di nodi, dove i punteggi di similarità vengono calcolati in base ai vicini dei nodi.

  • JaccardSimilarity: In base al rapporto tra vicini comuni e 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 dell'algoritmo, consulta la sezione Similarità a coppie tra nodi.

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 Sì N/D
target_nodes Array di nodi Sì N/D

Output

Funzione restituisce:

Nome Tipo Descrizione
source_node GRAPH_ELEMENT (nodo) Il nodo di origine utilizzato nel calcolo della somiglianza.
target_node GRAPH_ELEMENT (nodo) Il nodo target utilizzato nel calcolo della somiglianza.
somiglianza 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 la 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 molti-a-molti.

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 Sì N/D
target_nodes Array di nodi Sì N/D

Output

Funzione restituisce:

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