Relaciones de amistad algoritmo de seguimiento

Question

Estoy pensando en una aplicación que intente probar el " Seis grados de separación " Teoría con un conjunto de usuarios que forman parte de una red social.

Tendría esos elementos:

1. Un par de usuarios para los que me gustaría probar la teoría de los seis grados
2. Para cada usuario, conozco la lista de amigos en la red social

¿Cuál es el mejor algoritmo para ver si los dos usuarios están conectados, con qué grado y mostrar los pasos finales en la conexión?

Answer 1

Encontrar el grado de separación entre dos personas en una red social es solo un caso especial de encontrar el camino más corto entre dos puntos en una gráfica. El enfoque más común es algoritmo de Dijkstra , pero vea también una discusión más larga de Problema de ruta más corta .

Además, al ejecutar un algoritmo de ruta más corta de todos los pares, puede averiguar el número mínimo, máximo y promedio de grados de separación para toda la red.

Answer 2

Algunos materiales de fondo adicionales:

Para resolver este problema en general, usted querría evitar el raspado web y otras técnicas ad hoc que son específicas de una red social. En su lugar, probablemente querrá ver XHTML Friends Network (XFN) , que es una forma de usar la red = " " atributo de un hipervínculo para indicar la relación entre el objetivo de ese hipervínculo y usted. También hay un estándar en competencia llamado FOAF que usa RDF .

Estos microformats han existido por un tiempo, pero el apoyo para ellos ha crecido mucho recientemente. StackOverflow utiliza " yo " en el enlace de tu página de perfil. Los blogs de WordPress proporcionan una manera fácil en la interfaz de edición para que el blogroll agregue estas etiquetas. Muchos sitios sociales los utilizan en enlaces entre amigos para indicar relaciones.

Debido a esto, Google se ha interesado en esto, y está empezando a minar estos datos. Tienen un API de gráficos sociales que puede extraer datos de XFN y FOAF para hacer exactamente algunos de las cosas que quieres hacer Te sugiero que empieces allí. Lo bueno de la API de Google es que, como están minando en toda la web, puede ampliar su búsqueda más allá de la red social específica que tenía en mente.