El algoritmo de vecinos comunes o Common Neighbors es un tipo de algoritmo diseñado para estudiar la predicción de enlaces dentro de las estructuras de un grafo. Este posee un funcionamiento particular que depende de la aplicación de una formula matemática y en esta entrada conoceremos información muy importante sobre él. A continuación, descubrirás de que se ocupa este algoritmo disponible en la biblioteca de Neo4j y desarrollaremos un ejemplo práctico para comprender mejor su funcionamiento.

¿Qué es el algoritmo de vecinos comunes?

Este algoritmo conocido como algoritmo de vecinos comunes funciona bajo el principio de captar la idea de que dos elementos extraños, tienen un elemento en común, tienen más posibilidades de conectarse entre si, que elementos que no posean ningún «amigo» en común. Para demostrar esta suposición se aplica una formula matemática que te presentaremos a continuación:

Esta formula nos permite determinar si dos nodos que comparten relación con un nodo en común pueden establecer alguna consexión. Dentro de esta formula tenemos que  N (x) es el conjunto de nodos adyacentes al nodo x, y N (y) es el conjunto de nodos adyacentes al nodo y. En cuanto a los valores que arroja esta formula, un valor 0 o cercano, indica que los nodos en estudio no están cerca, mientras que los valores más elevados indican que dichos vértices están más cerca.

Ejemplo de aplicación del algoritmo de vecinos comunes

Para comprender el alcance y la funcionalidad de este importante algoritmo de predicción de enlaces, vamos a desarrollar un ejemplo de trabajo en Neo4j. Procederemos en primer lugar a construir un grafo que contendrá algunos nodos con información detallada. A cada uno de los nodos del grafo le designaremos nombres, simulando el entorno de interacción de una red social. Una vez designados los nombres de cada uno de los vértices, agregaremos características o categorías que nos permitirán entender las relaciones o conexiones de los nodos entre sí.

Creamos el grafo de la siguiente forma:

MERGE (zhen:Person {name: "Zhen"})
MERGE (praveena:Person {name: "Praveena"})
MERGE (michael:Person {name: "Michael"})
MERGE (arya:Person {name: "Arya"})
MERGE (karin:Person {name: "Karin"})

MERGE (zhen)-[:FRIENDS]-(arya)
MERGE (zhen)-[:FRIENDS]-(praveena)
MERGE (praveena)-[:WORKS_WITH]-(karin)
MERGE (praveena)-[:FRIENDS]-(michael)
MERGE (michael)-[:WORKS_WITH]-(karin)
MERGE (arya)-[:FRIENDS]-(karin)

Una vez creado el grafo, ejecutaremos el algoritmo, solicitando el análisis de dos nodos solamente en Cypher. Para ejecutar la consulta, debemos hacerlo de la siguiente forma:

MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN algo.linkprediction.commonNeighbors(p1, p2) AS score

score
1.0

El resultado nos explica de forma clara y precisa que existe un tipo de relación directa entre los vértices estudiados. Ahora bien, podemos realizar consultas más especificas para conocer más información sobre los datos suministrados. Podemos ahora consultar en Cypher específicamente sobre el tipo de relación que rige a los vértices.

MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN algo.linkprediction.commonNeighbors(p1, p2, {relationshipQuery: "FRIENDS"}) AS score

score
0.0

El resultado en este caso nos indica que no existe relación entre los nodos de la forma que hemos consultado.

Esperamos que esta información sea de utilidad para comprender de mejor manera este importante algoritmo de predicción de enlaces.

Visita más de Grapheverywhere para descubrir todo lo que necesitas sobre algoritmos de análisis de grafos.