Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Suche Algorithmus für Freundenetzwerk
Savage
myCSharp.de - Member



Dabei seit:
Beiträge: 94

Themenstarter:

Suche Algorithmus für Freundenetzwerk

beantworten | zitieren | melden

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?
private Nachricht | Beiträge des Benutzers
DavidT
myCSharp.de - Member

Avatar #avatar-3073.png


Dabei seit:
Beiträge: 1008
Herkunft: Winterberg

beantworten | zitieren | melden

Ist das nicht ein normaler join über x-Ebenen?

Gruß David
private Nachricht | Beiträge des Benutzers
Savage
myCSharp.de - Member



Dabei seit:
Beiträge: 94

Themenstarter:

beantworten | zitieren | melden

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?
private Nachricht | Beiträge des Benutzers
Kartoffel
myCSharp.de - Member



Dabei seit:
Beiträge: 27

beantworten | zitieren | melden

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.).
private Nachricht | Beiträge des Benutzers
cadi
myCSharp.de - Member

Avatar #avatar-1786.jpg


Dabei seit:
Beiträge: 308
Herkunft: Hamburg

beantworten | zitieren | melden

Zitat von Savage
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)
private Nachricht | Beiträge des Benutzers
Savage
myCSharp.de - Member



Dabei seit:
Beiträge: 94

Themenstarter:

beantworten | zitieren | melden

Danke für die Info, werde es mir anschauen.
private Nachricht | Beiträge des Benutzers