Fragen nach Social Network Analysis (SNA) -Algorithmus

Question

Ich habe die Aufgabe erhalten, eine social graph, wo, mit einem Benutzer in der center, zeigt es die Verbindungen, die er hat.

Aber bevor wir das erreichen können, ist unser Fokus, wie wir die shortest path zwischen 2 Benutzern ermitteln können.

Ich habe einen Algorithmus dafür gefunden, aber es scheint, dass es viel Zeit braucht, und weil es um soziale Verbindungen geht, suchen wir nach einem, der am schnellsten ist, weil wir ihn regelmäßig ausführen müssen um mit den Updates in Freunden Schritt zu halten.

Also, wissen Sie, welcher wäre der schnellste Weg, um den kürzesten Weg zwischen zwei Benutzern zu bestimmen?

PS: Wenn Sie ein Beispiel in PHP & MySQL kennen, gebe ich Ihnen ein virtuelles Bier (oder Cola). : D

Answer 1

findet den kürzesten Pfad zwischen zwei Knoten in einem Diagramm.

Answer 2

Es scheint mir, dass wenn Sie den gesamten Graphen trotzdem zeichnen, der einfachste Weg wäre, den Pfad jeder Person zu verfolgen, wie sie dem Graph hinzugefügt werden. Für die Freunde der Person ist der Pfad nur "Hauptperson -> Freund". Dann, wenn Sie jeden IHRER Freunde dem Graph hinzufügen, speichern Sie den Pfad "Hauptperson -> Freund 1 -> Freund 2" etc.

Wenn das Bild in meinem Kopf genau ist, scheint das der einfachste Weg zu sein Mach es, aber ich könnte etwas falsch verstehen.

Answer 3

was Sie wollen, ist ein all-pairs shortest path Algorithmus; Wenn Sie die Paare global für den Graphen generieren müssen, ist es schneller, als einen Algorithmus für den kürzesten Pfad für jedes Paar auszuführen. Dies zu aktualisieren ist ein weiteres Problem - beachten Sie, dass Sie dies jedes Mal tun müssen, wenn Sie eine Verbindung zum Diagramm hinzufügen, nicht nur jedes Mal, wenn Sie eine Person hinzufügen. Wenn dies für eine Produktionsstätte gilt, könnte es sich lohnen, die Graphengenerierung als eine Offline-Aufgabe zu pflegen, die in einer Sprache geschrieben ist, die schneller als PHP ist, und ihre Ergebnisse zurück in die Datenbank zu schreiben. Sie werden wahrscheinlich vorhandene C++ - Implementierungen finden.

Answer 4

Dijsktra-Algorithmus funktioniert gut auf gewichteten Graphen. In einer sozialen Grafik haben alle Kanten das gleiche Gewicht. Also wird Dijkstras Algorithmus zu BFS. In einem dichten Graphen wird die Liste der Knoten, die auf jeder Ebene untersucht werden, jedoch sehr groß sein. Eine Optimierung, die Sie tun können, ist, die Suche von beiden Enden (A und B) zu starten.