Kategorien
Six Degrees of Separation (friend of a friend)
Nein, hier geh’ts nicht um den Film-Remake mit Will Smith (Six Degrees of Separation) sondern um eine Funktion die man öfters auf Social-Web 2.0 Seiten sieht. Ich kenne diese Person über ….
Kleine Geschichtsstunde.
Ich bin so frei und übernehme den Text des Wikipedia Artikels:
1967 startete der Psychologe/Soziologe Stanley Milgram (übrigends der selbe welcher das „Milgram Experiment“ durchführte) das „Small World“ Experiment. Milgram erstellte eine Art Informationspaket, das 60 zufällig ausgewählte Teilnehmer an jeweils eine vorher festgelegte Person in Boston zu senden hatten. Als Startpunkte wählte er Personen aus den sozial und geografisch weit von der Zielstadt entfernten Städten Omaha und Wichita. Die Aufgabe der Teilnehmer bestand darin, das Paket nicht direkt an die Zielperson zu senden, sofern sie diese nicht persönlich kannten (bei ihrem Vornamen ansprachen), sondern an eine Person, die sie persönlich kannten und bei der die Wahrscheinlichkeit höher war, dass sie die Zielperson kannte. Gleichzeitig waren die Teilnehmer angehalten, grundlegende Daten über sich selbst in einer Tabelle zu vermerken und eine Postkarte an die Wissenschaftler zu senden, um die Kette nachvollziehbar zu machen.
Insgesamt erreichten drei Pakete die Zielpersonen mit einer durchschnittlichen Pfadlänge von 5,5 oder aufgerundet sechs. Die Wissenschaftler schlossen daraus, dass jede Person der US-amerikanischen Bevölkerung von jeder anderen Person der USA durchschnittlich durch sechs Personen getrennt ist oder, andersherum formuliert, durch durchschnittlich sechs Personen erreicht werden kann.
In einem zwei Jahre später durchgeführten Experiment mit 296 möglichen Ketten wurden 217 Pakete gestartet und 64 erreichten ihr Ziel.[1] Im Jahre 1970 folgte ein weiterer Versuch, der, neben der Entfernung der Menschen untereinander, auch mögliche Grenzen zwischen ethnisch unterschiedlichen Gruppen untersuchen sollte. Von 270 mit afroamerikanischen Personen als Ziel gestarteten Paketen erreichten 13 % diese Person, während 33 % von wiederum 270 an „weiße“ Personen adressierte Pakete ihr Ziel erreichten.[2]
Möchte man jetzt die Verbindung von Person A zu Person B darstellen, läuft man schnell in das „shortest path problem„. Um dies zu lösen eignet sich der sogenannte „Dijkstra-Algorithmus„.
Wie sieht jetzt die Impementierung in PHP aus ?
Wir nehmen an wir haben eine Tabelle mit unseren Usern, und eine Zweite die Verbindungen von den Usern untereinander darstellt (fromid => toid).
CREATE TABLE IF NOT EXISTS `users` ( `id` int(11) NOT NULL auto_increment, `firstnames` varchar(200) NOT NULL, `lastname` varchar(200) NOT NULL, PRIMARY KEY (`id`) ) ENGINE=MyISAM DEFAULT CHARSET=utf8 AUTO_INCREMENT=22 ; CREATE TABLE IF NOT EXISTS `links` ( `link_id` int(11) NOT NULL auto_increment, `fromid` int(11) NOT NULL, `toid` int(11) NOT NULL, PRIMARY KEY (`link_id`) ) ENGINE=MyISAM DEFAULT CHARSET=utf8 AUTO_INCREMENT=11 ;
Als erstes brauchen wir den theoretisch längsten Pfad: Dies wäre die Anzahl der User +1.
Nächster Schritt das Basis array, welches die schritte von person x zu person y festlegt, da wir dies aber noch nicht wissen inintialisieren wir das array mit -1 (unbekannter pfad). Einen Pfad kennen wir jedoch nämlich den Pfad von $fromid zu $fromid. Dieser hat die Distanz 0.
private function _fetchUser(){
$m_user = new UserModel();
$this->_users = $m_user->fetchAll();
$this->_longestPath = $this->_users->count()+1;
}
private function _buildSkel($fromid){
if(!$this->_users){
$this->_fetchUser();
}
foreach($this->_users as $user){
$this->_nodes[]=$user->id;
$this->_dist[$user->id]=$this->_longestPath;
$this->_previous[$user->id]=-1;
}
if($fromid>0)
$this->_dist[$fromid]=0;
}Jetzt beginnt der Spass, suchen des kürzesten Pfads von User A zu User B:
private function _findPath($toid){
$Q = $this->_nodes;
while(count($Q)>0){
$qsize=count($Q);
$unode = $this->_findMin($Q);
if($unode == $toid){
break; // We have found ToId
}
$u = array_search($unode, $Q);
$Q[$u]=false;
$Q = array_filter($Q);
if($qsize == count($Q)){
throw new Exception("Qsize doesnt shrink!");
}
$m_link = new LinksModel();
$invitees = $m_link->fetchAll("fromid='$unode'");
$inviters = $m_link->fetchAll("toid='$unode'");
if($invitees->count()>0)
$this->_relaxNeighbors($unode,$invitees,'toid');
if($inviters->count()>0)
$this->_relaxNeighbors($unode,$inviters,'fromid');
}
}
private function _relaxNeighbors($unode,$neighbors,$col){
foreach($neighbors as $neighbor){
$this->_relax($unode,$neighbor->$col);
}
}
private function _relax($u,$v){
if($this->_dist[$v] > $this->_dist[$u]+1){
$this->_dist[$v]=$this->_dist[$u]+1;
$this->_previous[$v] = $u;
}
}
private function _findMin($nodes){
$keys = array_keys($nodes);
$minid = $nodes[$keys[0]];
$mindist = $this->_dist[$minid];
foreach ($keys as $key){
$tnode = $nodes[$key];
if($this->_dist[$tnode] < $mindist){
$mindist = $this->_dist[$tnode];
$minid=$tnode;
}
}
return $minid;
}Wir laufen also unsere Knoten durch und berechnen die Kantenlängen für jeden knoten. Dabei wird ein bereits bekannter kürzester Weg benutzt und um eine Kante (zu dem jeweils nächsten) Nachfolgeknoten ergänzt. Dadurch entsteht letztendlich eine Baumstruktur, welche die kürzesten Wege von einem Startknoten repräsentiert.
Die gesamte Klasse findet sich auf http://www.cwd.at/shortestpath.phps
Raum für Optimierung gibt es genug. Zb. das errechnen der Kantenlängen jedes Users zueinander und speichern in einer Tabelle. Oder aber auch den gesamten Algorithmus in die Datenbank auszulagern.
Absolut interessant – danke für den Beitrag.
Hab mich auch schon mal gefragt wie die Communities das bewerkstelligen aber
da ich es bis jetzt nicht gebraucht habe…
Da es sich um einen ungewichteten Graphen handeln dürfte, verstehe ich nicht, weshalb der Dijkstra-Algorithmus angewendet wird. Eine simple Breitensuche löst nämlich auch das kürzeste-Wege-Problem auf ungewichteten Graphen und ist nicht nur schneller zu implementieren, sondern auch komplexitätstheoretisch schneller.
Außerdem verstehe ich nicht, was du mit „Kantenlängen für jeden Knoten“ meinst, denn eine Kante existiert immer zwischen genau zwei Knoten – meintest du das Erstellen von neuen Kanten (mit einem Gewicht) oder die Weglänge zwischen zwei Knoten? Beim Erstellen von neuen Kanten muss man aufpassen, da der Platzverbrauch auf O(n^n) (bei einem gerichteten Graphen) steigt, was schon bei einer ziemlich kleinen Zahl nicht mehr effizient machbar ist.
Ich danke dir bereits für die Antworten im Voraus und hoffe auf weitere solcher Artikel. 🙂
@Backflash:
Kantenlängen ist wohl falsch ausgedrück, da hast nicht ganz unrecht. Gemeint ist alle verbindungen die dieser Knoten besitzt.
Du hast auch nicht ganz unrecht das die Breitensuche hier vielleicht einen tick schneller ist, allerdings stammt der code der klasse aus einer anwendung die eine wertigkeit der verbindungen enthält. (zb. ich vertraue diesen user 0-100) Und hier ist die „Weglänge“ dann durchaus interessant, in diesem fall der vertrauenswürdigste pfad.
wow Super Artikel! zu diesem Thema könnt ihr ruhig öfters was bringen 😉
Vertrauenswürdige Pfade klingen ziemlich interessant, wobei man Vertrauen nicht wirklich quantifizieren kann. 😉
P.S.: Es hätte übrigens in meinem ersten Kommentar O(n^2) bzw. O(n*n) heißen müssen.
Super Beitrag, danke schön. Hatte den Nils ja schon mal gefragt ob er die friend of a friend Geschichte hier mal bringen kann. Kann ich gerade gut für mein Projekt gebrauchen.
Moin,
die Frage ist nur ob man mit so einem diskreten Ansatz noch durch die Daten kommt,
diese Portale haben ja ohne problem 10-20k Benutzer und da ist so
eine Suche schon nicht mehr just-in-time zu lösen. Also entweder eine Online
Variante von der Breitensuche oder man hat die dabei entstehenden Bäume eh schon
in der datenbank vorliegen, und Bäume lassen sich mit Hilfe von Binärer Indexierung
gut in der DB ablegen. Ja, ist ne ganze Ecke informationen die da Anfallen, aber
solche Portale verdienen ihr Geld ja auch mit der Analyse solcher Netzwerke.
mfg
Binäre Indexierung?
Noch nie gehört, hast du vllt irgendwelche Research-Paper oder andere Informationen?
@sargon: Keine Frage. Aber wie es auch im artikel steht „genug raum für optimierung“ SQL bietet ja selbst die möglichkeit mit binären bäumen zu arbeiten. vgl. http://www.teialehrbuch.de/Kostenlose-Kurse/SQL/14695-Binaere-Baeume.html bzw http://www.artfulsoftware.com/infotree/queries.php?&bw=1680#766
In ein paar wochen kann ich dir sagen ab welcher user bzw verbinungsanzahl die „just in time“ berechnung nicht mehr funktioniert 🙂 Der Vorteil ist ja daß die Querys sehr einfach sind, und auch das Result nicht sehr groß ist, dh. man kann hier den querycache von zb. MySQL voll ausnutzen, und Hauptspeicher kostet ja heutzutage nichts mehr. (erst vorige woche 8GB für meine Workstation um 89 euro erstanden 🙂
@Tobias: Binäre Indexierung kannte ich auch nicht, aber ich denke er meint die Binäre Suche (vgl. http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche )
@backflash „Vertrauenswürdige Pfade klingen ziemlich interessant, wobei man Vertrauen nicht wirklich quantifizieren kann. “
Im konkreten fall gehts darum ob man die person schon sehr lange persönlich kennt, oder erst seit kurzem, oder nur mit der person telefoniert/gemailt hat… usw.
Könnte mir aber auch vorstellen das man damit zb. ein „Web of Trust“ aufbauen könnte, wie es auch zb. CACert verwendet. (Personen werden durch andere Personen „beglaubigt“.)
Klingt ganz interessant, wir betreiben selbst ein großes Social Network, hier haben wir es allerdings anders lösen müssen, da es bei über 88Mio Verbindungen zwischen Usern dann doch ein wenig schwer wird 😉
Die Freundestabelle hat 3,4GB =)
Ich beschaeftige mich schon seit recht langer Zeit mit diesem Thema. Zur gerade mal wieder etwas intensiver. Bei einem Graphen in „Xing“ Größe (~9Mio User und geschätzten durchschnittlichen Kontakten von 100) behaupte ich mal: Breitensuche kann man vergessen, SQL kann man vergessen, Graphen-Algorithmen kann man vergessen … Vorberechnen von Daten kann man auch vergessen.
Die Lösung auf die ich gekommen bin ist denkbar einfach – Alle Kontaktlisten (sortiert) im Speicher, einfache Datenstrukturen, hochoptimierte Schnittmengen-Funktion und dann Brute-Force durch die Listen (in C) solange bis genug Ergebnisse vorhanden sind. Bislang sieht es ganz gut aus. Die Anzahl der User ist dabei vollkommen egal – das einzige was zaehlt ist der Wert der durchschnittlichen Kontakte pro User (bei 100 Kontakten ist auf Distanz 6 mit theoretischen 100^6 Pfad-Enden zu rechnen!).
Was mich sehr interessieren würde:
Kennt jemand von euch die durchschnittliche Kontakte-Anzahl in „großen“ Communities? Klar sieht man immer wieder Leute (bei Xing) die 5000+ Kontakte haben – aber wie gesagt, was zaehlt ist der Durchschnitt.