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 según su 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 la página de clasificación 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 lo siguiente:

Nombre Tipo Obligatorio Predeterminado Descripción
source_nodes Es un array de nodos del gráfico. No (ninguno) Si está presente, es la fuente del PageRank personalizado.
damping_factor double No 0.85 Es la probabilidad de que, en cualquier iteración determinada, el algoritmo elija recorrer una de las aristas salientes del nodo actual. Debe estar en el rango de [0, 1).
max_iterations int 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 double No 1e-2 Es el umbral de precisión de aproximación del algoritmo. Debe ser 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 lo siguiente:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del gráfico.
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

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 gráfico. Consulta centralidad de intermediación para obtener detalles sobre el algoritmo.

Firma de la función

BetweennessCentrality(input_parameters) YIELD node, centrality

Parámetros de entrada

Todos los parámetros de entrada comunes y lo siguiente:

Nombre Tipo Obligatorio Predeterminado Descripción
num_source_nodes INT64 No (ninguno) Si se configura, debe ser positivo y especificar cuántos nodos de origen debe seleccionar el algoritmo para calcular las centralidades aproximadas de intermediación. Si no se establece o se establece en un número mayor que la cantidad de nodos del gráfico, se usan todos los nodos 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 lo siguiente:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del gráfico.
centralidad 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, centrality
RETURN node.id, centrality;

ClosenessCentrality

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

Firma de la función

ClosenessCentrality(input_parameters) YIELD node, centrality

Parámetros de entrada

Todos los parámetros de entrada comunes y lo siguiente:

Nombre Tipo Obligatorio Predeterminado Descripción
Standard STRING No EXACT Es el modo del algoritmo. Los valores admitidos son EXACT y HYBRID.
use_wasserman_faust BOOL No FALSO Si es "false", se calculan las centralidades de cercanía estándar. Si es "true", se calculan las medidas de centralidad 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 pequeños 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 aproximadamente 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 lo siguiente:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del gráfico.
centralidad 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, centrality
RETURN node.id, centrality;

Agrupamiento en clústeres

Los algoritmos de agrupamiento agrupan los nodos en clústeres (también conocidos como comunidades) de modo que los nodos dentro de cada clúster estén más densamente conectados entre sí que con los nodos de otros clústeres. Esto es útil para detectar posibles redes de fraude en fintech, 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 lo siguiente:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del gráfico.
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 las conexiones dentro de los clústeres en comparación con lo que se esperaría en una red aleatoria. Consulta agrupamiento por modularidad para obtener detalles sobre el algoritmo.

Firma de la función

ModularityClustering(input_parameters) YIELD node, cluster

Parámetros de entrada

Todos los parámetros de entrada comunes y lo siguiente:

Nombre Tipo Obligatorio Predeterminado Descripción
resolution double 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 tienden a 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 int No 10 Es la cantidad máxima de iteraciones externas del algoritmo. Debe ser positivo. Los valores más grandes tienden a generar agrupamientos de mayor calidad a costa de un tiempo de ejecución más largo.
max_inner_iterations int No 10 Es la cantidad máxima de iteraciones internas del algoritmo. Debe ser positivo. Los valores más grandes tienden a generar agrupamientos de mayor calidad a costa de un tiempo de ejecución más largo.

Salida

La función produce lo siguiente:

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 [0, N), donde N es la cantidad de nodos en el gráfico.

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 particiona los nodos según 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 lo siguiente:

Nombre Tipo Obligatorio Predeterminado Descripción
resolution double Sí (ninguno) Controla el nivel de detalle de la agrupación 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 los bordes son positivos, el algoritmo (con una cantidad suficiente de iteraciones) encuentra los componentes conectados del grafo.
max_iterations int No 10 Es la cantidad máxima de iteraciones externas del algoritmo. Debe ser positivo. Los valores más grandes tienden a generar agrupamientos de mayor calidad a costa de un tiempo de ejecución más largo.
max_inner_iterations int No 10 Es la cantidad máxima de iteraciones internas del algoritmo. Debe ser positivo. Los valores más grandes tienden a generar agrupamientos de mayor calidad a costa de un tiempo de ejecución más largo.

Salida

La función produce lo siguiente:

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 [0, N), donde N es la cantidad de nodos en el gráfico.

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 con un etiquetado inicial que puede usar etiquetas iniciales 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 lo siguiente:

Nombre Tipo Obligatorio Predeterminado Descripción
seed_label_property cadena No (ninguno) Es el nombre de la propiedad del nodo para la etiqueta de semilla.
max_iterations int 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 lo siguiente:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del gráfico.
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 el agregador de clics 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 muchos clics.

Parámetros de entrada

Todos los parámetros de entrada comunes y lo siguiente:

Nombre Tipo Obligatorio Predeterminado Descripción
min_density double 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 lo siguiente:

Nombre Tipo Descripción
nodo GRAPH_ELEMENT (nodo) Es un nodo del gráfico.
clique INT64 Es el ID de la camarilla 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 las aristas faltantes entre los nodos para la resolución de entidades, las recomendaciones 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 las vecindades 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: Basado en la cantidad de vecinos compartidos
  • TotalNeighborsSimilarity: Se basa en la cantidad de vecinos de al menos uno de los dos nodos.

Consulta 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 lo siguiente:

Nombre Tipo Obligatorio Predeterminado Descripción
source_nodes Es un array de nodos. Sí N/A
target_nodes Es un array de nodos. Sí N/A

Salida

La función produce lo siguiente:

Nombre Tipo Descripción
source_node GRAPH_ELEMENT (nodo) Es el nodo fuente que se usa en el cálculo de similitud.
target_node GRAPH_ELEMENT (nodo) Es el nodo objetivo 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 ruta

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 muchos a muchos 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 lo siguiente:

Nombre Tipo Obligatorio Predeterminado Descripción
source_nodes Es un array de nodos. Sí N/A
target_nodes Es un array de nodos. Sí N/A

Salida

La función produce lo siguiente:

Nombre Tipo Descripción
source_node GRAPH_ELEMENT (nodo) Es el nodo de origen de la ruta.
target_node GRAPH_ELEMENT (nodo) Es el nodo de destino de la ruta.
ruta de acceso GRAPH_PATH Es la ruta más corta que se encontró.
costo FLOAT64 Es 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?