Small Worlds und Communities

Small Worlds und Communities
1.
Der Begriff Small World
1.
2.
3.
4.
5.
2.
Communities
1.
2.
3.
Grundbegriffe
Clusteringkoeffizient
Zufällige vs reguläre Grafen
Modelle von SW Grafen
Beispiele
Algorithmisierung von Communities
Die Begriffe Hubs und Authorities
Literatur
1
1. Der Begriff der Small World
• A trifft B und beide stellen zu ihrer Überraschung fest,
dass sie C kennen.
• Im Deutschen durch Phrase „Die Welt ist ein Dorf.“
repräsentiert
• Der englische Begriff wurde von Milgram durch
berühmtes Briefkettenexperiment geprägt. (Zwei USBürger sind durch im Schnitt 6 Personen verbunden)
• Später durch Filmdatenbank, Baseballdatenbank usw.
wieder belegt.
2
1.1. Wichtige Begriffe
• Graf G = (V,C)
• Grad der Verbundenheit deg(v) eines Knotens gibt an, mit
wievielen anderen er verbunden ist.
• Weglänge
zwischen zwei Knoten A und B ist die
Anzahl der Kanten, die besucht werden, um von A nach B
zu kommen.
• Durchschnittliche minimale Weglänge: Wie lang die
kürzesten Wege zwischen allen Knoten in einem Grafen
sind.
3
1.2. Clusteringkoeffizient
• Nachbarn eines Knotens v sind:
• Clustering Koeffizient vergleicht, wie oft die Nachbarn
eines Knotens miteinander verbunden sind, gemittelt über
den gesamten Grafen:
• Hoher Clustering Koeffizient: 13 Knoten, 21 Kanten
(c = 0,66)
(c = 0)
4
1.2.1. Clusteringkoeffizient II
D
G
B
E
H
A
I
J
?
C
F
5
1.3. Zufällige und reguläre Grafen
• Zufälliger Graf ist (stark vereinfacht) ein Graf, bei dem
Knoten zufällig miteinander verbunden sind
• Regelmäßiger Graf ist ein Graf, bei dem es eine Ordnung
über den Knoten gibt und Knoten A mit C erst dann
verbunden sind, wenn A und B, sowie B und C bereits
miteinander verbunden sind. (Auch “Matrixgrafen”
gehören hierzu)
zufälliger Graf
regelmäßige Grafen
6
1.3.1. Small World Grafen
• SW Grafen als Optimum zwischen zwei Extremen:
Graph:
Weglänge
Cluster Wert
regulär
lang
hoch
zufällig
kurz
klein
small-world
kurz
hoch
• Bislang Erklärung dafür, warum diverse
Seuchenausbreitungs- , Nachrichtenverbreitungsmodelle
und andere auf zufälligen Graphen basierende
Simulationen mit ihren Ergebnissen daneben lagen
• Cluster Wert: Überall im Grafen abgrenzbare
Häufungen (allerdings hängen diese komplex miteinander
zusammen)
• Kurze Weglänge möglicher Hinweis auf effizientest
mögliche assoziative Speicherung der Wörter im Gehirn
7
1.4. Modelle für Small World Grafen
•
•
•
•
•
Für SWG gilt, dass die durchschnittliche minimale Weglänge einer
Gesetzmäßigkeit folgt:
Ursprünglicher Modellvorschlag von Watts & Strogatz 98: Man nehme
einen regelmäßigen Grafen und verbinde zufällig eine Kanten neu.
Dieses Modell später durch preferential attachment Modell (Barabasi)
abgelöst, da es zu einfach war und scale-freeness (Eigenschaften
gelten unabhängig von Größe und Beschädigung des Netzes) nicht
erklären konnte.
Preferential attachment: Beim Anbinden eines neuen Knotens an
einen vorhanden verbinden und fast alle seine “Freunde” übernehmen.
Aber auch dieses Modell kann nicht alle Effekte zufriedenstellend
beschreiben, wie etwa Unterschiede in Verbungsnheitsgraden usw.
8
1.5. Beispiele für Small Worlds
Dabei stets wichtig, dass wesentlich weniger Kanten
(Verbindungen) existieren, als theoretisch möglich wären:
n*(n-1)/2
• Stromnetz eines Landes
• Wie Gehirnzellen von verschiedenen Lebewesen
miteinander verbunden sind
• Wortgraph
• Internetgraph
• Soziale Netzwerke im allgemeinen (Milgram)
• Strassennetzwerk
9
1.5.1. Anwendung der Small Worlds
• Besseres Modell für Seuchenverbreitung
• Besseres Modell für Erklärung des übergangs von
Aggregatzuständen diverser Zubstanzen
• Disambiguierung von Wörtern
• Neue P2P Suchmaschinen
10
1.5.2. Small World in der Sprache
• Graf: jeweils 100.000 Knoten und 20Mio Kanten
Zufälliger G.
Regelmäßiger G.
Kookkurrenzg.
c
0.000001
0.0001
0.05
d
5
1000
3.8
Anzahl Kookkurrenzen von Wörtern nach Häufigkeit sortiert
100000
10000
1000
100
10
1
100
1000
10000
100000
11
2. Communities
• Communities sind Sammlungen von Webseiten, die Inhalte
zu ein und demselben Thema bieten und sich auf einander
beziehen.
• Ursprünglich Begriff aus dem Englischen für Gruppe von
Menschen mit starkem Zusammengehörigkeitsgefühl
(Glaube, Politik usw.)
• Im Sprachgebrauch hat sich “Community” auf vielfältige
Weisen verankert: “Frag mal einen von den, die kennen
sich aus.” (Wenn nach speziellem Wissen gesucht wird)
• Im Web wie im Sozialen ist auch beobachtbar, dass
Communities eigenen Sprachgebrauch entwickeln (Welche
Community? “Bitte 2 TT gerade Strecken!”)
12
2.0.1. Nutzen von Communities
• Im Web finden sich Communities, um Information zu
sammeln, somit ist konzentriert Information findbar, wenn
zunächst Community “extrahiert” werden würde.
• Somit wäre ein das Web abgrasender Suchalgorithmus, der
weiss, was eine Community ist und dies ausnutzt,
erfolgreicher, als einer, der zufällig Links probiert oder via
Tiefen/Breitensuche.
• Jeder Teilnehme einer Community trägt zwar zu den
Themen der Community bei, aber jeweils das seiner
Meinung nach wichtigste, somit müßte die gesamte
Community erwischt werden, um einen erschöpfenden
Überblick über deren Inhalte zu erlangen.
13
2.1. Algorithmisierung von Communities
• Community als Clique
– C ist Subgraf, für den gilt, dass alle Knoten miteinander
verbunden sind.
– Probleme:
• Berechnung, bzw. Bestimmung von Cliquen geht nicht besser,
als alles durchzuprobieren.
• Es sind selten wirklich alle Knoten miteinander verbunden –
nicht jeder kennt jeden in einer Clique. Schärfer formuliert:
Wir wollen auch Cliquen erfassen, die hierarchische Struktur
aufweisen.
• Webrings – sind communities, aber nur minimal miteinander
verbunden!
14
2.2. Authorities und Hubs
•
•
Ähnlich zu PageRank
Es werden zwei Klassen von Knoten unterschieden:
•
Bei PageRank werden (vereinfacht) zuerst die Authority Gewichte,
dann daraus die Hub Gewichte berechnet, rekursiv.
Auf Suchanfragen angewandt, werden diejenigen top 10 Webseiten
ausgegeben, die die hoechsten Authority Gewichte tragen – sie stellen
dann den Kern der gesuchten Community dar
Auch hier Webrings wieder problematisch
•
•
15
2.2.1. HITS Algorithmus
•
•
Erweiterung des Hub- und Authoritybegriffs um Gewichtung der
Kanten. Ausserdem soll nicht zu einer Suchanfrage
nur eine C. gefunden werden, sondern alle vorh.
Methode:
– Gewicht der Kanten ist Ähnlichkeit
zwischen den repräsentierten Dokumenten
– Modifizierte Definition von C.:
C = dichter, gerichteter in zwei Teile teilbarer
Subgraf
– Die ist ähnlich zu Bibliometrie, bei welcher
Veröffentlichungen darüber verglichen werden, wie oft
sie zusammen mit einer anderen zitiert worden sind.
•
Bsp: Fanseiten: Es entsteht ein Bipartiter Graf, bei dem es eine
offizielle, sowie einige inoffizielle sehr bekannte Fanseiten gibt, sowie
eine unzahl privater Webseiten zu diesem Thema
16
2.2.2. Weitere Algorithmen
• Probleme allgemein bisher:
– Annahme, dass ein Knoten immer nur in einer Community
sein kann. Allerdings beinhalten einzelne Seiten Links zu
unterschiedlichen Themen, bzw. Webseiten können Teil von
mehreren Communities sein.
• Typische Wissenschaftlerseite:
Publikationen (Mathematik, Grafentheorie)
Material für Studenten (Grundkurse Algorithmen usw.)
Hobby (Schachspielen, Reiten)
– Zentralistische Sichtweise: Alles dreht sich um authoritäten
– echt demokratische Cs wie Webrings können auf diese
Weise nicht erkannt werden.
17
2.2.3. Weitere Ansätze
• Neuronale Netze:
– Es wird davon ausgegangen, dass sich aktivität in
“verknotungen” ansammeln müßte und diese sind dann
communities. (allerdings ist Komplexität sehr hoch)
• Min-cut:
– An welcher Stelle kann ein (allerdings bereits vorher
extrahierter) Graf geteilt werden, so dass möglichst wenige
Kanten/Knoten gelöscht werden müssen und zerfallende
Teile möglichst groß sind.
• Ameisen:
– Sog. Ameisen laufen von einem Startknoten zufällig los und
manche kommen recht bald wieder, was auf zyklen
schließen läßt -> Community.
18
2.3. Zu erfüllende Eigenschaften einer
Communitydefinition
•
Strukturen: verschiedene Linkstrukturen sollten gleichberechtigt und
auffindbar sein. Allerdings selten in der prototypischen Form
anzutreffen
– Zentralistische (Authority/Hubs)
– Webringe
– „demokratische“ Formen.
•
•
•
•
•
Mehrdeutigkeit: Ein Knoten in mehrere Communities
Enthaltensein: Communities können Bestandteil von anderen,
größeren Communities sein.
Relationen: Es muss möglich sein, dass Communities untereinander in
Beziehung stehen
Kardinalität: Ein Knoten muß nicht Mitglied einer Community sein
Natürlichkeit: Schließlich sollte eine bestimmte Definition einer
Community immer noch dem intuitiven Begriff von Community
entsprechen.
19
2.3.1. Eigenschaften von Algorithmen
• Stabilität: Der Algorithmus sollte nicht bei unwesentlich
veränderten Parametereinstellungen deutlich andere
Ergebnisse liefern.
• Laufzeit: Das Laufzeitverhalten sollte zwischen dem
Linearen (wenn auch mit großer Konstante) und
quadratischen Bereich liegen, da sonst bereits
herkömmliche Clusteralgorithmen genommen werden
könnten, deren Komplexität meist zwischen quadratischem
und kubischem Bereich liegen.
20
3. Literatur – Small Worlds
•
•
•
•
•
•
•
A.L. Barabasi et al . Scale-free characteristics of random networks: the
topology of the World-wide web, Physica A (281)70-77, 2000
R. Ferrer i Cancho, R. V. Solé (2001): The Small-World of Human Lan-guage
http://www.santafe.edu/sfi/publications/
G. Heyer, U. Quasthoff, T. Wittig, C. Wolff. Learning Relations Using
Collocations, A. Maedche, S. Staab, C. Nedellec and E. Hovy, (eds.), Proc.
IJCAI Workshop on Ontology Learning, Seattle/ WA, 2001
J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc.
32nd ACM Symposium on Theory of Computing, 2000
S. Milgram. The small world problem. Psychology Today 2, pp. 60-67, 1967.
M. Steyvers, J. B. Tenenbaum. The large-scale structure of semantic
networks: statistical analyses and a model of semantic growth. M. Steyvers,
J. B. Tenenbaum, Cognitive Science, 2002
Watts, D.J., S.H. Strogatz (1998): Collective dynamics of ‘small-world’
networks; Nature 393:440-442
21
3.1. Literatur - Communities
•
•
•
•
•
•
•
•
•
•
•
•
Brin, S., Page, L. (1998): The anatomy of a large scale hypertextual web search engine. In
Proceedings of WWW7, Brisbane, Australia.
Chakrabarti, S., Dom, B., Gibson, D., Kumar, R., Raghavan, P., Rajagoplan, S., and Tomkins, A.,
(1998): Spectral filtering for resource discovery. In ACM SIGIR workshop on Hypertext
Information Retrieval on the Web.
Flake, G., W., Lawrence, S., Gilles, C., L., Coetzee, F., M. (2002): Self-organization and
identification of web communities. IEEE Computer, pp. 66-71.
Garey, M., R., & Johnson, D., S. (1979): Computers and Intractability, W.H. Freeman and
Company.
Gibson, D., Kleinberg, J., M., Raghavan, P., (1998): Inferring Web Communities from Link
Topology. in Proceedings of the 9th ACM Conference on Hypertext and Hypermedia, Pittsburgh,
Pennsylvania, pp. 225-234.
Kleinberg, J., M. (1999): Authoritative sources in a hyperlinked environment. Journal of the
ACM, vol. 46, no. 5, pp. 604-632, 1999
Kleinberg, J., M., Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A., S. (1999): The web as
a graph: Measurements, models and methods. Lecture Notes in Computer Science, vol. 1627,
pp.1-18.
Kumar, R., Raghavan, P., Rajagopalan, S. (1999): Trawling the Web for emerging
cybercommunities. Computer Networks (Amsterdam, Netherlands), vol 31. no. 11-16, pp. 14811493.
Matsumura, N.,Ohsawa, Y., Ishizuka, M. (2001): Future Directions of Communities on the Web.
Page, L. (1997): PageRank: Bringing order to the Web. Stanford Digital Linraries working paper.
Pirolli, P., Pitkow, J., Rao, R. (1996): Silk from a sow's ear: Extracting usable structures from the
web. In Proc. ACM Conf. Human Factors in Computing Systems, CHI. ACM Press.
Verbeurgt, K. (2003): Inferring Emergent Web Communities, SSGRR-2003W
22