-
pushWP erweitert euren Wordpres-Blog um ein paar Features, die helfen sollen ihn noch bekannter zu machen.
Mit BlockRules sind Wordpress User in der Lage bestimmte Inhaltsblöcke unter bestimmten Umständen anzuzeigen.
pushWP erweitert euren Wordpres-Blog um ein paar Features, die helfen sollen ihn noch bekannter zu machen.
Mit BlockRules sind Wordpress User in der Lage bestimmte Inhaltsblöcke unter bestimmten Umständen anzuzeigen.
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.
[...] Themen, die ich analysieren werden, sind schon geplant. Dabei geht es zum Einem um das “Friend of a friend” Feature, wie es z.B. Xing besitzt und zum anderen geht es um eine einfache Umkreissuche, die [...]
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”.)
Friend of a Friend…
Heute möchet ich euch ein kleine Klasse von mir vorstellen, die die Verbindung von einem User über Verbindungen zu anderen Usern bis zum gesuchten User erstellt vorstellen. Diese Funktion ist manchen vielleicht von Xing oder anderen Netzwerken beka…
RSS-Feed für Kommentare zu diesem Artikel. TrackBack-URL
Dieses Mal mit Artikeln zu den Themen Silverlight 3, MySQLDUmper, Doctrine.
Social Media (R)evolution. Weitere Themen sind noSQL, Crowdsourcing ...
PHP Frameworks optimal nutzen, Workshops für PHP Profis, Typo3 auf dem Weg zu Version 5.
Falls du Ahnung von PHP hast, dann mache es wie einige vor dir und melde dich bei uns (autor@phphatesme) als Co-Autor.