Berechnung "Kevin Bacon" Zahlen

Question

Ich habe mit einigen Sachen herum gespielt und die Idee des Versuchens ausgearbeitet, Kevin Bacon Zahlen herauszufinden. Ich habe Daten für eine Seite, die zu diesem Zweck wir ein soziales Netz betrachten können. Nehmen wir an, dass es Facebook ist (zur Vereinfachung der Diskussion). Ich habe Leute und ich habe eine Liste ihrer Freunde, also habe ich die Verbindungen zwischen ihnen. Wie kann ich die Entfernung von einer Person zur anderen berechnen (im Grunde eine Kevin Bacon Nummer)?

Meine beste Idee ist eine Bidirectional search, mit einer Tiefenbegrenzung (um die Komplexität der Berechnung zu begrenzen und das Problem von Menschen zu vermeiden, die einfach nicht in der Grafik verbunden werden können), aber ich weiß, dass dies ziemlich brachiale Kraft ist.

Könnte es besser sein, kleine Untergraphen zu erstellen (sagen Sie etwas, das zu Gruppen auf Facebook äquivalent ist), die kürzesten Abstände zwischen ihnen zu berechnen (vielleicht vor der Zeit) und dann THOSE zu benutzen, um einen Link zu finden? Während dies eine Vorberechnung erfordert, könnte es möglich sein, viel weniger Knoten zu durchsuchen (Knoten können Gruppen anstelle von Individuen sein, wodurch der Graph viel kleiner wird). Dies wäre jedoch immer noch eine bidirektionale Suche.

Ich könnte auch die Anzahl der Personen, mit denen eine Person verbunden ist, vorausberechnen, indem ich die Knoten nach "populären" Leuten durchsuche, da sie die beste Chance haben, sich mit der gegebenen Zielperson zu verbinden. Mir ist klar, dass dies eine Abwägung der Geschwindigkeit für den kürzesten Weg wäre. Ich würde denken, dass ich auch eine Suche nach Tiefentiefe anstelle der Suche mit der größten Breite, die ich in den anderen Fällen verwenden möchte, verwenden möchte.

Kann jemand an einen einfacheren/schnelleren Weg denken? Ich würde gerne die kürzeste Länge zwischen zwei Personen finden, also ist es nicht so einfach wie immer den gleichen Endpunkt zu haben (wie beim Kevin Bacon Problem).

Ich erkenne, dass es Probleme gibt, wie ich Ketten von 200 Leuten und so bekommen konnte, aber das kann gelöst werden, meine Begrenzung auf die Tiefe habend, die ich suche bin.

Answer 1

Dies ist ein Standard shortest path problem. Es gibt viele Lösungen, einschließlich Dijkstra's algorithm und Bellman-Ford. Sie könnten besonders interessiert sein, die A* algorithm zu betrachten und zu sehen, wie sie mit der Kostenfunktion relativ zu der Inversen eines bestimmten Knotengrads durchführen würde. Die Idee wäre, populärere Knoten (die mit höherem Grad) zuerst zu besuchen.

Answer 2

Klingt wie ein Job für Dijkstra's algorithm.

ED: Äh, ich hätte den Abzug nicht so schnell drücken sollen. Dijkstra (und Bellman-Ford) reduziert sich auf eine Breitensuche, wenn die Gewichte 1 sind, also ist das nicht allzu nützlich. Naja.

Die A* algorithm, von Tvanfosson erwähnt, kann dafür ideal sein. Die Idee besteht darin, dass Sie anstatt in jeder Reihenfolge der Elemente auf jeder Ebene des Baums zu suchen und zu rekursiv zu werden (basierend auf Ihrem Start- oder Endpunkt), eine Heuristik verwenden, um zu bestimmen, welches Element zuerst getestet wird. In Ihrem Fall wäre eine gute Wette wahrscheinlich der Grad eines Knotens (Anzahl der "Freunde"), aber Sie könnten möglicherweise die Anzahl der Personen innerhalb einer beliebigen Anzahl von Graden einer bestimmten Person verwenden wollen (dh der Typ, der hat drei Freunde, die jeweils 100 Freunde haben, ist wahrscheinlich ein besserer Knoten als der Typ, der 20 Freunde in einer Clique hat, die Außenseiter meidet). Es gibt alle möglichen anderen Dinge, die Sie als Heuristik verwenden können (Freunde erhalten 2 Punkte, Freunde von Freunden erhalten 1 Punkt; was auch immer, Experiment).

Kombinieren Sie dies mit einer Tiefenbegrenzung (abgeschnitten nach 6 Grad Trennung, oder was auch immer), und Sie können Ihren durchschnittlichen Fall erheblich verbessern (Worst Case ist immer noch der gleiche wie Basic BFS).

Answer 3

betreiben eine Breitensuche in beiden Richtungen (von jedem Endpunkt) und stoppen, wenn Sie eine Verbindung haben oder Ihre Tiefengrenze erreichen

Answer 4

Diese insgesamt besser sein könnte Floyd-Warshall die alle kürzester Abstand Paare.