El algoritmo Adamic Adar es uno de los miembros de la familia de algoritmos de predicción de enlaces que encontramos en la biblioteca del poderoso Neo4j. Este toma como base de su funcionamiento el indice Adamic/Adar que nos ayuda a predecir enlaces en entornos de redes sociales. A continuación conoceremos un poco más sobre su funcionamiento, la formula que rige su funcionamiento y tendremos a disposición un ejemplo desarrollado en los módulos de consulta Cypher de Neo4j para entender a profundidad cómo aprovecharlo.

¿Qué es el algoritmo Adamic Adar?

Este importante algoritmo denominado Adamic Adar toma su nombre por indice presentado por Lada Adamic y Eytan Adar en el año 2003. Su indice esta creado para predecir enlaces en entornos de redes sociales inter-conectadas, de acuerdo con la cantidad de enlaces compartidos entre dos vértices pertenecientes a un grafo. Este en otros términos se define como la suma de la centralidad del grado logarítmico inverso de los vecinos compartidos por ambos nodos.

Veamos a continuación la formula que rige su funcionamiento.

Formula del algoritmo Adamic Adar

Para obtener el indice Adamic Adar, debemos aplicar la formula matemática que presentamos a continuación:

Dentro de esta formula se tiene que N (u) es el conjunto de nodos adyacentes a u. Para analizar sus valores debemos considerar que un valor de 0 indica que dos nodos no están cerca, mientras que los valores más altos indican que los nodos están más cerca.

Veamos a continuación un ejemplo aplicado a un grafo para entender de mejor manera su funcionamiento.

Ejemplo de aplicación

Para comprender a profundidad el funcionamiento del algoritmo procederemos a crear en primer lugar un grafo con un diversos nodos en los que registraremos los nombres de los miembros de una red social. Adicionalmente asignaremos a dichos miembros algunas características y etiquetas que nos permitan comprender las relaciones existentes entre ellos.  A algunos le añadiremos la categoría de amigos y a otros la categoría de compañeros de trabajo y analizaremos la relación entre los nodos con el algoritmo.

Se construye el grafo de las forma siguiente:

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 construido el grafo, procedemos a ejecutar la consulta respectiva en Cypher para obtener los resultados que nos indican que tan relacionados o conectados están los nodos pertenecientes al grafo. Para esta consulta ejecutaremos el algoritmo en base a solo un par de nodos de los que están contenidos en el grafo, independientemente de la categorización que estos tengan.

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

 

score
1.4426950408889634

Obtenidos los resultados, podemos ejecutar una consulta especifica en base a los nodos que deseemos consultar. En este caso ejecutaremos la consulta entre los vértices denominados como Michael y y Karin, tomando en cuenta únicamente la categoría de «amigos» que fue preestablecida en el grafo y asignada solo a algunos nodos.

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

score
0.0

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

Visita más de Grapheverywhere para conocer más acerca de los algoritmos de análisis de grafos y sus múltiples potencialidades.