Suche Algorithmus für Freundenetzwerk
Hallo Leute,
ihr kennt sicher Community-Portale (Xing, StudiVZ, etc.), bei denen man sehen kann, über welche „Ecken“ man eine bestimmte Person kennt.
Ich muss so was entwickeln und weiß nicht, wie ich es angehen soll. Mein Ansatz war eine rekursive Abfrage, also einfach die eigenen Freunde durchsuchen, prüfen ob diese die Zielperson kennen, wenn nicht, dessen Freunde wieder durchsuchen usw.
Aber diese Methode ist natürlich sehr langsam, wenn die Rekursion in die Tiefe geht.
Wie kann ich das am besten lösen?
Ist das nicht ein normaler join über x-Ebenen?
Gruß David
Ja, aber bekommt man da nicht ein Performance-Problem?
Angenommen ich habe 10 Freunde und jeder dieser Freunde hat auch 10 Freunde etc…. Dann würde der Join bei 5 Ebenen 10^5 (also 100.000) Datensätze durchsuchen müssen. Oder habe ich da jetzt einen Denkfehler?
Wenn die Freunde alle unterschiedlich sind hast du Recht.
Das Problem ist recht aufwändig (vor allen Dingen, wenn die Anzahl der Datenbankaufrufe das kritishe Moment ist). Es kann graphentheoretisch modelliert werden. Pathfindig-Algorithmen auf Graphen (wie z.B. Dijkstra oder A*) sind hier aber nicht schneller als deine rekursive Tiefensuche, denn A* benötigt z.B. eine gute Heuristik um die nächste Kante zu wählen, die mir in einem Community-Network ohne Weiteres nicht einfällt.
Du wirst also nicht drum rum kommen, die Rekursionstiefe deines Algos zu beschränken oder mit viel Aufwand und Vorberechnungen die Komplexität des Netzwerkes verringen (z.B. Beschränkung auf Supernodes, Freunde zu Clustern zusammenzufügen, etc.).
ihr kennt sicher Community-Portale (Xing, StudiVZ, etc.), bei denen man sehen kann, über welche „Ecken“ man eine bestimmte Person kennt.
Wie kann ich das am besten lösen?
Hallo, das ganze hört sich sehr nach Graphentheorie an.
Jeder User ist ein Node und jede Verbindung eine Kante. Wenn Du deine Verknüpfungen so gepflegt hast ist der rest kein problem mehr...
Schau dir mal QuickGraph an. Da sind die endsprechenden Algorithmen bereits drinne.
http://www.codeplex.com/quickgraph
(Btw. Xing macht das genau so, wenn auch nicht in c# und .NET)
Danke für die Info, werde es mir anschauen.