Archiv verlassen und diese Seite im Standarddesign anzeigen : Small World Phänomen
zebrawurm
30.12.2006, 18:40
Mit Small World meinte man zunächst das soziologische Phänomen, dass alle Menschen auf der Welt über sechs Zwischenschritte miteinader verbunden sind, obgleich die Wahrscheinlichkeit eines direkten Kontakts nahe bei null liegt.
Könnte das Programm die Anzahl der Zwischenschritte bei Studivz ermitteln?
mfg Bunny
Off Topic:
Darüber hab ich auch schon was gehört interesantes Thema!
Klar koennte man sich das mal im StudiVZ ansehen, die Frage ist wie repraesentativ solche 'Social-Networks' sind.
Ich hab mich mal recht lange wild durch OpenBC bzw. Xing geklickt und musste dann doch feststellen, dass die Verbindungen wirkich nicht ueber 6 Leute gingen und das mit nur 16 Kontakten dort...
es gibt kein programm.
Der Sinn deiner Aussage ist mir völlig unklar.
Klar koennte man sich das mal im StudiVZ ansehen, die Frage ist wie repraesentativ solche 'Social-Networks' sind.
Der Vergleich wäre ja das Interessante.
Ich hab mich mal recht lange wild durch OpenBC bzw. Xing geklickt und musste dann doch feststellen, dass die Verbindungen wirkich nicht ueber 6 Leute gingen und das mit nur 16 Kontakten dort...
Du hast alle durchgeklickt? Wie hast du den Wert ermittelt.
Wie würde euer Algo im groben aussehen(in Worten)? Spanner(Die keine Freunde haben) sollte dieser natürlich nicht berücksichtigen.
Der Sinn deiner Aussage ist mir völlig unklar.
der OP redet von einem ominoesen programm, welches ungenannt bleiben sollte... der sinn meiner aussage ist es, auf dieses mysterioese programm anzuspielen, welches immernoch ungesehen und ungenannt ist.
der OP redet von einem ominoesen programm, welches ungenannt bleiben sollte... der sinn meiner aussage ist es, auf dieses mysterioese programm anzuspielen, welches immernoch ungesehen und ungenannt ist.
Auch wenn ich mir jetzt besser jegliches Kommentar verkneifen würde. Aber das Gras, was du rauchst, ist bestimmt nicht gut. :)
ungesehen und ungenanntHast du evtl. uebersehen, wie das Unterforum heisst, in dem sich dieser Thread befindet, und wieso es so heisst?
Hast du evtl. uebersehen, wie das Unterforum heisst, in dem sich dieser Thread befindet, und wieso es so heisst?
ui, asche auf mein haupt. ich guck dort (name des unterforums) so gut wie nie hin...
Also hab ich das jetzt richtig verstanden. Es geht darum zu verifizieren, dass jedes Profil im Studivz über 6 Kontakte mit jedem Profil verbunden ist?
Falls ja würde ich das ungefähr so berechnen:
Ich bau aus dem Netzwerk ne Adjazenzmatrix und berechne dann von jedem Knoten zu jedem den kürzesten Weg. Ich meine der Floyd/Warshall-Algorithmus leistet das. Dann sollten alle Wege < 6 sein und alles ist gut. Problematisch ist wohl nur, dass nicht von jedem Knoten jeder andre Knoten erreichbar ist. Sprich es gibt mehrere Teilgraphen.
Aber da man so oder so die komplette Datenbank braucht, können das höchstens die Studivz Leute mal machen. Und ich nehme mal an, dass das bei solchen großen Graphen sehr lange dauert!
Korrekt ... allerdings ist dieses Problem in linearer Zeit lösbar wie der liebe Omer Reingold 2004 bereits bewiesen hat. Ich hab hier bissle was über das USTCON Problem geschrieben ...
http://code-foundation.de/?p=176
Es ist halt lediglich eine Frage des Speicherplatzes ... :D
Ach, das war alles? Er "mappt" die Laufzeit einfach auf den Speicher um? :P
@Dominik:
Entweder formulierst du so ungenau, dass deine Aussagen falsch werden, oder mir entgeht hier was Wesentliches. Ich habe das Paper allerdings nur angelesen (bis Seite 3, dann grob überflogen) und mit LOGSPACE kenne ich mich auch nicht aus.
Momentan reden wir doch vom Durchmesser des Graphen, also dass der Abstand zweier beliebiger(!) Knoten kleiner einer Konstanten ist.
In dem Paper geht es aber darum, zu entscheiden, ob zwei gegebene (also konkrete) Knoten verbunden sind. (Der Abstand fällt da vermutlich auch nebenbei mit ab.) Ist das in linearer Zeit entscheidbar (klar, z.B. durch Tiefensuche), kommt dadurch, dass wir das für alle Paare prüfen müssen noch der Faktor n^2 dazu.
Der in dem Paper vorgestellte Alg. hat sowieso polynomielle Laufzeit.
Irgendwie passt das nicht zusammen. Oder habe ich an der falschen Stelle geguckt?
Nebenbei bemerkt ist die Aussage in deinem Blog definitiv falsch:
The main question is:
Are there two vertices s and t in a directed graph that are connected by a path? Das wäre äquivalent zu der Frage, ob es eine Kante in dem Graphen gibt, denn hier könnte ich s und t beliebig wählen.
@Dominik:
Entweder formulierst du so ungenau, dass deine Aussagen falsch werden, oder mir entgeht hier was Wesentliches. Ich habe das Paper allerdings nur angelesen (bis Seite 3, dann grob überflogen) und mit LOGSPACE kenne ich mich auch nicht aus.
Hehe, ok ... ;-) we will see.
Also Small-World-phenomenon hat nicht direkt was mit ST-connectivity zu tun, obwohl ...:
Man nehme einen Graphen K und beweise, dass alle Knoten dieses Graphen über max. 6 Verbindungen zusammenhängen.
Mit ST-connectivity kann man in größeren Netzen erst einmal schauen, ob ÜBERHAUPT eine Verbindung besteht. Über die Dimension wird natürlich nichts ausgesagt ... anyway, ich dachte, die Thematik könnte interessant sein. Hab mir nicht allzuviel Gedanken über den genauen Bezug zum small-world-phenomenon gemacht.
Momentan reden wir doch vom Durchmesser des Graphen, also dass der Abstand zweier beliebiger(!) Knoten kleiner einer Konstanten ist.
In dem Paper geht es aber darum, zu entscheiden, ob zwei gegebene (also konkrete) Knoten verbunden sind. (Der Abstand fällt da vermutlich auch nebenbei mit ab.)
Korrekt ... so sehe ich das auch, siehe oben.
Ist das in linearer Zeit entscheidbar (klar, z.B. durch Tiefensuche), kommt dadurch, dass wir das für alle Paare prüfen müssen noch der Faktor n^2 dazu.
Der in dem Paper vorgestellte Alg. hat sowieso polynomielle Laufzeit.
Irgendwie passt das nicht zusammen. Oder habe ich an der falschen Stelle geguckt? Nebenbei bemerkt ist die Aussage in deinem Blog definitiv falsch:Das wäre äquivalent zu der Frage, ob es eine Kante in dem Graphen gibt, denn hier könnte ich s und t beliebig wählen.
Das wage ich mal definitiv zu bezweifeln. :D Mein Bloggeschreibsel sagt doch genau das gleiche aus wie das hier. Oder irre ich?
st-connectivity (reachability) refers to a problem in computer science and computational complexity theory, a decision problem asking if two vertices s and t in a directed graph are connected by a path.
The language of the decision problem is given by PATH = {<D, s, t> | D is a directed graph with a path from vertex s to t}
http://en.wikipedia.org/wiki/ST_Connectivity
Wenn Du Dich mit den Autoren dieses Geschriebenen rumschlagen willst ... #crypto auf freenode. Ich versteh aber auch nur wenig/bis gar nichts von dem was die labern. ;-)
IcePic schrieb ja was von wegen "Teilgraphen, da nicht alle miteinander verbunden sind .." genau darauf spielt mein Posting an. Oder bist Du der Meinung dass ST-connectivity nichts damit zu tun hat?
HTH schönen Abend
Also Small-World-phenomenon hat nicht direkt was mit ST-connectivity zu tun, obwohl ...:
Man nehme einen Graphen K und beweise, dass alle Knoten dieses Graphen über max. 6 Verbindungen zusammenhängen.
Mit ST-connectivity kann man in größeren Netzen erst einmal schauen, ob ÜBERHAUPT eine Verbindung besteht. Über die Dimension wird natürlich nichts ausgesagt ... anyway, ich dachte, die Thematik könnte interessant sein. Hab mir nicht allzuviel Gedanken über den genauen Bezug zum small-world-phenomenon gemacht. Ist ja auch interessant. Ich dachte nur, du siehst hier einen stärkeren Bezug, der mir entgangen ist.
Mein Bloggeschreibsel sagt doch genau das gleiche aus wie das hier. Oder irre ich?
st-connectivity (reachability) refers to a problem in computer science and computational complexity theory, a decision problem asking if two vertices s and t in a directed graph are connected by a path.In der Tat, du irrst. Es sind die kleinen Worte die wichtig sind. Diese Aussage ist korrekt. Hier werden s und t ja vorgegeben. Dein Bloggeschreibsel ist gleich der folgend formulierten Aussage:
st-connectivity (reachability) refers to a problem in computer science and computational complexity theory, a decision problem asking if there are two vertices s and t in a directed graph that are connected by a path.
Der Unterschied liegt darin, ob s und t gegeben oder frei wählbar sind.
IcePic schrieb ja was von wegen "Teilgraphen, da nicht alle miteinander verbunden sind .." genau darauf spielt mein Posting an. Oder bist Du der Meinung dass ST-connectivity nichts damit zu tun hat?Doch, doch. Ich dachte halt, du redest vom Durchmesser-Problem und nicht nur von der Erreichbarkeit. Das diese in linearer Zeit lösbar ist, ist ja auch nicht so die umwerfende Neuigkeit. Da muss man nur eine Tiefen-/Breitensuche machen. Das wurde sicher auch nicht erst 2004 entdeckt.
HTH schönen Abend:)
Zumindest meine Verwirrung ist beseitigt.
Der Unterschied liegt darin, ob s und t gegeben oder frei wählbar sind.Alright, das leuchtet ein ... unter dem Blickwinkel hab ich das natürlich noch gar nicht betrachtet, aber es ergibt Sinn. ;-)
Doch, doch. Ich dachte halt, du redest vom Durchmesser-Problem und nicht nur von der Erreichbarkeit. Das diese in linearer Zeit lösbar ist, ist ja auch nicht so die umwerfende Neuigkeit. Da muss man nur eine Tiefen-/Breitensuche machen. Das wurde sicher auch nicht erst 2004 entdeckt.
Nein, aber der Omer-Beweis soll anscheinend schon ne tolle Sache sein. Problem:
Genau bis zu diesem Grad kann ich mitreden, mehr dann aber auch nicht. Ich verstehe die Grundidee und die Absicht ... aber wie das alles dann von Statten geht, is mir bisher noch nicht klar geworden bzw. hab ich nicht mehr Zeit da reininvestiert da diese einfach fehlt. Muss mich hier also leider ausklinken ... Anyway, danke für den Hinweis :)
Das Thema sollte man, falls Zeit vorhanden, auf jeden Fall nochmals tiefer durchleuchten da sich gerade solche Probleme oftmals auf anderen Probleme "reduzieren" lassen oder umgekehrt. Und dann sind wir ratz-fatz wieder bei Graphen-Homomorphismen mit denen man herrlich Zero-Knowledge-Dinge anstellen kann. :D
Schönen Abend