Verbindungen von Freunden in einer Freundesliste

[Forumsgast]

Hallo,

ich möchte bei meiner Community ein Funktion einbauen die Verbindungen zwischen usern zeigt.

Beispiel:

ich habe a in der freundesliste, a hat b in der freundesliste und b wiederrum c

Fall ich nun das Profil von c besuch soll wie bei studivz angezeigt werden:

Ich -> a -> b -> c

Ich hab durch ein paar recherchen jetzt rausgefunden das es wie bei einer routenplanung mit dem Dijkstra-Algorithmus realisiert werden könnte. Das bedeutet allerdings einen immensen Rechenaufwand.

Kennt jemand einen besseren weg diese Funktion zu realisieren ? Das würde mir echt weiterhelfen.

[Forumsgast]

Ich weiß nicht, ob der Algorithmus geeignet ist. Was passiert denn, wenn a und c über b1, b2 als auch b3 miteinander bekannt sind? Du hast hier keine gewichteten Kanten, d.h. im Endeffekt sind die Wege über b1, b2 und b3 gleichberechtigt. Anders als auf ner Landkarte, wo dann die Entfernungen entscheiden. Denk mal über den Fall nach und wie du dann verfahren willst.

[Forumsgast]

Ansich wird dann per Zufall eine Verbindungsperson angezeigt. Ein Kollege von mir hat mal etwas von einer Methode geredet wie soetwas gelöst werden kann. Ich weiß nicht ob es sich um den Dijkstra-Algo handelt oder um eine Alternative ... ich frag nochmal nach.

Auf jeden Fall hat er gemeint das sich statistisch gesehen alle Menschen sich über sechs Ecken kennen. Ist doch relativ wenig.

Wenn du allerdings nicht garantieren kannst dass sich alle deine User irgendwie untereinander kennen. Dann musst du eine maximale Ebene definieren bei der dann aufgehört wird zu suchen. Ansonsten kommst du sehr schnell zu einer Endlosschleife. Bzw. einer Schleife die alle User durchsucht ... das wäre bestimmt nicht gut für die Performance. Ich werd mich selber nochmal erkundigen da ich dieses Thema doch sehr interessant finde.

[Forumsgast]

Über XING (falls es jemand kennt) kenne ich meine Schwester, mit der ich keine gemeinsamen Freunde habe und die in Hamburg wohnt, über 5 Ecken auf 10 verschiedene Ketten. Da kann echt was dran sein RaZor.

Und schaut doch mal ins studivz, da kennt man doch echt jeden.

Such einfach deine Freunde und Freundesfreunde, tu das gleiche mit der Zielperson und die Übereinstimmungen sind dein Ergebnis.

Wahrscheinlich geht es auch performanter, aber da bietet dir Google bestimmt genug eigene Treffer. Andererseits glaube ich zu wissen, dass es ein Wegfindungsproblem gibt (ob ich Städte oder Freunde finde ist ja egal). Wie hieß es doch gleich, Problem des Reisenden? Vielleicht verwechsle ich es aber auch gerade..

[Forumsgast]

http://de.wikipedia.org/wiki/Problem...lungsreisenden

das meinte ich, aber hier ist die Menge der Städte ja fix. Doch nicht das gesuchte.

[Forumsgast]

Ja die Theorie mit den 6 Menschen kenne ich auch. Es gab mal ne Website, auf der das exemplarisch für Schauspieler gezeigt wurde (hier war ein Knoten, dass Sie zusammen in einem Film gespielt haben). Spannend.

Ich mußte auch gleich ans Travelling Salesman Problem denken, aber eigentlich ist ja die kürzeste Verbindung zwischen den Nutzern relevant. Aber wie gesagt, die meisten Algoritmen (A* etc.) behandeln gewichtete Graphen, also Kanten mit verschiedenen Längen.

Edit (und etwas OT):
Habs gefunden, Stichworte sind 'six degrees of separation' oder 'Small world phenomenon' bzw. 'Milgram's experiment'

[Forumsgast]

Das Problem des Handlungsreisenden betrifft ja nur Kreis. In Falle der Verknüpfung gibt es aber keine Kreise (bzw implizit schon, weil der Rückweg ja auch denkbar wäre ), weil du ja nur von Person A (ich) zu Person Z (den "Suchtreffer") über Personen B, C, D, ... (den Freunden der Freunde der Freunde der ...) gehst.

Ist eigentlich garnicht so schwierig. Stichwort ist hier Breitensuche. Dijkstra halte ich für etwas oversized, da es sich ja nicht um gewichtete Kanten handelt.

Nachteil der Breitensuche mag möglicherweise sein, dass der gefundene Weg bei mehreren gleichlangen möglichen Wegen vom Zufall abhängt. Bei intelligenter Datenstruktur lässt sich aber einrichten, dass er einfach den Weg findet, der als erstes vollständig existierte. Ebenfalls Nachteile, wobei die sich möglicherweise auch mit Dijkstra nicht lösen lassen:
1. Gibt es keinen Weg, durchsucht er trotzdem den vollen Graphen.
2. Gibt es mehrere unabhängige Graphen, sollte man versuchen nur Knoten (Personen) mit einzubeziehen, die überhaupt irgendwie in den Kreis der potentiellen Täter sein kann.

[Forumsgast]

Hier habe ich schonmal so eine Diskussion losgetreten. Hier sind auch noch ein paar Links und Resourcen. Vielleicht hilft es ja, um endlich mal eine Lösung und wirkliche Erfahrungsberichte aufzustellen!

http://www.developers-guide.net/foru...la-xing-openbc

[Forumsgast]

Naja, meine Meinung hab ich ja scho los getreten Mir wurde im 1. Semester noch beigebracht, dass die einfachste (aber vllt nicht effizienteste) Methode, um einen kürzesten Weg durch einen ungewichteten, ungerichteten Graphen die Breitensuche ist. Wenn man die Breitensuche ohne Abbruchkriterium durchführt, hat man hinterher einen Baum mit dem Startknoten als Wurzel und die Abstände zwischen der Wurzel und den Knoten ist immer minimal. Soweit muss man aber bei "kürzester Weg zwischen A und B" garnicht gehen, weil man eben "B gefunden" als Abbruchkriterium einführen kann und somit is Ende.

Effizient ist das alles nicht, da es immer noch den (nicht unwahrscheinlichen) Fall gibt, dass garkein Weg zwischen zwei Knoten gibt, aber da nehmen sich die Algorithmen nichts. Die Frage ist bloss, ob es wirklich sooo inperformant abläuft, wenn sich im Graphen 10.000+ Knoten befinden, weil im Endeffekt er keine großen Berechnungen durchführt (immer nur "Ist Knoten X == Freund B? Ja: Abbruch und Pfad zurück geben, Nein: Nächster Knoten Z und Knoten X aus Queue entfernen").

Ehrlich gesagt finde ich das Problem jetzt nicht so richtig diskussionwürdig, da haben sich schließlich schon viele große Köpfe Gedanken drüber gemacht