Solicitud de análisis de redes sociales algoritmo (SNA)

Question

He recibido la tarea de hacer una gráfico social, donde, con un usuario en la , que muestra las conexiones que tiene.

Pero antes de que podamos llegar a eso, nuestro enfoque es cómo podemos determinar la camino más corto entre 2 usuarios.

He encontrado algún algoritmo para hacerlo, pero parece que se necesita una gran cantidad de tiempo, y porque se trata de vínculos sociales, estamos buscando uno que es el más rápido, porque tendremos que ejecutarlo en una base regular para mantenerse al día con las actualizaciones de los amigos.

Así que, ¿sabe usted lo que sería la forma más rápida para determinar la ruta más corta entre dos usuarios?

PS: Si conoce un ejemplo en PHP y MySQL, que le dará una cerveza virtual (o coque). : D

Answer 1

el algoritmo de Dijkstra encuentra el camino más corto entre dos nodos en un gráfico.

Answer 2

Lo que queremos es un todos los pares de camino más corto algoritmo; si tiene que generar los pares a nivel mundial para la gráfica es más rápido que la ejecución de un algoritmo de ruta más corta para cada par. mantener esta actualizado es otro problema - en cuenta que vas a tener que hacerlo cada vez que se agrega una conexión con el gráfico, no sólo cada vez que añada una persona. si esto es para una planta de producción, podría valer la pena mantener la generación de gráficos como una línea de trabajo escrito en un lenguaje más rápido que php, y escribiendo sus resultados a la db. probablemente encontrará implementaciones de C ++ existente por ahí.

Answer 3

Me parece que si vas a sacar todo el gráfico de todas formas, lo más fácil sería hacer un seguimiento de la trayectoria de cada persona, a medida que se añaden a la gráfica. Así que para los amigos de la persona, la ruta es simplemente "persona principal -> amigo". Luego, a medida que agrega cada uno de sus amigos a la gráfica, almacenar la ruta "persona principal -> amigo 1 -> 2 amigo". Etc.

Si la imagen en mi mente es exacta, que parece ser la forma más fácil de hacerlo, pero puede ser que sea un poco malentendido.

Answer 4

El algoritmo de Dijsktra funciona bien en grafos ponderados. En un gráfico social de todos los bordes tienen el mismo peso. Por lo tanto el algoritmo de Dijkstra se convierte BFS. Sin embargo en un gráfico densa la lista de nodos examinados en cada nivel será enorme. Una optimización que puede hacer es, para iniciar la búsqueda de los dos extremos (A y B).