Algoritmo Random Walk

El algoritmo random walk es uno de los algoritmos que compone la familia de los encargados de determinar rutas más cortas. Forma parte la familia de algoritmos orientados a grafos y se encarga de proporcionarnos rutas de características aleatorias dentro de la estructura de un grafo. A continuación conoceremos más a profundidad su concepto, principales casos de uso, restricciones y realizaremos un ejemplo practico para entender mejor su funcionamiento.

¿Que es el algoritmo Random Walk?

El termino Random Walk traducido al castellano significa camina aleatoria. Esto significa que se realiza un recorrido desde un nodo que compone un grafo y se desarrollan recorridos escogiendo nodos vecinos al azar o en función de una distribución de probabilidad proporcionada. Posteriormente se realizar el mismo proceso desde el nodo que en un principio fue un destino, manteniendo la ruta en una lista.

El concepto de «caminata aleatoria» fue mencionado por primera vez por el matemático ingles  Karl Pearson en 1905. Según los registros académicos sobre esta discusión el debate sobre el concepto se remonta a tiempos anteriores al problema de la ruina del jugador, sin embargo, solo en tiempos recientes los investigadores han desarrollado estudios de la aplicación de las caminaras aleatorias al estudio de grafos.  Conozcamos a continuación sus principales casos de uso.

Casos de uso del algoritmo

Este algoritmo posee un ámbito de aplicación extenso y ha sido implementado en estudios del área de las ciencias naturales, especialmente en la biología, ya que permite comprender la dispersión de las especies animales. También tiene un gran alcance en el mundo de las finanzas, siendo implementado para el análisis  de las cotizaciones de acciones en la bolsa de valores.

El Random Walk también puede ser complemento de otros algoritmos. Este puede ser utilizado como parte del algoritmo node2vec y graph2vec, que pueden crear incrustaciones de nodos. Adicionalmente puede complementar algoritmos de detecciones de comunidades en el caso de que una camina aleatoria devuelva un pequeño conjunto de nodos dentro de un grafo.

random

El Algoritmo Page Rank en muchas ocasiones desarrolla caminatas aleatorias para obtener sus resultados. Pero su alcance no se ve limitado únicamente al análisis de grafos. Este también puede formar parte del proceso de enseñanza dentro de un proceso de Machine Learning.

Restricciones

Las restricciones del algoritmo random walk son similares a las restricciones que tiene el algoritmo Page Rank. En ambos casos pueden producirse callejones sin salida. Esto sucede cuando no existen enlaces o conexiones externas del rango de datos analizados hacia otro nodo. En este caso la caminata aleatoria se abortará y entregará una ruta que contenga solamente el primer nodo. Es importante en estos casos establecer párametros de recorrido amplios para que la caminata se produzca en todas direcciones.

Ejemplo de aplicación

Para comprender su aplicación a profundidad desarrollaremos un grafo simple representando la arquitectura de un sitio web con algunas secciones como el que mostramos a continuación:

MERGE (home:Page {name:'Home'})
MERGE (about:Page {name:'About'})
MERGE (product:Page {name:'Product'})
MERGE (links:Page {name:'Links'})
MERGE (a:Page {name:'Site A'})
MERGE (b:Page {name:'Site B'})
MERGE (c:Page {name:'Site C'})
MERGE (d:Page {name:'Site D'})

MERGE (home)-[:LINKS]->(about)
MERGE (about)-[:LINKS]->(home)
MERGE (product)-[:LINKS]->(home)
MERGE (home)-[:LINKS]->(product)
MERGE (links)-[:LINKS]->(home)
MERGE (home)-[:LINKS]->(links)
MERGE (links)-[:LINKS]->(a)
MERGE (a)-[:LINKS]->(home)
MERGE (links)-[:LINKS]->(b)
MERGE (b)-[:LINKS]->(home)
MERGE (links)-[:LINKS]->(c)
MERGE (c)-[:LINKS]->(home)
MERGE (links)-[:LINKS]->(d)
MERGE (d)-[:LINKS]->(home)

Una vez desarrollado el grafo, ejecutaremos el algoritmo para que nos entregue producto del análisis un recorrido aleatorio:
MATCH (home:Page {name: "Home"})CALL algo.randomWalk.stream(id(home), 3, 1)
YIELD nodeIds UNWIND nodeIds AS nodeId RETURN algo.asNode(nodeId).name AS page

Una vez ejecutado el algoritmo, este nos devolverá como resultados una tabla con los el recorrido aleatorio realizado por los datos indicados en el grafo y se presentan de una forma similar a la que se presenta a continuación:

Page
"Home"
"Site C"
"Links"
"Site A"

Esperamos que esta información sea de utilidad para comprender el alcance y la aplicación de este algoritmo

Visita más de Grapheverywhere para conocer más sobre algoritmos de análisis de grafos.

Share This