Saltearse al contenido

Algoritmos de grafos

Los algoritmos de grafos se ejecutan dentro del motor como CALL algo.<name>(…). Cada uno produce una fila por nodo (o una fila por destino alcanzable), así que los combinas con MATCH, WITH, ORDER BY y RETURN como cualquier otra consulta. Son exactos (sin muestreo), deterministas y respetan el timeout de la consulta.

Los ejemplos usan este grafo:

CREATE (a:Person {name: 'Alice'}), (b:Person {name: 'Bob'}), (c:Person {name: 'Carol'}),
(d:Person {name: 'Dave'}), (e:Person {name: 'Eve'}),
(a)-[:KNOWS {weight: 1.0}]->(b), (b)-[:KNOWS {weight: 1.0}]->(c),
(c)-[:KNOWS {weight: 5.0}]->(a), (a)-[:KNOWS {weight: 9.0}]->(c),
(d)-[:KNOWS {weight: 1.0}]->(e)

Llamar a un algoritmo

CALL algo.pagerank() YIELD node_id, score
MATCH (n:Person) WHERE id(n) = id(node_id)
RETURN n.name AS name, score
ORDER BY score DESC
{name: 'Carol', score: 0.408…}
{name: 'Alice', score: 0.390…}
{name: 'Eve', score: 0.081…}
{name: 'Bob', score: 0.077…}
{name: 'Dave', score: 0.044…}

Reglas que se aplican a todas las llamadas algo.*:

  • El CALL debe ser la primera cláusula de la consulta. Pasa las entradas (como el id de un nodo de origen) como parámetros en lugar de obtenerlas de un MATCH anterior.
  • node_id es una referencia a un nodo sin sus propiedades. Únelo de nuevo con MATCH (n) WHERE id(n) = id(node_id) para leer propiedades, como en el ejemplo.
  • Filtra sobre una columna producida con un WITH … WHERE posterior (YIELD … WHERE no está soportado).
  • Las opciones van en un único argumento de mapa. Una opción que el algoritmo no lee es un error que lista las opciones permitidas.

Proyecciones

Todos los algoritmos aceptan tres opciones de proyección que seleccionan el subgrafo sobre el que se ejecutan:

OpciónPor defectoSignificado
labelstodos los nodosSolo los nodos con alguno de estos labels (el subgrafo inducido).
edge_typestodos los tiposSolo estos tipos de relación.
direction'natural''natural' (dirección almacenada), 'reverse' o 'undirected'.
CALL algo.pagerank({labels: ['Person'], edge_types: ['KNOWS'], direction: 'undirected', damping: 0.9})
YIELD node_id, score
RETURN node_id, score ORDER BY score DESC LIMIT 10

Referencia

ProcedimientoProduceOpciones (además de las proyecciones)
algo.pageranknode_id, scoredamping (0.85), max_iterations (100), tolerance (1e-6)
algo.wccnode_id, component—
algo.sccnode_id, component—
algo.degreenode_id, in_degree, out_degree, degree—
algo.triangle_countnode_id, triangles, coefficient—
algo.label_propagationnode_id, communitymax_iterations (10)
algo.louvainnode_id, communitymax_levels (10), max_iterations (10), tolerance (1e-4)
algo.betweennessnode_id, score—
algo.shortest_pathnode_id, distance, hops, pathsource (obligatoria), target, weighted (false)
algo.fastRPnode_id, embeddingdimension (256), iterations, iteration_weights ([0.0, 1.0, 1.0, 1.0]), normalization_strength (0.0), seed (42)

Componentes conexas

wcc trata el grafo como no dirigido (componentes débilmente conexas); scc sigue las direcciones (componentes fuertemente conexas, es decir, ciclos dirigidos). Los ids de componente son deterministas.

CALL algo.wcc() YIELD node_id, component
MATCH (n) WHERE id(n) = id(node_id)
RETURN component, collect(n.name) AS members ORDER BY component
// {component: 0, members: ['Alice', 'Bob', 'Carol']}
// {component: 1, members: ['Dave', 'Eve']}

Grado

CALL algo.degree() YIELD node_id, in_degree, out_degree, degree
MATCH (n) WHERE id(n) = id(node_id)
RETURN n.name AS name, in_degree, out_degree, degree
ORDER BY degree DESC, name LIMIT 2
// {name: 'Alice', in_degree: 1, out_degree: 2, degree: 3}
// {name: 'Carol', in_degree: 2, out_degree: 1, degree: 3}

Triángulos y clustering

CALL algo.triangle_count({direction: 'undirected'}) YIELD node_id, triangles, coefficient
MATCH (n) WHERE id(n) = id(node_id)
RETURN n.name AS name, triangles, coefficient ORDER BY name
// Alice, Bob and Carol: 1 triangle, coefficient 1.0; Dave and Eve: 0

Comunidades

label_propagation es rápido y aproximado; louvain optimiza la modularidad.

CALL algo.louvain() YIELD node_id, community
RETURN count(DISTINCT community) AS communities
// {communities: 2}

Betweenness

Centralidad de intermediación (betweenness) de Brandes, exacta:

CALL algo.betweenness() YIELD node_id, score
MATCH (n) WHERE id(n) = id(node_id)
RETURN n.name AS name, score ORDER BY score DESC LIMIT 1
// {name: 'Alice', score: 1.0}

Camino más corto

source y target son ids de nodos (los strings que retorna id(n)), normalmente pasados como parámetros. Sin un target, la llamada retorna la distancia a cada nodo alcanzable desde el origen (saltos BFS; path es null):

CALL algo.shortest_path({source: $alice}) YIELD node_id, distance, hops
MATCH (n) WHERE id(n) = id(node_id)
RETURN n.name AS name, distance, hops ORDER BY hops, name
// {name: 'Alice', distance: 0.0, hops: 0}
// {name: 'Bob', distance: 1.0, hops: 1}
// {name: 'Carol', distance: 1.0, hops: 1}

Con un target retorna una fila, o ninguna cuando el destino no es alcanzable, y path contiene la secuencia de nodos con sus labels y propiedades:

CALL algo.shortest_path({source: $alice, target: $carol}) YIELD distance, hops, path
RETURN distance, hops, [n IN path | n.name] AS route
// {distance: 1.0, hops: 1, route: ['Alice', 'Carol']}

weighted: true ejecuta Dijkstra sobre la propiedad numérica weight de cada relación:

CALL algo.shortest_path({source: $alice, target: $carol, weighted: true})
YIELD distance, hops, path
RETURN distance, hops, [n IN path | n.name] AS route
// {distance: 2.0, hops: 2, route: ['Alice', 'Bob', 'Carol']}

Para un camino entre dos nodos con los que ya hiciste match, shortestPath(…) de Cypher es la forma de patrón.

Embeddings FastRP

FastRP calcula embeddings estructurales de nodos solo a partir de la forma del grafo, sin modelos ni servicios externos. El resultado es un vector que puedes guardar y buscar con un índice vectorial para encontrar nodos estructuralmente similares.

CALL algo.fastRP({dimension: 8, iterations: 3, seed: 42}) YIELD node_id, embedding
RETURN size(embedding) AS dim, count(*) AS nodes
// {dim: 8, nodes: 5}

El mismo (graph, options, seed) siempre produce los mismos embeddings.

Costo

Los algoritmos, salvo un shortest_path con destino, construyen el grafo proyectado en memoria y lo recorren completo, así que su costo crece con el tamaño de la proyección. Acótala con labels y edge_types, y sube --query-timeout en el servidor para grafos grandes. Un shortest_path con destino en la dirección natural solo lee la parte del grafo que explora.

Los agentes de IA pueden ejecutar los mismos algoritmos con la herramienta MCP graph_algorithm; consulta Servidor MCP.