The link-prediction problem

Predict the likelihood of a future association between two nodes

Dado un grafo G de |V| nodos o vertices, cuyos edges E(u,v) representan las uniones entre los nodos, los autores presentan distintos métodos para predecir una nueva interacción, a través de un Score, tal que la probabilidad para un E(u,v) u y v nodos que no se encontraban relacionados con anterioridad estén relacionados, será definido como Score(u,v).

Las métricas definidas para encontrar el Score fueron:

  • Graph distance: el Score(u,v) se mide como el negativo de la distancia del shortest path entre u y v. La noción tras de esta métrica es que las redes sociales son del tipo small world, donde los individuos están relacionados a través de cadenas cortas.
  • Common Neighbors: el Score(u,v) se mide como la cantidad de vecinos en común que tienen los nodos u y v (la intersección). La noción tras de esta métrica es que en las redes sociales se tienden a formar triángulos cerrados.
  • Jaccard coefficient: Tal como Jaccard propone, mide la probabilidad de que u y v tengan en común una feature f, que en este caso serían los vecinos de u y v. Luego Jaccard’s Coefficient será la relación entre los vecinos en común (Common Neighbors) y el total de amigos de ambos nodos (la suma).
  • Adamic/Adar (Frequency-Weighted Common Neighbors): el Score(u,v) se mide encontrando el amigo en común de u y v, denominemoslo z, y a z se le calcula la cantidad de edges. Luego el Score será 1 sobre el logaritmo de la cantidad de edges (o amigos) de z. La noción de esta métrica es que los nodos con menos amigos tenderán a juntarse más que aquellos que funcionan como hub, por lo que se le da más peso a las relaciones con menos amigos.
  • Preferential Attachment: el Score(u,v) se mide como la miltiplicación del total de amigos de u y del total de amigos de v. La noción tras esta métrica es que los nodos que tienden a tener muchos amigos seguirán teniendo muchos amigos (concepto de the rich get richer).
  • Katz (Exponentially Damped Path Counts): Se mide la cantidad de caminos de un nodo u a un nodo v de largo L multiplicado por un parámetro B (determinado de forma empírica) el cual se encuentra elevado al L. Se hace la sumatoria de L=1 hasta infinito. La noción tras esta métrica es que mientras más caminos hayan entre dos nodos, mayor será la probabilidad de que se conecten.
  • Hitting Time: El Score será el negativo del tiempo esperado en llegar del nodo u al nodo v, eligiendo caminos de forma random. El autor no especifica la noción tras esta métrica.
  • Rooted PageRank: Basado en el Hitting Time, pero añade un factor pi, tal que señale la proporción de “pasarse” del nodo buscado. El autor no especifica la noción tras esta métrica.

Finalmente los autores hacen un benchmark sobre la mejora del uso de los algoritmos. Algo muy criticable a esta lectura es la forma en que presentan los resultados. Per se las predicciones de link prediction tienen muy bajo índice de acierto. Por lo anterior el resultado en bruto es bastante malo al compararlo con un ground-true directamente. Lo que los autores hacen es presentar la mejora frente a predicciones random (en vez del ground true) tal que se muestra que tanto es mejor la métrica frente al correr un random.

Frente a lo anterior, los que han resultado mejor son Adamic/Adar y Katz waighted (el parámetro encontrado con esta tecnica). Los que peor rendimiento tuvieron fueron Graph distance y Hitting time. Luego al hacer la comparación con Graph distance, se ve que la mejora entre uno y otro método no es tanto mejor. Por ultimo al ver el comportamiento con distintas redes, algunas métricas dieron mejores resultados con algunas redes y otros con otras.

Finalmente y como cierre a esta crítica, creo que es una buena lectura. Los métodos presentados son simples y fáciles de aplicar, existen gran cantidad de librerías que trabajan con grafos de forma rápido, por lo que realizar predicciones ya sea para generar eventualmente una lista de recomendación o no, es bastante simple. En cuanto a la lectura, lo malo es que la mejora o calidad de la predicción no es buena, lo que no queda claro en la lectura pues hacen la comparación con cuanto mejora versus a predicciones random, y no frente a un ground true. Otro punto negativo es que no muestran métricas de tiempo y performance. Como se mencionó existen muchas librerías optimizadas para trabajar con grafos, por lo que faltó un análisis de tiempo usando alguna de estas (dado que en bruto, realizar el calculo podría dar tiempos bastante grandes).


[1] David Liben-Nowell and Jon Kleinberg. 2007. The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol. 58, 7 (May 2007), 1019–1031.

Like what you read? Give Maria Fernanda Sepulveda a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.