Python-Anwendung der Breitensuche im sozialen Graphen

Question

Ich habe viele stackoverflow-Fragen darüber gelesen, wie man die Breitensuche, Tiefensuche, A*, etc. verwendet, die Frage ist, was ist die optimale Verwendung und wie man sie in der Realität im Vergleich zu simulierten Graphen implementiert. Zum Beispiel.

Stellen Sie sich vor, Sie haben einen sozialen Graphen von Twitter/Facebook/Einer sozialen Netzwerkseite, mir scheint ein Suchalgorithmus würde wie folgt funktionieren:

Wenn Benutzer A 10 Freunde hatte, von denen einer 2 Freunde und ein anderer 3 hatte. Die Suche würde zuerst herausfinden, wer die Freunde von Benutzer A waren, dann müsste sie herausfinden, wer die Freunde von jedem der zehn Benutzer waren. Mir scheint das wie bfs?

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

Danke,

Answer 1

Für meinen Senf, wenn Sie nur versuchen, den gesamten Graphen zu durchqueren, spielt es keine große Rolle, welchen Algorithmus Sie verwenden, solange jeder Knoten nur einmal erreicht wird. Es scheint das zu sein, was Sie sagen, wenn Sie bemerken:

Ich versuche nur, den gesamten Graphen zu durchqueren

Dies bedeutet, dass Ihre Terminologie technisch gesehen fehlerhaft ist, Sie sprechen über das Durchlaufen eines Graphen, nicht das Suchen eines Graphen. Es sei denn, Sie versuchen tatsächlich, nach etwas Bestimmtem zu suchen, was Sie in der Frage überhaupt nicht erwähnen.

Das gesagt, Facebook und Twitter sind sehr unterschiedliche Graphstrukturen, die sich darauf auswirken, wie Sie sie durchlaufen:

1. Facebook ist grundsätzlich ein ungerichteter Graph. Wenn X mit Y befreundet ist, muss auch Y mit X befreundet sein. (Oder in einer Beziehung stehen oder verwandt sein, usw.).

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

Diese Fragen werden sich erheblich auf den Graph-Durchlaufalgorithmus auswirken. Ganz ehrlich, wenn Sie nur alle Knoten besuchen möchten, brauchen Sie überhaupt einen Graphen? Warum iterieren Sie nicht einfach über alle? Wenn Sie alle Knoten in einer Datenstruktur MY_DATA haben, die iterierbar ist, könnten Sie einfach einen Generatorausdruck wie diesen haben:

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

Sicherlich müssten Sie die internen Bestandteile des nodeGenerators anpassen, um zu behandeln, wie Sie tatsächlich auf die Knoten zugreifen. Mit das gesagt, implementieren die meisten Graphstrukturen einen Knoten-Iterator. Dann können Sie einfach immer dann einen Iterator erstellen, wenn Sie Dinge tun wollen via:

 for node in nodeGenerator(MY_DATA):
     (Hier etwas tun)

Vielleicht verstehe ich den Punkt der Frage hier nicht, aber im Moment haben Sie eine Frage über Suchalgorithmen ohne ein Suchproblem gestellt. Aufgrund der No Free Lunch-Natur der Optimierung und Suche wird der Wert eines Suchalgorithmus vollständig von dem Suchproblem abhängen, das Sie untersuchen wollen.

Dies gilt sogar für dasselbe Datenset. Schließlich, wenn Sie nach jedem suchen, dessen Name mit dem Buchstaben D beginnt, wäre ein großartiger Ansatz, einfach alle alphabetisch zu sortieren und eine binäre Suche durchzuführen. Wenn Sie stattdessen den Grad der Trennung von Kevin Bacon für alle finden möchten, benötigen Sie einen Algorithmus, der mit Herrn Bacon beginnt und rekursiv über alle iteriert, die ihn kennen und jeder, den sie kennen. Dies sind beides Dinge, die Sie auf Facebook oder Twitter tun könnten, aber ohne spezifische Angaben gibt es wirklich keine Möglichkeit, einen Algorithmus zu empfehlen. Wenn Sie also nichts wissen, iterieren Sie einfach über alle als Liste. Es ist genauso gut wie alles andere. Wenn Sie dann optimieren möchten, zwischenspeichern Sie Berechnungen.

Answer 2

Ich habe ungefähr 300 Freunde bei Facebook und einige meiner Freunde haben im Durchschnitt auch 300 Freunde. Wenn du daraus einen Graphen erstellen möchtest, wird er riesig sein. Korrigiere mich, wenn ich falsch liege? Wird ein BFS in diesem Szenario ziemlich anspruchsvoll sein?

Danke J