Catálogo de algoritmos de Spanner Graph

Spanner Graph, en estrecha colaboración con Google Research Graph Mining, ofrece un conjunto de algoritmos que cubren las necesidades de análisis de grafos para los siguientes casos de uso:

Centralidad

Los algoritmos de centralidad clasifican los nodos según su importancia estructural dentro de un grafo. Puede ayudarte a identificar cuentas fraudulentas en fintech, influencers en gráficos sociales, routers críticos en redes de telecomunicaciones y mucho más.

PageRank

PageRank califica los nodos por importancia. Un nodo se considera más importante si muchos otros nodos importantes se vinculan a él. El algoritmo simula una caminata aleatoria a través del gráfico. Los nodos que se visitan con más frecuencia en este recorrido se consideran más importantes. Consulta PageRank para obtener detalles sobre el algoritmo.

Firma de la función

PageRank(input_parameters) YIELD node, score

Parámetros de entrada

Todos los parámetros de entrada comunes y los siguientes:

Nombre Tipo Obligatorio Predeterminado Descripción
source_nodes Array de nodos de grafo No (ninguno) Si está presente, es la fuente del PageRank personalizado.
damping_factor FLOAT64 No 0.85 Es la probabilidad de que, en cualquier iteración determinada, el algoritmo elija recorrer uno de los bordes salientes del nodo actual. Debe estar en el rango de [0, 1).
max_iterations INT64 No 10 Es la cantidad máxima de iteraciones del algoritmo. Debe ser positivo. Una mayor cantidad de iteraciones tiende a producir resultados más precisos a costa de un tiempo de ejecución más largo.
approx_precision FLOAT64 No 1e-2 Es el umbral de precisión de aproximación para el algoritmo. Debe ser un valor no negativo. Los valores más pequeños tienden a producir resultados más precisos a costa de un tiempo de ejecución más largo.

Salida

La función produce:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del grafo.
puntuación FLOAT64 Es la puntuación de PageRank del nodo.

Ejemplo

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

La BetweennessCentrality mide la frecuencia con la que un nodo se encuentra en las rutas más cortas entre otros pares de nodos. Los nodos con una alta centralidad de intermediación suelen actuar como puentes críticos que conectan diferentes partes del grafo. Consulta centralidad de intermediación para obtener detalles del algoritmo.

Firma de la función

BetweennessCentrality(input_parameters) YIELD node, score

Parámetros de entrada

Todos los parámetros de entrada comunes y los siguientes:

Nombre Tipo Obligatorio Predeterminado Descripción
num_source_nodes INT64 No (ninguno) Si se establece, debe ser positivo y especifica cuántos nodos de origen debe seleccionar el algoritmo para calcular las centralidades de intermediación aproximadas. Si no se establece o se establece en un número mayor que la cantidad de nodos en el grafo, todos los nodos se usan como nodos de origen, es decir, el algoritmo calcula las centralidades de intermediación exactas. Los valores más altos generan mejores aproximaciones, pero también tiempos de ejecución más largos.

Salida

La función produce:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del gráfico.
puntuación FLOAT64 Es la puntuación de centralidad del nodo.

Ejemplo

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

La ClosenessCentrality mide qué tan cerca está un nodo de todos los demás nodos del grafo. Los nodos con una alta centralidad de cercanía pueden llegar a otros nodos a través de rutas más cortas. Consulta la centralidad de cercanía para obtener detalles del algoritmo.

Firma de la función

ClosenessCentrality(input_parameters) YIELD node, score

Parámetros de entrada

Todos los parámetros de entrada comunes y los siguientes:

Nombre Tipo Obligatorio Predeterminado Descripción
Standard STRING No EXACTA Es el modo del algoritmo. Los valores admitidos son EXACT y HYBRID.
use_wasserman_faust BOOL No FALSO Si es false, calcula las medidas de centralidad de cercanía estándar. Si es true, calcula las centralidades de cercanía de Wasserman-Faust.
épsilon FLOAT64 No 0.1 Solo se usa para el algoritmo HYBRID. Debe estar en el rango (0.0, 1.0). En general, los valores más bajos significan una mayor precisión. Por lo general, los valores más grandes permiten que el algoritmo se ejecute más rápido.
sample_size INT64 No 0 Solo se usa para el algoritmo HYBRID. Es la cantidad de nodos de pivote que se usarán para calcular de forma aproximada los valores de centralidad. Must be non-negative (La precisión de las coordenadas de latitud y longitud, en metros. No debe ser un valor negativo). Si no se establece o es cero, se usa un valor predeterminado de min(100 * ln(N), N), donde N es el recuento de nodos del gráfico de entrada.

Salida

La función produce:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del grafo.
puntuación FLOAT64 Es la puntuación de centralidad de cercanía del nodo.

Ejemplo

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;

Agrupamiento en clústeres

Los algoritmos de agrupamiento en clústeres agrupan los nodos en clústeres (también conocidos como comunidades) de modo que los nodos de cada clúster estén conectados de forma más densa entre sí que con los nodos de otros clústeres. Esto es útil para detectar posibles redes de fraude en tecnología financiera, identificar segmentaciones de clientes en el comercio minorista y mucho más.

WeaklyConnectedComponents

WeaklyConnectedComponents encuentra conjuntos disjuntos de nodos de modo que se pueda acceder a cada nodo de un conjunto desde cualquier otro nodo del mismo conjunto, pero no desde nodos de otros conjuntos. Consulta componentes conectados para obtener detalles sobre el algoritmo.

Firma de la función

WeaklyConnectedComponents(input_parameters) YIELD node, cluster

Parámetros de entrada

Todos los parámetros de entrada comunes

Salida

La función produce:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del grafo.
clúster INT64 Es el ID del componente o clúster conectado al que pertenece el nodo. En el rango [0, N), donde N es la cantidad de nodos en el gráfico.

Ejemplo

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 el grafo en clústeres optimizando la modularidad, una medida de calidad de la densidad de conexiones dentro de los clústeres en comparación con lo que se esperaría en una red aleatoria. Consulta el agrupamiento en clústeres de modularidad para obtener detalles del algoritmo.

Firma de la función

ModularityClustering(input_parameters) YIELD node, cluster

Parámetros de entrada

Todos los parámetros de entrada comunes y los siguientes:

Nombre Tipo Obligatorio Predeterminado Descripción
resolution FLOAT64 No 1.0 Controla el nivel de detalle de la agrupación en clústeres. Debe ser finito y no negativo. Los valores de resolución más pequeños suelen generar clústeres más grandes. Los valores típicos se encuentran en el rango [0.5, 5]. Cuando la resolución es cero, el algoritmo (con una cantidad suficiente de iteraciones) encuentra los componentes conectados del grafo (ignorando las aristas cuyo peso es cero).
max_iterations INT64 No 10 Es la cantidad máxima de iteraciones externas del algoritmo. Debe ser positivo. Los valores más grandes suelen generar agrupamientos de mayor calidad a costa de un tiempo de ejecución más largo.
max_inner_iterations INT64 No 10 Es la cantidad máxima de iteraciones internas del algoritmo. Debe ser positivo. Los valores más grandes suelen generar agrupamientos de mayor calidad a costa de un tiempo de ejecución más largo.

Salida

La función produce:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del gráfico.
clúster INT64 Es el ID de la comunidad o el clúster al que pertenece el nodo. En el rango de [0, N), donde N es la cantidad de nodos en el grafo.

Ejemplo

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 divide los nodos en función de su similitud o diferencia por pares, con el objetivo de agrupar los nodos similares y separar los diferentes. Consulta agrupamiento por correlación para obtener detalles sobre el algoritmo.

Firma de la función

CorrelationClustering(input_parameters) YIELD node, cluster

Parámetros de entrada

Todos los parámetros de entrada comunes y los siguientes:

Nombre Tipo Obligatorio Predeterminado Descripción
resolution FLOAT64 Sí (ninguno) Controla el nivel de detalle del agrupamiento en clústeres. El cliente debe definirlo de forma explícita. Debe ser finito y no negativo. Los valores más pequeños tienden a generar clústeres más grandes. Cuando la resolución es cero y todos los pesos de las aristas son positivos, el algoritmo (con una cantidad suficiente de iteraciones) encuentra los componentes conectados del grafo.
max_iterations INT64 No 10 Es la cantidad máxima de iteraciones externas del algoritmo. Debe ser positivo. Los valores más grandes suelen generar agrupamientos de mayor calidad a costa de un tiempo de ejecución más largo.
max_inner_iterations INT64 No 10 Es la cantidad máxima de iteraciones internas del algoritmo. Debe ser positivo. Los valores más grandes suelen generar agrupamientos de mayor calidad a costa de un tiempo de ejecución más largo.

Salida

La función produce:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del grafo.
clúster INT64 Es el ID de la comunidad o el clúster al que pertenece el nodo. En el rango de [0, N), donde N es la cantidad de nodos en el grafo.

Ejemplo

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 asigna nodos a clústeres con una técnica de propagación de etiquetas, comenzando por un etiquetado inicial que puede usar etiquetas de origen proporcionadas en la entrada. A medida que los nodos adoptan de forma iterativa la etiqueta que comparte la mayoría de sus vecinos, los grupos densamente conectados convergen en una etiqueta de consenso, lo que forma comunidades. Consulta propagación de etiquetas para obtener detalles del algoritmo.

Firma de la función

LabelPropagation(input_parameters) YIELD node, cluster

Parámetros de entrada

Todos los parámetros de entrada comunes y los siguientes:

Nombre Tipo Obligatorio Predeterminado Descripción
seed_label_property STRING No (ninguno) Es el nombre de la propiedad del nodo para la etiqueta de origen.
max_iterations INT64 No 10 Es la cantidad máxima de iteraciones de propagación de etiquetas que realiza el algoritmo. Debe ser finito y positivo.

Salida

La función produce:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del grafo.
clúster INT64 Es el ID de clúster o etiqueta propagado del nodo.

Ejemplo

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 se superponen potencialmente y que cumplen con un umbral de densidad mínimo, de modo que cada camarilla (un grupo de nodos en el que cada nodo está conectado a todos los demás nodos) se incluye en al menos un clúster. Consulta agregador de camarillas para obtener detalles sobre el algoritmo.

Firma de la función

CliqueFinding(input_parameters) YIELD node, clique

Nota: A diferencia de la mayoría de los algoritmos, puede haber varias filas para el mismo nodo, ya que un nodo puede formar parte de muchas camarillas.

Parámetros de entrada

Todos los parámetros de entrada comunes y los siguientes:

Nombre Tipo Obligatorio Predeterminado Descripción
min_density FLOAT64 No 0.9 Es la densidad mínima de los clústeres que se devolverán. Debe estar en [0, 1].

Salida

La función produce:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del grafo.
clique INT64 Es el ID de la clique a la que pertenece el nodo.

Ejemplo

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;

Similitud

Los algoritmos de similitud cuantifican qué tan parecidos son los pares de nodos según la estructura de sus vecindades. Esto es útil para inferir los bordes faltantes entre los nodos para la resolución de entidades, la recomendación y mucho más.

Spanner Graph admite las siguientes similitudes de nodos por pares, en las que las puntuaciones de similitud se calculan en función de los vecindarios de los nodos.

  • JaccardSimilarity: Se basa en la proporción de vecinos comunes con respecto a la cantidad total de vecinos.
  • CosineSimilarity: Se basa en los pesos de las aristas de los vecinos comunes.
  • CommonNeighborsSimilarity: Según la cantidad de vecinos compartidos
  • TotalNeighborsSimilarity: Se basa en la cantidad de vecinos de, al menos, uno de los dos nodos.

Consulta la similitud de nodos por pares para obtener detalles del algoritmo.

Estos cuatro algoritmos comparten los mismos argumentos y la misma estructura de salida.

Firma de la función

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

Parámetros de entrada

Todos los parámetros de entrada comunes y los siguientes:

Nombre Tipo Obligatorio Predeterminado Descripción
source_nodes Array de nodos de grafo Sí N/A Son los nodos de origen para el cálculo de la similitud por pares.
target_nodes Array de nodos de grafo Sí N/A Son los nodos objetivo para el cálculo de la similitud por pares.

Salida

La función produce:

Nombre Tipo Descripción
source_node GRAPH_ELEMENT (nodo) Es el nodo de origen que se usa en el cálculo de similitud.
target_node GRAPH_ELEMENT (nodo) Es el nodo de destino que se usa en el cálculo de similitud.
similitud FLOAT64 Es la puntuación de similitud calculada entre el nodo de origen y el de destino.

Ejemplo

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;

Búsqueda de rutas

Los algoritmos de búsqueda de rutas calculan las rutas óptimas entre nodos. Esto es útil para identificar la ruta más económica en las cadenas de suministro, evaluar la vulnerabilidad en la ciberseguridad y mucho más.

ShortestPath

ShortestPath calcula las rutas más cortas entre un conjunto determinado de nodos de origen y un conjunto determinado de nodos de destino. Consulta Rutas más cortas de varios a varios para obtener detalles sobre el algoritmo.

Firma de la función

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

Parámetros de entrada

Todos los parámetros de entrada comunes y los siguientes:

Nombre Tipo Obligatorio Predeterminado Descripción
source_nodes Array de nodos de grafo Sí N/A Son los nodos de origen para el cálculo de la ruta más corta.
target_nodes Array de nodos de grafo Sí N/A Son los nodos de destino para el cálculo de la ruta más corta.

Salida

La función produce:

Nombre Tipo Descripción
source_node GRAPH_ELEMENT (nodo) Es el nodo de origen de la ruta de acceso.
target_node GRAPH_ELEMENT (nodo) Es el nodo de destino de la ruta de acceso.
ruta de acceso GRAPH_PATH Es la ruta más corta que se encontró.
costo FLOAT64 El costo de la ruta más corta.

Ejemplo

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;

¿Qué sigue?