Catalogue des algorithmes Spanner Graph

Aperçu — Algorithmes Spanner Graph

Cette fonctionnalité est soumise aux "Conditions des offres de pré-DG" de la section "Conditions générales du service" des Conditions spécifiques du service. Les fonctionnalités pré-DG sont disponibles "en l'état" et peuvent avoir une prise en charge limitée. Pour en savoir plus, consultez les descriptions des étapes de lancement.

Remarque : Cette fonctionnalité est disponible dans les éditions Spanner Enterprise et Enterprise Plus. Pour en savoir plus, consultez la présentation des éditions Spanner.

Spanner Graph, en étroite collaboration avec Google Research Graph Mining, propose une suite d'algorithmes couvrant les besoins d'analyse de graphes pour les cas d'utilisation suivants :

• Centralité
• Clustering
• Similarité
• Recherche de chemin

Centralité

Les algorithmes de centralité classent les nœuds en fonction de leur importance structurelle dans un graphique. Elle peut vous aider à identifier les comptes frauduleux dans la fintech, les influenceurs dans les graphiques sociaux, les routeurs critiques dans les réseaux de télécommunications et plus encore.

PageRank

PageRank attribue un score aux nœuds en fonction de leur importance. Un nœud est considéré comme plus important si de nombreux autres nœuds importants y sont associés. L'algorithme simule une marche aléatoire dans le graphe. Les nœuds visités plus souvent au cours de cette marche sont considérés comme plus importants. Pour en savoir plus sur l'algorithme, consultez PageRank.

Signature de la fonction

PageRank(input_parameters) YIELD node, score

Paramètres d'entrée

Tous les paramètres d'entrée courants et :

Nom	Type	Obligatoire	Par défaut	Description
source_nodes	Tableau de nœuds de graphique	Non	(aucun)	Si elle est présente, source du PageRank personnalisé.
damping_factor	FLOAT64	Non	0,85	Probabilité que, à une itération donnée, l'algorithme choisisse de traverser l'un des bords sortants du nœud actuel. La valeur doit être comprise dans la plage [0, 1).
max_iterations	INT64	Non	10	Nombre maximal d'itérations de l'algorithme. Doit être positive. Un nombre d'itérations plus élevé tend à produire des résultats plus précis, mais au détriment d'un temps d'exécution plus long.
approx_precision	FLOAT64	Non	1e-2	Seuil de précision de l'approximation pour l'algorithme. La valeur ne doit pas être négative. Des valeurs plus petites ont tendance à produire des résultats plus précis, mais au détriment d'un temps d'exécution plus long.

Sortie

Résultats de la fonction :

Nom	Type	Description
nœud	GRAPH_ELEMENT (nœud)	Un nœud dans le graphique.
score	FLOAT64	Score PageRank du nœud.

Exemple

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 mesure la fréquence à laquelle un nœud se trouve sur les chemins les plus courts entre d'autres paires de nœuds. Les nœuds à forte centralité d'intermédiarité servent souvent de ponts essentiels reliant différentes parties du graphique. Pour en savoir plus sur l'algorithme, consultez Centralité d'intermédiarité.

Signature de la fonction

BetweennessCentrality(input_parameters) YIELD node, score

Paramètres d'entrée

Tous les paramètres d'entrée courants et :

Nom	Type	Obligatoire	Par défaut	Description
num_source_nodes	INT64	Non	(aucun)	S'il est défini, il doit être positif et spécifie le nombre de nœuds sources que l'algorithme doit sélectionner pour calculer les centralités d'intermédiarité approximatives. Si cette valeur n'est pas définie ou est définie sur un nombre supérieur au nombre de nœuds du graphique, tous les nœuds sont utilisés comme nœuds sources, c'est-à-dire que l'algorithme calcule les centralités d'intermédiarité exactes. Des valeurs plus élevées permettent d'obtenir de meilleures approximations, mais aussi des temps d'exécution plus longs.

Sortie

Résultats de la fonction :

Nom	Type	Description
nœud	GRAPH_ELEMENT (nœud)	Un nœud dans le graphique.
score	FLOAT64	Score de centralité du nœud.

Exemple

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 mesure la proximité d'un nœud par rapport à tous les autres nœuds du graphique. Les nœuds présentant une centralité de proximité élevée peuvent atteindre d'autres nœuds via des chemins plus courts. Pour en savoir plus sur l'algorithme, consultez Centralité de proximité.

Signature de la fonction

ClosenessCentrality(input_parameters) YIELD node, score

Paramètres d'entrée

Tous les paramètres d'entrée courants et :

Nom	Type	Obligatoire	Par défaut	Description
Standard	STRING	Non	EXACT	Mode de l'algorithme. Les valeurs acceptées sont EXACT et HYBRID.
use_wasserman_faust	BOOL	Non	FALSE	Si la valeur est false, calculez les centralités de proximité standards. Si la valeur est true, calcule les centralités de proximité Wasserman-Faust.
epsilon	FLOAT64	Non	0,1	Utilisé uniquement pour l'algorithme HYBRID. La valeur doit être comprise entre 0,0 et 1,0. Des valeurs plus petites signifient généralement une précision plus élevée. Des valeurs plus élevées permettent généralement à l'algorithme de s'exécuter plus rapidement.
sample_size	INT64	Non	0	Utilisé uniquement pour l'algorithme HYBRID. Nombre de nœuds pivots à utiliser pour calculer approximativement les valeurs de centralité. Cette valeur ne doit pas être négative Si elle n'est pas définie ou est égale à zéro, la valeur par défaut min(100 * ln(N), N) est utilisée, où N correspond au nombre de nœuds du graphique d'entrée.

Sortie

Résultats de la fonction :

Nom	Type	Description
nœud	GRAPH_ELEMENT (nœud)	Nœud du graphique.
score	FLOAT64	Score de centralité de proximité du nœud.

Exemple

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

Les algorithmes de clustering regroupent les nœuds en clusters (également appelés communautés) de sorte que les nœuds de chaque cluster sont plus densément connectés les uns aux autres qu'aux nœuds des autres clusters. Cela permet de détecter les éventuels réseaux de fraude dans le secteur de la fintech, d'identifier les segmentations de clients dans le secteur de la vente au détail, et plus encore.

WeaklyConnectedComponents

WeaklyConnectedComponents recherche des ensembles de nœuds disjoints de sorte que chaque nœud d'un ensemble soit accessible depuis n'importe quel autre nœud du même ensemble, mais pas depuis les nœuds d'autres ensembles. Pour en savoir plus sur l'algorithme, consultez Composantes connexes.

Signature de la fonction

WeaklyConnectedComponents(input_parameters) YIELD node, cluster

Paramètres d'entrée

Tous les paramètres d'entrée courants.

Sortie

Résultats de la fonction :

Nom	Type	Description
nœud	GRAPH_ELEMENT (nœud)	Nœud du graphique.
cluster	INT64	ID du composant/cluster connecté auquel appartient le nœud. Dans la plage [0, N), où N est le nombre de nœuds dans le graphe.

Exemple

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 partitionne le graphe en clusters en optimisant la modularité, une mesure de qualité de la densité des connexions au sein des clusters par rapport à ce qui serait attendu dans un réseau aléatoire. Pour en savoir plus sur l'algorithme, consultez Clustering par modularité.

Signature de la fonction

ModularityClustering(input_parameters) YIELD node, cluster

Paramètres d'entrée

Tous les paramètres d'entrée courants et :

Nom	Type	Obligatoire	Par défaut	Description
resolution	FLOAT64	Non	1.0	Contrôle la précision du clustering. Doit être un nombre fini et non négatif. Des valeurs de résolution plus petites ont tendance à entraîner des clusters plus grands. Les valeurs types sont comprises entre 0, 5 et 5. Lorsque la résolution est de zéro, l'algorithme (avec un nombre suffisant d'itérations) trouve les composants connectés du graphique (en ignorant les arêtes dont la pondération est de zéro).
max_iterations	INT64	Non	10	Nombre maximal d'itérations externes de l'algorithme. Doit être positive. Des valeurs plus élevées ont tendance à générer des clusters de meilleure qualité, au détriment d'une durée d'exécution plus longue.
max_inner_iterations	INT64	Non	10	Nombre maximal d'itérations internes de l'algorithme. Doit être positive. Des valeurs plus élevées ont tendance à générer des clusters de meilleure qualité, mais au prix d'un temps d'exécution plus long.

Sortie

Résultats de la fonction :

Nom	Type	Description
nœud	GRAPH_ELEMENT (nœud)	Un nœud dans le graphique.
cluster	INT64	ID de la communauté/du cluster auquel appartient le nœud. Dans la plage [0, N), où N correspond au nombre de nœuds dans le graphique.

Exemple

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 partitionne les nœuds en fonction de leur similarité ou dissimilarité par paires, dans le but de regrouper les nœuds similaires tout en séparant ceux qui ne le sont pas. Pour en savoir plus sur l'algorithme, consultez clustering de corrélation.

Signature de la fonction

CorrelationClustering(input_parameters) YIELD node, cluster

Paramètres d'entrée

Tous les paramètres d'entrée courants et :

Nom	Type	Obligatoire	Par défaut	Description
resolution	FLOAT64	Oui	(aucun)	Contrôle la précision du clustering. Doit être explicitement défini par le client. Doit être un nombre fini et non négatif. Les valeurs plus petites ont tendance à générer des clusters plus grands. Lorsque la résolution est nulle et que toutes les pondérations d'arêtes sont positives, l'algorithme (avec un nombre suffisant d'itérations) trouve les composants connectés du graphe.
max_iterations	INT64	Non	10	Nombre maximal d'itérations externes de l'algorithme. Doit être positive. Des valeurs plus élevées ont tendance à générer des clusters de meilleure qualité, au détriment d'une durée d'exécution plus longue.
max_inner_iterations	INT64	Non	10	Nombre maximal d'itérations internes de l'algorithme. Doit être positive. Des valeurs plus élevées ont tendance à générer des clusters de meilleure qualité, mais au prix d'un temps d'exécution plus long.

Sortie

Résultats de la fonction :

Nom	Type	Description
nœud	GRAPH_ELEMENT (nœud)	Un nœud dans le graphique.
cluster	INT64	ID de la communauté/du cluster auquel appartient le nœud. Dans la plage [0, N), où N correspond au nombre de nœuds dans le graphique.

Exemple

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 attribue des nœuds à des clusters à l'aide d'une technique de propagation de libellés, en commençant par un libellé initial qui peut utiliser des libellés de départ fournis dans l'entrée. À mesure que les nœuds adoptent de manière itérative l'étiquette partagée par la majorité de leurs voisins, les groupes densément connectés convergent vers une étiquette de consensus, formant ainsi des communautés. Pour en savoir plus sur l'algorithme, consultez Propagation d'étiquettes.

Signature de la fonction

LabelPropagation(input_parameters) YIELD node, cluster

Paramètres d'entrée

Tous les paramètres d'entrée courants et :

Nom	Type	Obligatoire	Par défaut	Description
seed_label_property	STRING	Non	(aucun)	Nom de la propriété de nœud pour l'étiquette de départ.
max_iterations	INT64	Non	10	Nombre maximal d'itérations de propagation d'étiquettes effectuées par l'algorithme. Doit être un nombre fini et positif.

Sortie

Résultats de la fonction :

Nom	Type	Description
nœud	GRAPH_ELEMENT (nœud)	Nœud du graphique.
cluster	INT64	ID du cluster/de l'étiquette propagé du nœud.

Exemple

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 identifie les communautés denses qui se chevauchent potentiellement et qui atteignent un seuil de densité minimal, de sorte que chaque clique (un groupe de nœuds où chaque nœud est connecté à tous les autres nœuds) est contenue dans au moins un cluster. Pour en savoir plus sur l'algorithme, consultez Agrégateur de cliques.

Signature de la fonction

CliqueFinding(input_parameters) YIELD node, clique

Remarque : Contrairement à la plupart des algorithmes, il peut y avoir plusieurs lignes pour le même nœud, car un nœud peut faire partie de plusieurs cliques.

Paramètres d'entrée

Tous les paramètres d'entrée courants et :

Nom	Type	Obligatoire	Par défaut	Description
min_density	FLOAT64	Non	0,9	Densité minimale des clusters à renvoyer. La valeur doit être comprise entre 0 et 1.

Sortie

Résultats de la fonction :

Nom	Type	Description
nœud	GRAPH_ELEMENT (nœud)	Nœud du graphique.
clique	INT64	ID de la clique à laquelle appartient le nœud.

Exemple

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é

Les algorithmes de similarité quantifient la ressemblance entre des paires de nœuds en fonction de la structure de leur voisinage. Cela est utile pour déduire les arêtes manquantes entre les nœuds pour la résolution d'entités, les recommandations et plus encore.

Spanner Graph est compatible avec les similarités de nœuds par paires suivantes, où les scores de similarité sont calculés en fonction des voisinages des nœuds.

• JaccardSimilarity : basé sur le ratio entre les voisins communs et le nombre total de voisins
• CosineSimilarity : basé sur les pondérations des arêtes des voisins communs
• CommonNeighborsSimilarity : en fonction du nombre de voisins partagés
• TotalNeighborsSimilarity : basé sur le nombre de voisins d'au moins l'un des deux nœuds.

Pour en savoir plus sur l'algorithme, consultez Similitude des nœuds par paire.

Ces quatre algorithmes partagent les mêmes arguments et la même structure de sortie.

Signature de la fonction

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

Paramètres d'entrée

Tous les paramètres d'entrée courants et :

Nom	Type	Obligatoire	Par défaut	Description
source_nodes	Tableau de nœuds de graphique	Oui	N/A	Nœuds sources pour le calcul de la similarité par paires.
target_nodes	Tableau de nœuds de graphique	Oui	N/A	Nœuds cibles pour le calcul de la similarité par paire.

Sortie

Résultats de la fonction :

Nom	Type	Description
source_node	GRAPH_ELEMENT (nœud)	Nœud source utilisé dans le calcul de similarité.
target_node	GRAPH_ELEMENT (nœud)	Nœud cible utilisé dans le calcul de la similarité.
similarité	FLOAT64	Score de similarité calculé entre le nœud source et le nœud cible.

Exemple

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;

Recherche de chemin

Les algorithmes de recherche de chemin calculent les itinéraires optimaux entre les nœuds. Cela est utile pour identifier l'itinéraire le moins cher dans les chaînes d'approvisionnement, évaluer la vulnérabilité en cybersécurité, etc.

ShortestPath

ShortestPath calcule les chemins les plus courts entre un ensemble donné de nœuds sources et un ensemble donné de nœuds cibles. Pour en savoir plus sur l'algorithme, consultez Chemins les plus courts de plusieurs à plusieurs.

Signature de la fonction

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

Paramètres d'entrée

Tous les paramètres d'entrée courants et :

Nom	Type	Obligatoire	Par défaut	Description
source_nodes	Tableau de nœuds de graphique	Oui	N/A	Nœuds sources pour le calcul du plus court chemin.
target_nodes	Tableau de nœuds de graphique	Oui	N/A	Nœuds cibles pour le calcul du chemin le plus court.

Sortie

Résultats de la fonction :

Nom	Type	Description
source_node	GRAPH_ELEMENT (nœud)	Nœud source du chemin d'accès.
target_node	GRAPH_ELEMENT (nœud)	Nœud cible du chemin d'accès.
chemin d'accès	GRAPH_PATH	Chemin le plus court trouvé.
coût	FLOAT64	Coût du chemin le plus court.

Exemple

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;

Étapes suivantes

• Algorithmes d'exécution de Spanner Graph.
• Exigences de schéma et compatibilité des fonctionnalités de l'algorithme Spanner Graph.
• Bonnes pratiques concernant les algorithmes Spanner Graph