Ich habe eine Datenbank mit 20 Millionen Nutzern und Verbindungen zwischen diesen Leuten. Wie kann ich das Konzept des "Six grade of separation" -Konzepts am effizientesten in der Programmierung unter Beweis stellen?
Sie möchten nur den Durchmesser des Diagramms messen. Dies ist genau die Metrik, um die Trennung zwischen den am weitesten entfernten Knoten in einem Graphen herauszufinden.
Viele Algorithmen bei Google, Boost-Grafik .
Sie können das Diagramm wahrscheinlich in den Speicher einfügen (in der Darstellung, dass jeder Knoten eine Liste seiner Nachbarn kennt).
Dann können Sie von jedem Scheitelpunkt n eine Breite-zuerst-Suche (unter Verwendung einer Warteschlange) bis zur Tiefe von 6 durchführen und die Anzahl der besuchten Scheitelpunkte zählen. Wenn nicht alle Ecken besucht werden, haben Sie den Satz widerlegt. Andernfalls fahren Sie mit dem nächsten Vertex n fort.
Das ist O (N * (N + #edges)) = N * (N + N * 100) = 100N ^ 2, wenn der Benutzer durchschnittlich 100 Verbindungen hat, was für N = 20 Millionen nicht ideal ist. Ich frage mich, ob die erwähnten Bibliotheken den Durchmesser in besserer zeitlicher Komplexität berechnen können (allgemeiner Algorithmus ist O (N ^ 3)).
Die Berechnungen für einzelne Scheitelpunkte sind unabhängig und können parallel ausgeführt werden.
Eine kleine Heuristik: Beginnen Sie mit Ecken, die den niedrigsten Grad haben (bessere Chance, den Satz zu widerlegen).
Ich denke, der effizienteste Weg (schlimmster Fall) ist fast N ^ 3. Erstellen Sie eine Adjazenzmatrix und nehmen Sie dann die Matrix ^ 2, ^ 3, ^ 4, ^ 5 und ^ 6. Suchen Sie nach allen Einträgen im Diagramm, die 0 für Matrix durch Matrix ^ 6 sind.
Heuristisch können Sie versuchen, Untergraphen (große Klumpen von Menschen, die nur durch eine relativ kleine Anzahl von "Brücken" -Knoten mit anderen Klumpen verbunden sind) auszusondern, aber es gibt absolut keine Garantie, die Sie haben werden.
Es ist schon eine bessere Antwort gegeben worden, aber von meinem Kopf wäre ich mit dem Floyd-Warshall gegangen der Algorithmus für den kürzesten Pfad aller Paare, der O (n ^ 3) ist. Ich bin mir nicht sicher, wie komplex der Graph-Durchmesser-Algorithmus ist, aber "klingt", als wäre das auch O (n ^ 3). Ich würde gerne eine Klarstellung darüber machen, wenn jemand es weiß.
Übrigens, haben Sie wirklich eine solche Datenbank? Unheimlich.
Tags und Links algorithm graph-theory combinatorics networking