Calcule la distancia social entre dos usuarios

Question

Cómo codificaría un algoritmo eficiente que puede devolver una "distancia" social entre dos usuarios.

Por ejemplo, cuando visita un perfil en LinkedIn, puede ver cuál es la distancia entre usted y el usuario.

-> usuario A es amigo con el usuario B - B y C es amigo de cuando A visitará C (la distancia será de 1)

La gráfica es enorme y así me pregunto cómo se puede realizar tan rápido.

Sé que es probable que esta pregunta se cierre, pero realmente creo que es una pregunta de programación/algoritmo. No especificaría ningún idioma porque estoy interesado en el concepto.

Answer 1

que suponiendo que no tienen ningún heuristic function acerca de la distancia al objetivo, la mejor solución que sea válida es bi-directionalBFS:
Algoritmo idea: hacer una búsqueda BFS simultáneamente desde el origen y el destino: [BFS hasta la profundidad 1 en ambos, hasta la profundidad 2 en ambos, ....].
El algoritmo finalizará cuando encuentre un vértice v, que está en el frente de ambos BFS.

Comportamiento del algoritmo: El vértice v que finaliza la ejecución del algoritmo estará exactamente en el medio entre la fuente y el objetivo.
Este algoritmo arrojará resultados mucho mejores en la mayoría de los casos, luego BFS de la fuente [explicación de por qué es mejor que BFS], y seguramente proporcionará una respuesta, si existe.

¿por qué es mejor que BFS desde la fuente?
suponga que la distancia entre el origen y el destino es k, y el factor de bifurcación es B [cada vértice tiene bordes B].
BFS se abrirá: 1 + B + B^2 + ... + B^k vértices.
BFS bidireccional se abrirá: 2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2) vértices.

para grandes B y K, el segundo es obviamente mucho mejor que el primero.

EDIT:
NOTA, que esta solución no requiere almacenar todo el gráfico en la memoria, que sólo requiere la aplicación de una función: successor(v) que devuelve todos los sucesores de un vértice [todos los vértices se puede llegar a, dentro de 1 paso de v]. Con esto, solo se deben almacenar los nodos que abra [2 + 2B + ... + 2B^(k/2) como se explicó anteriormente]. Para ahorrar aún más memoria, puede usar Iterative Deepening DFS desde una dirección, en lugar de BFS, pero consumirá más tiempo.

Answer 2

Hubiera supuesto que esto se haría aplicando un algoritmo de ruta más corta, como breadth first search a graph database. Pero parecen almacenar todo su gráfico en la memoria, al menos de acuerdo con this.

Estoy seguro de que el algoritmo finalmente se reduce a alguna forma de ruta más corta uno sobre una estructura de gráfico (nodos y bordes).

Editar: Se modificó el algoritmo según los comentarios.

Answer 3

Primero, debe completarse el gráfico. No puedo decir cómo se vincula el gráfico, probablemente haciendo un BFS o DFS de los nodos, descubriendo los gráficos y estableciendo enlaces. Para encontrar la distancia entre dos mejores es hacer una BFS desde el nodo de origen y detener cuando se encuentra el destino. Los enlaces no tienen pesos, creo, si no implican algo diferente.

En este caso, debe aplicar un BFS cada uno para encontrar la distancia entre cada par, cuando el nodo fuente es diferente. De lo contrario, puede implementar el algoritmo de Floyd Warshall para obtener todas las rutas de destino más cortas de destino, y dado que cada enlace tiene el mismo peso, obtendrá lo que desee. En este caso, una vez hecha la estructura, para cualquier fuente y destino se puede encontrar la distancia más corta. Un problema es que la red siempre está cambiando, por lo tanto, se necesita un nuevo procesamiento. Por lo tanto, BFS creo que será bueno.

Para que el procesamiento sea más rápido, puede implementar BFS para que se ejecute en paralelo. Eche un vistazo a Design and analysis of a nondeterministic parallel breadth-first search algorithm