El algoritmo de asignación de recursos forma parte de la familia de algoritmos que se utilizan para predecir el comportamiento de enlaces en los grafos. Este algoritmo que forma parte de la biblioteca de Neo4j tiene un funcionamiento importante y nos permite calcular la cercanía de los nodos en función de sus vecinos compartidos. A continuación, conoceremos la formula que rige a este algoritmo y ejecutaremos un ejemplo para comprender más a detalle las potencialidades del algoritmo.

¿Cómo funciona el algoritmo de asignación de recursos?

Este algoritmo de asignación de recursos nos ofrece una medida con la que podemos estimar con precisión la cercanía entre vértices pertenecientes a un grafo, tomando como principal referencia la función de sus vecinos compartidos. El algoritmo toma como teoría principal de desarrollo los conceptos presentados en el año 2009 por Tao Zhou, Linyuan Lü y Yi-Cheng Zhang que forma parte de un estudio desarrollado para predecir enlaces en varias redes.

Su funcionamiento esta regido por la siguiente formula:

Donde N(u) es el conjunto de nodos adyacentes a u. Dentro de los resultados que podemos obtener con este algoritmo se tiene que los valores 0 indican que los nodos que son objeto de estudio no están cerca, mientras que en el caso de valores altos indican que los nodos están más cerca.

A continuación presentaremos un ejemplo desarrollado en Neo4j para comprender de mejor manera la ejecución del algoritmo.

Ejemplo de ejecución del algoritmo

Para comprender a profundidad la ejecución del algoritmo de asignación de recursos desarrollaremos un ejemplo construyendo un grafo con diversos nodos donde se designarán algunos nombres y se establecerán relaciones para estudiar la cercanía de estos vértices.

En primer lugar se construye 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)

Posteriormente a que se construya el grafo, procedemos a ejecutar la función del algoritmo para obtener los resultados tomando dos vértices especificos.

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

 

score
0.5

Ahora, también podemos analizar los nodos que componen el grafo tomando solo en cuenta las relaciones que conectan a los elementos del grafo.

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

score
0.0

Esperamos que esta indormación sea de utilidad para comprender de mejor manera el funcionamiento de los algoritmos de predicción de enlaces.

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