Catalogue des algorithmes Spanner Graph

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é

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 graphique. Les nœuds visités plus souvent au cours de cette promenade sont considérés comme plus importants. Pour en savoir plus sur l'algorithme, consultez PageRank.

Signature de 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 double Non 0,85 Probabilité que, à une itération donnée, l'algorithme choisisse de parcourir l'un des bords sortants du nœud actuel. La valeur doit être comprise dans la plage [0, 1).
max_iterations int Non 10 Nombre maximal d'itérations de l'algorithme. Doit être positive. Un nombre d'itérations plus élevé a tendance à produire des résultats plus précis, mais au prix d'un temps d'exécution plus long.
approx_precision double Non 1e-2 Seuil de précision d'approximation pour l'algorithme. Cette valeur ne doit pas être négative. Des valeurs plus petites ont tendance à produire des résultats plus précis, 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) Nœud du 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 avec une centralité d'intermédiarité élevée 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 fonction

BetweennessCentrality(input_parameters) YIELD node, centrality

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) Si cette valeur est définie, elle doit être positive et spécifie le nombre de nœuds sources que l'algorithme doit sélectionner pour calculer les centralités de degré intermédiaire approximatives. S'il n'est pas défini ou s'il est défini 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) Nœud du graphique.
centralité 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, centrality
RETURN node.id, centrality;

ClosenessCentrality

ClosenessCentrality mesure la proximité d'un nœud par rapport à tous les autres nœuds du graphique. Les nœuds avec une centralité de proximité élevée peuvent atteindre d'autres nœuds par des chemins plus courts. Pour en savoir plus sur l'algorithme, consultez Centralité de proximité.

Signature de fonction

ClosenessCentrality(input_parameters) YIELD node, centrality

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", calcule 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. En général, plus la valeur est faible, plus la précision est é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, une valeur par défaut de 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.
centralité 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, centrality
RETURN node.id, centrality;

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 soient plus densément connectés les uns aux autres qu'aux nœuds d'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 trouve des ensembles disjoints de nœuds de sorte que chaque nœud d'un ensemble soit accessible à partir de n'importe quel autre nœud du même ensemble, mais pas à partir des nœuds d'autres ensembles. Pour en savoir plus sur l'algorithme, consultez Composants connectés.

Signature de fonction

WeaklyConnectedComponents(input_parameters) YIELD node, cluster

Paramètres d'entrée

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

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 correspond au nombre de nœuds dans le graphique.

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 graphique 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 la section Clustering par modularité.

Signature de 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 double Non 1.0 Contrôle la précision du clustering. Doit être finie et non négative. Des valeurs de résolution plus faibles ont tendance à entraîner des clusters plus grands. Les valeurs types sont comprises dans la plage [0,5, 5]. Lorsque la résolution est nulle, l'algorithme (avec un nombre suffisant d'itérations) trouve les composants connectés du graphique (en ignorant les arêtes dont le poids est nul).
max_iterations int 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é, mais au prix d'un temps d'exécution plus long.
max_inner_iterations int 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) Nœud du 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 par corrélation.

Signature de 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 double Oui (aucun) Contrôle la précision du clustering. Doit être explicitement défini par le client. Doit être finie et non négative. Les valeurs plus petites ont tendance à générer des clusters plus grands. Lorsque la résolution est nulle et que tous les poids des arêtes sont positifs, l'algorithme (avec un nombre suffisant d'itérations) trouve les composants connectés du graphique.
max_iterations int 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é, mais au prix d'un temps d'exécution plus long.
max_inner_iterations int 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) Nœud du 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 le libellé partagé par la majorité de leurs voisins, les groupes densément connectés convergent vers un libellé de consensus, formant ainsi des communautés. Pour en savoir plus sur l'algorithme, consultez la section Propagation des libellés.

Signature de 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é du nœud pour le libellé de départ.
max_iterations int Non 10 Nombre maximal d'itérations de propagation des libellés effectuées par l'algorithme. Doit être finie et positive.

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 potentiellement chevauchantes qui répondent à 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 contenu dans au moins un cluster. Pour en savoir plus sur l'algorithme, consultez Agrégateur de cliques.

Signature de 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 double 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 leurs quartiers. 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 quartiers des nœuds.

  • JaccardSimilarity : basé sur le ratio de voisins communs par rapport au nombre total de voisins
  • CosineSimilarity : basé sur les pondérations des arêtes des voisins communs
  • CommonNeighborsSimilarity : basé sur le 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 Similarité par paire des nœuds.

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

Signature de 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 Oui N/A
target_nodes Tableau de nœuds Oui N/A

Sortie

Résultats de la fonction :

Nom Type Description
source_node GRAPH_ELEMENT (nœud) Nœud source utilisé dans le calcul de la 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 peut être utile pour identifier l'itinéraire le moins cher dans les chaînes d'approvisionnement, évaluer la vulnérabilité en matière de cybersécurité et plus encore.

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 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 Oui N/A
target_nodes Tableau de nœuds Oui N/A

Sortie

Résultats de la fonction :

Nom Type Description
source_node GRAPH_ELEMENT (nœud) Nœud source du chemin.
target_node GRAPH_ELEMENT (nœud) Nœud cible du chemin.
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