Freundschaft Beziehungen Tracking-Algorithmus

Question

Ich denke an eine Anwendung, die die „ Six Degrees of Separation “Theorie mit einer Gruppe von Benutzern, die Teil eines sozialen Netzwerks sind.

Ich würde diese Elemente haben:

1. Ein paar Benutzer, für die Ich mag würde die sechs Grad Theorie
beweisen
2. Für jeden Benutzer, ich kenne die Liste von Freunden im sozialen Netzwerk

Welches ist der beste Algorithmus, um zu sehen, ob die beiden Benutzer verbunden sind, mit dem Grad und zeigt die möglichen Schritte im Zusammenhang?

Answer 1

Das Finden des Grades der Trennung zwischen zwei Menschen in einem sozialen Netzwerk ist nur ein Spezialfall von dem kürzesten Weg zwischen zwei Punkten in einem Graphen zu finden. Der häufigste Ansatz ist Dijkstra-Algorithmus , sondern auch eine längere Diskussion über die Kürzeste-Wege-Problem .

Darüber hinaus kann durch einen All-Paare kürzesten Weg Algorithmus ausgeführt wird, können Sie die minimale, maximale und durchschnittliche Anzahl der Grade der Trennung für das gesamte Netzwerk erfahren.

Answer 2

Einige zusätzliche Hintergrundmaterial:

Um dieses Problem generell zu lösen, werden Sie wollen Screen Scraping und andere Ad-hoc-Techniken zu vermeiden, die zu einem sozialen Netzwerk spezifisch sind. Stattdessen werden Sie wahrscheinlich wollen schauen XHTML Friends Network (XFN) , die eine Art und Weise ist die rel zu verwenden = „“ Attribut eines Hyperlinks, die die Beziehung zwischen dem Ziel des Hyper-Link, und Sie anzuzeigen. Es gibt auch einen konkurrierenden Standard FOAF genannt, die verwendet RDF .

Dieses Mikroformate für eine Weile gewesen sein, aber die Unterstützung für sie sehr viel vor kurzem gewachsen ist. Stackoverflow verwendet „me“ in dem Link auf Ihrer Profilseite. Wordpress-Blogs bieten eine einfache Möglichkeit in der Bearbeitungsoberfläche für die Blogroll diese Tags hinzuzufügen. Viele soziale Websites verwenden diese in Verbindungen zwischen Freunden Beziehungen anzuzeigen.

Aus diesem Grund hat Google interessiert sich für diese bekommen, und beginnt, diese Daten zu verminen. Sie haben einen Social Graph API , die beide XFN und FOAF Daten schürfen kann genau das zu tun, einige die Dinge, die Sie tun möchten. Ich schlage vor, Sie dort beginnen. Die nette Sache über die Google-API ist, da sie diesen in der ganz Web-Mining ist, können Sie Ihre Suche über das spezifische soziale Netzwerk verbreitern Sie im Sinne hatten.