Python Verwendung von Breitensuche auf Social Graph

Question

Ich habe viele Stackoverflow-Fragen über die Verwendung der Breitensuche, dfs, A * usw. gelesen, die Frage ist, was ist die optimale Nutzung und wie um es in Wirklichkeit zu implementieren, simulierte Graphen. Z.B.

Betrachten Sie eine Social Graph von Twitter/Facebook/Some Social-Networking-Website, für mich ist es ein Suchalgorithmus funktionieren würde, wie folgt scheint:

Wenn Benutzer A 10 Freunde hatte, dann einer von denen hatte zwei Freunde und andere 3. Die Suche würde zuerst herausfinden, wer die Freunde von Benutzer A waren, dann müsste es herausfinden, wer die Freunde wo zu jedem der zehn Benutzer waren. Für mich scheint das wie bfs?

Ich bin mir jedoch nicht sicher, ob das der Weg ist, den Algorithmus zu implementieren.

Danke,

Answer 1

Für meine zwei Cent, sind, wenn Sie nur die ganze Graph versuchen zu durchqueren es nicht eine ganze Menge ist egal, was Algorithmus Sie so lange verwenden, wie es nur einmal pro Knoten trifft. Dies scheint zu sein, was Sie sagen, wenn Sie Folgendes beachten:

Ich bin nur

die ganze Grafik zu überqueren versuchen

Dies bedeutet, dass Ihre Terminologie technisch ist flawed- Sie sprechen Walking ein Diagramm, nicht Suche ein Diagramm. Es sei denn, du versuchst tatsächlich, nach etwas speziellem zu suchen, was du in der Frage überhaupt nicht zu erwähnen scheinst.

Mit dieser sagte, Facebook und Twitter sind sehr unterschiedlich Graphenstrukturen, die einen Einfluss haben, wie Sie sie gehen:

1. Facebook ist im Grunde ein ungerichteter Graph. Wenn X mit Y befreundet ist, MÜSSEN Y mit X befreundet sein. (Oder in einer Beziehung mit oder verwandt mit usw.).

2. Twitter ist grundsätzlich ein gerichteter Graph. Wenn Sie X auf Y folgen, muss Y nicht X folgen.

Diese Probleme haben erhebliche Auswirkungen auf den Graph-Algorithmus. Um ganz ehrlich zu sein, wenn Sie nur alle Knoten besuchen wollen, brauchen Sie sogar eine Grafik? Warum nicht einfach alle durchlaufen? Wenn Sie alle Knoten in einem gewissen Datenstruktur my_data haben, die iterable ist, könnten Sie nur einen Generator Ausdruck wie diese:

def nodeGenerator(MY_DATA) 
    for node in MY_DATA: 
     yield node 

Natürlich müssen Sie die nodeGenerator Interna anpassen zu handhaben, wie Sie sind eigentlich Zugriff auf die Knoten. Nachdem dies gesagt wurde, implementieren die meisten Graphstrukturen einen Knoteniterator. Dann können Sie einfach einen Iterator, wann immer Sie Dinge tun wollen erstellen über:

for node in nodeGenerator(MY_DATA): 
    (Do something here) 

Vielleicht bin ich nur den Punkt der Frage fehlt hier, aber derzeit haben Sie eine Frage zu Suchalgorithmen ohne Durchsuchungs gestellt Problem. Aufgrund der Natur der Optimierung und Suche No Free Lunch hängt der Wert jedes Suchalgorithmus vollständig von dem Suchproblem ab, das Sie untersuchen möchten.

Dies gilt sogar für den gleichen Datensatz.Wenn Sie schließlich nach jedem suchen, dessen Name mit dem Buchstaben D beginnt, wäre es ein guter Ansatz, alle alphabetisch zu sortieren und eine binäre Suche durchzuführen. Wenn Sie stattdessen versuchen, den Grad der Trennung von Kevin Bacon zu finden, werden Sie einen Algorithmus haben, der mit Mr. Bacon beginnt und rekursiv über jeden, der ihn und alle anderen kennt, iteriert. Dies sind Dinge, die Sie auf Facebook oder Twitter tun könnten, aber ohne irgendwelche Besonderheiten gibt es wirklich keine Möglichkeit, einen Algorithmus zu empfehlen. Daher, wenn Sie nichts wissen, nur über alle als eine Liste iterieren. Es ist genauso gut wie alles andere. Wenn Sie dann optimieren möchten, cachen Sie alle Berechnungen zwischen.

Answer 2

Ich habe rund 300 Freunde in Facebook und einige meiner Freunde haben auch durchschnittlich 300 Freunde. Wenn du daraus einen Graphen erstellst, wird es riesig. Korrigiere mich, wenn ich falsch liege? . Ein BFS wird in diesem Szenario sehr fordernd sein?

Dank J