=Paper=
{{Paper
|id=None
|storemode=property
|title=Zuverlässige und schnelle Erzeugung von Zufallsnetzwerken für Evaluationszwecke
|pdfUrl=https://ceur-ws.org/Vol-750/yrs01.pdf
|volume=Vol-750
}}
==Zuverlässige und schnelle Erzeugung von Zufallsnetzwerken für Evaluationszwecke==
https://ceur-ws.org/Vol-750/yrs01.pdf
Zuverlässige und Schnelle Erzeugung von
Zufallsnetzwerken für Evaluationszwecke
Darko Obradović, Wolfgang Schlauch
AG Wissensbasierte Systeme, Fachbereich Informatik, TU Kaiserslautern
Kaiserslautern, Germany
darko.obradovic@dfki.uni-kl.de
wolfgang.schlauch@dfki.uni-kl.de
Abstract— Die Analyse von Netzwerken hat in der Soziologie sozialen Bewegungen und politischen Netzwerken beschäf-
seit dem 20. Jahrhundert einen hohen Stellenwert, ist aber tigte. Besondere Erwähnung verdient insbesondere Stanley
auch für andere Disziplinen interessant. Zum Beispiel bei der Milgram, der mit der These des Kleinen-Welt-Phänomens die
Untersuchung von neuronale Netzen oder DNA-Transkriptionen
in der Biologie. Für die Evaluation von Mustern gibt es verschie- Untersuchung der sozialen Netzwerke vorantrieb und durch
dene Methoden, wobei wir in dieser Arbeit den Fokus auf den die These, dass in den USA jeder Mensch mit jedem anderen
statistischen Vergleich des realen Netzwerks mit gleichartigen über durchschnittlich sechs Verbindungen bekannt sei, großes
Zufallsnetzwerken legen, da diese in besonderem Maße obje- Interesse erweckte, auch wenn dieses Experiment methodisch
tive Aussagen liefern kann. Für diese Methode existieren zwei stark umstritten ist.
Verfahren mit verschiedenen Unzulänglichkeiten, welche beide
nicht in allen Fällen zuverlässig machen. Für das Markov-Ketten Durch Duncan J. Watts und Steven H. Strogatz wurde
Monte-Carlo Verfahren versuchen wir, das offene Problem einer das Kleine-Welt-Phänomen 1998 weiter untersucht [3]. Sie
effizienten, aber auch zuverlässigen Schrittzahl mit einem neuen brachten interessante neue Ergebnisse hervor im Bezug auf
Ansatz anzugehen. Das Idee besteht darin, eine möglichst exakte bestimmte Effekte wie den Abstand zweier Knoten voneinan-
Berechnung dieser Schrittzahl für bestimmte KLassen von Netz- der. Sie nahmen in der realen Welt vorkommende Netze, zum
werken über ein Modell der Markov-Kette zu erreichen. Sollte
uns das in unserer zukünftigen Arbeit fundiert gelingen, wäre Beispiel den Graphen der Zusammenarbeit von Schauspielern,
dies der bisherigen empirischen Methode deutlich überlegen. und untersuchten sie, schlugen aber auch die genauere Unter-
suchung von anderen sozialen Netzwerken vor.
I. E INFÜHRUNG
B. Evaluation von Netzwerkeigenschaften
In diesem Papier beschäftigen wir uns mit der Analyse
von Netzwerkstrukturen, welche theoretisch stark in der Gra- Bei der Analyse von realen Netzwerken sind zwei grundle-
phentheorie der Mathematik verwurzelt ist, praktisch aber vor gende Methoden stark verbreitet.
allem durch die Untersuchung von sozialen Netzwerken vor- Zum Einen die explorative Analyse, bei welcher der For-
angetrieben wird [1]. Trotz der Fokussierung dieser Disziplin scher eine graphische Darstellung des Netzwerks interaktiv
auf soziale Netzwerke, woher sie auch ihren Namen Soziale durchsieht, oder spezielle Layouts betrachtet, um auffällige
Netzwerkanalyse (SNA) erhielt, lassen sich die Methoden auf Muster oder Eigenschaften zu entdecken. Diese Entdeckungen
jede andere Disziplin übertragen, welche ihre zu analysieren- sind dann das Ergebnis der Analyse. Hierfür existieren eine
den Strukturen in Netzwerken repräsentieren kann. Folglich Vielzahl von Tools wie bspw. GUESS.
zeigten sich auch schon erste Anwendungen der Biologie in Zum Anderen gibt es noch die Metriken-basierte Analy-
Neuronalen- oder Gen-Netzwerken. se, bei welcher Metriken auf dem Netzwerk (z.B. Dichte,
Durchmesser, ...) oder Metriken für einzelne Knoten (z.B.
A. Historie der Sozialen Netzwerkanalyse [2] Zentralität, Clustering-Koeffizient, ...) im Durchschnitt oder
Ende der 1930er Jahre tauchte bei John Moreno erstmals in ihrer Verteilung betrachtet werden. Hier können aber auch
das Konzept des Soziogramms auf, mit dem er soziale Bezie- Algorithmen zur Suche bestimmter quantifizierbarer Muster
hungen formalisierte, um sie danach methodisch zu untersu- zum Einsatz kommen (z.B. Clustering, Motive, ...).
chen. Im Jahre 1954 wurde der Term „Soziales Netzwerk“von Die explorative Methode ist bei vielen Forschern, die an-
J. A. Barnes als ein feststehender Ausdruck verwendet, um wendungsorientiert arbeiten, sehr beliebt, da man mit Stan-
sich wiederholende Strukturen in verschiedenen Gruppierun- dardwerkzeugen sehr schnell und einfach zu Ergebnissen
gen zu beschreiben, zum Beispiel in Stämmen, Familien oder kommen kann. Diesen Ergebnissen haftet jedoch stets ein
auch in sozialen Kategorien. Anschein der Subjektivität an, wo man in der Wissenschaft
Seitdem ging es mit der Untersuchung von sozialen Netz- doch aber stets um Objektivierungen bemüht ist. Folglich ist
werken langsam, aber stetig, weiter. Einerseits untersuchte die Metriken-basierte Analyse nach allgemeiner Ansicht die
Harrison White mit seiner Studiengruppe an der Harvard Uni- aussagekräftigere und stärkere Methode. Für viele Standard-
versity, Department of Social Relations, dieses Themengebiet metriken gibt es heute auch schon mächtige Werkzeuge wie
auf einer sozialen Ebene, während Charles Tilly sich mit z.B. Pajek. Diese stoßen zwar an ihre Grenzen, wenn das
Repertoire der Standardmetriken zur Beantwortung der For- als direkt generierender Algorithmus, welcher sehr einfach,
schungsfragen nicht ausreicht, und erfordern dann weitreichen- und in der Praxis am weitesten verbreitet ist, jedoch die
de Programmierfähigkeiten. Dennoch hat sich die Metriken- ihm gestellte Aufgabe nur bis zu einem bestimmten Grad
basierte Methode heute für wissenschaftliche Untersuchungen erfüllt, und Zweifel an seiner Zuverlässigkeit offen lässt. Zum
weitgehend durchgesetzt, auch in Kombination mit der explo- Anderen gibt es den Markov-Ketten Monte-Carlo Algorithmus,
rativen Methode. welcher deutlich aufwändiger ist, und sich in der Praxis noch
Eine dritte, recht neue Methode ist die statistisch- nicht etablieren konnte. Er erfüllt zwar die Anforderungen an
stochastische Analyse, welche die Metriken-basierte Analyse die Zufallsnetzwerke voll, hinterlässt beim Anwender aber,
erweitert. Die Objektivität der Metriken-basierten Analyse wie viele andere Markov-Ketten-basierte Algorithmen auch,
ist nämlich an jener Stelle nicht mehr gegeben, an welcher die Frage nach der richtigen Schrittzahl, welche einerseits für
die numerischen Ergebnisse durch den Forscher interpretiert die Geschwindigkeit und andererseits für die Uniformität des
werden. Problematisch sind hier Aussagen, welche die Beson- Verfahrens, und somit auch für seine stochastische Aussage-
derheit von Mustern, bzw. deren erwartetes Auftreten subjektiv kraft von entscheidender Bedeutung ist.
bewerten. Dies wurde in einem sehr bedeutenden Artikel Eine lineare Größenordnung dieser Schrittzahl, welche für
von Watts und Strogatz 1998 erstmals eindrücklich durch die Praktikabilität des Verfahrens von entscheidender Bedeu-
die Untersuchung von Zufallsnetzwerken demonstriert [3]. In tung ist, wird bisher nur vermutet, und für den Vorfaktor
diesem Licht erscheinen z.B. auch die „Six Degrees of Separa- gibt es nur indirekte empirische Untersuchungen. Tatsächlich
tion“ weit weniger spektakulär als ursprünglich angenommen, bewiesen wurde bisher nur eine quadratische Größenordnung
da das Gegenteil in einem nicht perfekt-regulären Netzwerk abhängig von der zu generierenden Kantenzahl. Diese Si-
objektiv gesehen eine viel größere Sensation gewesen wäre. tuation führt bei uns, und möglicherweise auch bei anderen
Diese Beobachtung machten sich Forscher dann auch erst- Forschern, noch zu einer Zurückhaltung vor der Anwendung.
mals zu Nutze, um Interpretationen von Metriken zu objekti- In diesem Papier präsentieren wir unsere Idee und erste
vieren. Hierfür wird eine Anzahl vergleichbarer1 Zufallsnetz- Experimente, um die Schrittzahl in Einzelfällen exakt zu
werke generiert, und die gewünschte Metrik für diese ermittelt. bestimmen. Indem wir dies für verschieden große Netzwerke
Somit erhält man einen Anhaltspunkt, welchen Wert der einer bestimmten, sehr weit verbreiteten Klasse von Kno-
Metrik man statistisch in gleichartigen Netzwerken erwarten tengradsequenzen, den sogenannten skalenfreien Netzen [6]
kann. ermitteln, erhoffen wir uns, allgemeine und verlässliche Rück-
So wies beispielsweise Alon 2007 nach, dass bestimmte schlüsse auf die notwendige Schrittzahl für die Uniformität in
Motive in biologischen Netzen um die vielfache Standardab- dieser Klasse zu ermitteln.
weichung öfter auftauchen, als im Durchschnitt von gleichar-
tigen Zufallsnetzwerken. Erst jetzt ist also die Aussage, dass II. Z UFALLSNETZWERKE
die gemessene Ausprägung einer Metrik ungewöhnlich sei, In diesem Kapitel gehen wir im Detail auf die bereits
tatsächlich objektiv nachgewiesen. erwähnte statistisch-stochastische Untersuchungsmethode für
Netzwerke ein, und beschreiben die daraus resultierenden
C. Motivation Anforderungen an entsprechende Generierungsverfahren für
Die statistisch-stochastische metrik-basierte Untersuchungs- Zufallsnetzwerke. Danach werden die bekannten Verfahren
methode für reale Netzwerke ist eine recht junge, aber sehr erläutert, kritisch betrachtet und verglichen.
vielversprechende Methode, wie die Rückmeldungen aus der
A. Die Statistisch-Stochastische Methode im Detail
Forschergemeinschaft zeigen. So erregte damals die Arbeit von
Watts and Strogatz schon viel Aufmerksamkeit, die Ergebnisse In diesem Abschnitt wollen wir genauer auf die in Kapi-
Alons aus der Praxis wurden ebefalls renommiert publiziert. tel I-B beschriebene statistisch-stochastische metrik-basierte
Und auch wir haben für Analysen der Blogosphäre mit Hilfe Untersuchungsmethode für reale Netzwerke eingehen. Aus-
dieser Methode viel Anerkennung erhalten [4], weshalb wir gangspunkt sind hierbei zum Einen das reale Netzwerk als
diese Methode intensiv weiterverfolgen möchten. Gegenstand der Untersuchung, und zum Anderen die vom
Als kritischer Punkt hat sich hierbei jedoch die Wahl Forscher ausgewählte Metrik, über welche er Aussagen treffen
des Algorithmus zur Generierung dieser gleichartigen Zu- möchte.
fallsnetzwerke erwiesen. Die Gleichartigkeit wird zuallererst Neben der Berechnung der Metriken auf dem realen Netz-
natürlich über die Anzahl an Knoten und Kanten definiert, werk, wird diese auch mit ihren erwarteten Ausprägungen bei
nach allgemeinem Konsens aber auch über die Knotengrade gleichartigen Zufallsnetzwerken verglichen. Diese Gleichartig-
der einzelnen Knoten, welche eine vorgegebene Knotengrad- keit definiert sich über die Anzahl der Knoten und Kanten, und
sequenz für das Netzwerk zur Folge hat. Nun gibt es zwei zusätzlich auch über die Knotengradsequenz des Netzwerkes.
Algorithmen zur Generierung eines Zufallsnetzwerkes mit ei- D.h. dass zu jedem Knoten des realen Netzwerkes im Zufalls-
ner solchen vorgeschriebenen Sequenz, welche in [5] erläutert netzwerk ein Pendant mit exakt der gleichen Zahl an ein- und
und verglichen werden. Zum Einen das Konfigurationsmodell ausgehenden Kanten existiert.
Verfügt man gedanklich über eine Urne, welche alle mög-
1 mehr zur Vergleichbarkeit in den folgenden Abschnitten lichen Netzwerke enthält, die in Größe und Gradsequenz
dem realen Netzwerk entsprechen, so kann man nun eine e1
A B A B
hinreichend große Anzahl s dieser Netzwerke mit jeweils
gleicher Wahrscheinlichkeit ziehen, und erhält somit eine e2
repräsentative Teilmenge. Üblich sind hier alles zwischen 30 e1
und 1000 Ziehungen. Für jedes gezogene Netzwerk wird nun C e2 D C D
die Metrik berechnet, und für die Menge insgesamt kann man
nun die deskriptive statistische Verteilung der Ausprägung (a) (b)
ermitteln. Dies resultiert in einem Durchschnittswert mit einer Fig. 1. gültiger Kantentausch
Standardabweichung.
Für das reale Netzwerk kann man nun den absoluten Ab-
stand der Metrik zum statistischen Mittel der Zufallsnetzwerke Um dennoch einfache Graphen zu erhalten, werden in der
berechnen, und gibt diesen geteilt durch die Standardabwei- Praxis parallele Kanten und Selbst-Kanten einfach gelöscht,
chung als z-Wert an. Hat die Metrik auf dem realen Netz- was aber sowohl die Anzahl der Kanten als auch die Gradse-
werk ein z < 1 so ist die Eigenschaft im Rahmen des zu quenz des damit generierten Netzwerkes verfälscht. Dies wird
Erwartenden, weist sie allerdings ein z > 3 auf, so kann in der Praxis bei großen Netzwerken gerne als vernachlässig-
man davon ausgehen, eine Besonderheit des realen Netzwerks bar dargestellt. Zwar mag dies oftmals stimmen, dennoch gibt
im Vergleich zu gleichartigen Zufallsnetzwerken entdeckt zu es Erkenntnisse, welche Probleme bei der Uniformität des Ver-
haben. Die Interpretation der Bedeutung dieser Besonderheit fahrens nachweisen [5]. Insgesmat sind wir der Meinung, dass
ist nun natürlich wieder subjektiv, stützt sich mittlerweile das Verfahren unter strengsten wissenschaftlichen Kriterien als
aber auf schon zwei objektivierte Aussagen. Im Normalfall nicht zuverlässig betrachtet werden muss.
wird damit eine vorher entsprechend aufgestellte Hypothese Die Verbundenheit der Graphen kann in keinster Weise
überprüft. garantiert werden, aber auch der Versuch, alle nicht verbunde-
nen generierten Graphen zu verwerfen ist für fast alle real
B. Anforderungen an die Verfahren
vorkommenden Gradsequenzen hoffnungslos, wie fundierte
Ein konkretes Netzwerk, welches eine gegebene Knoten- Abschätzungen über den Anteil nicht verbundener Graphen für
gradsequenz realisiert, nennt man eine Konfiguration dieser gegebene Sequenzen zeigen [9]. Benötigt man in der Praxis
Sequenz. Nun übersteigt schon bei kleinen Sequenzen die dennoch diese Einschränkung, so ist es üblich, nur den größten
Anzahl der Konfigurationen aufgrund der kombinatorischen zusammenhängenden Teilgraphen des Netzwerkes zu nehmen.
Explosion alle Speichermöglichkeiten [7], weshalb eine ent- Eine solche giant component, welche nahe an die vorgegebene
sprechende Urne durch ein uniformes Generierungsverfahren Größe des Netzwerkes herankommt, wird es zwar meistens mit
für diese Konfigurationen simuliert werden muss; uniform hoher Wahrscheinlichkeit geben [10], das Resultat verliert aber
insofern, dass jede mögliche Konfiguration exakt die gleiche noch weiter an Zuverlässigkeit.
Wahrscheinlichkeit haben muss, durch ein solches Verfahren Von Uniformität kann man bei diesem Verfahren kaum
generiert zu werden. noch sprechen, da die generierten Netzwerke gar nicht in der
Aufgrund der Beschaffenheit fast aller realer Netzwerke vorgegebenen Menge der Konfigurationen liegen. Hier werden
kommen noch folgende Einschränkungen an die Menge der stattdessen die statistischen Werte bestimmter Metriken als
Konfigurationen hinzu. Erstens soll die Gesamtmenge aller Vergleich herangezogen, die Uniformität also rein empirisch
Konfigurationen nur einfache Graphen enthalten, d.h. sie sol- betrachtet.
len weder parallele Kanten noch Kanten zwischen ein und
demselben Knoten, welche wir hier Selbst-Kanten nennen,
D. Der MCMC-Algorithmus
enthalten. Zweitens sind oftmals auch nur zusammenhängende
Graphen gewünscht, also Graphen ohne vollständig isolier- Der Markov-Ketten Monte-Carlo Algorithmus ist ebenfalls
te Subgraphen. Diese Anforderungen sollen die statistisch- ein Verfahren für die Generierung entsprechender Konfigu-
stochastischen Werte auf Grundlage der real überhaupt nur rationen. Die Idee ist hierbei, aus einer Startkonfiguration
in Frage kommenden Netzwerke ermitteln. heraus solange zwei zufällig ausgewählte Kanten miteinan-
der zu vertauschen, bis jede Konfiguration mit der gleichen
C. Das Konfigurationsmodell Wahrscheinlichkeit erreicht wird.
Das Konfigurationsmodell ist ein sehr einfaches, direkt Als Startkonfiguration für das Verfahren nimmt man ent-
generierendes Verfahren (siehe [8] Abschnitt IV.B.1). Die Idee weder das reale Netzwerk, oder, falls nur eine Gradsequenz
besteht darin, alle Knoten zu Beginn mit der entsprechenden gegeben ist, generiert man eine Konfiguration mit dem Havel-
Anzahl an Kantenstummeln zu versehen, und danach iterativ Hakimi-Algorithmus [11]. Beim Tausch zweier zufällig aus-
jeweils zwei zufällig ausgewählte Stummel mittels einer Kante gewählter Kanten gibt es gültige und ungültige Folgekon-
miteinander zu verbinden. Dies funktioniert in linearer Zeit, figurationen. Ungültig ist ein Kantentausch dann, wenn die
generiert aber zum Einen auch nicht-einfache Graphen, und Folgekonfiguration kein einfacher Graph mehr wäre, dies lässt
kann auch die Verbundenheit des Netzwerkes nicht garantie- sich jedoch sehr leicht anhand der ausgewählten Kanten vorab
ren. überprüfen, wie in den Abbildungen 1 und 2 zu sehen ist.
e1
A B C
A e1 B e2 C e2
(a) (b)
Fig. 2. ungültiger Kantentausch wegen Schleife
Aufgrund theoretischer Gegebenheiten konvergiert dieses
Verfahren bei einer Schrittzahl q von erfolgreichen oder
versuchten Kantentauschen gegen unendlich zu einer perfekt
uniformen Generierung aller Konfigurationen. Doch genau bei
der Bestimmung dieser Schrittzahl q liegt das Problem dieses
Verfahrens, wie bei vielen anderen Markov-Ketten-Verfahren
auch. Nachgewiesen ist, dass eine Schrittzahl in der Grö-
ßenordnung von O(m2 ) für die Uniformität ausreichend ist,
jedoch gibt es keine verlässliche Aussage über den Vorfaktor. Fig. 3. Empirische Schätzung des Vorfaktors fq aus [5]
Empirische Tests legen gar eine lineare Größenordnung nahe,
und schlagen einen Vorfaktor fq von 100 dazu vor [5], [12],
also insgesamt eine Schrittzahl von q = 100·m. Wir werden in Algorithmus vor, so dass dieser möglichst uniforme Ergebnisse
Kapitel III genauer auf diese Problematik und Überlegungen liefert, aber nicht übermäßig viel Zeit braucht. Wir hinter-
zu möglichen Auswegen eingehen. fragen diesen kritisch und zeigen anhand einiger Beispiele
Vorab wollen wir noch kurz auf die Generierung von aus- Unzulänglichkeiten und mögliche Lösungswege hierfür auf.
schließlich verbundenen Graphen eingehen, welche mit dem
MCMC-Algorithmus unter Wahrung der Uniformität möglich A. Bisherige Festlegung
ist, was das Verfahren deswegen auch so attraktiv macht. Dass die Schrittzahl q für den MCMC-Algorithmus linear
Nehmen wir an, die Schrittzahl liege tatsächlich in O(m). von der Anzahl der Kanten m abhängt ist bisher wie gesagt
Man kann nun nach jedem Kantentausch überprüfen, ob die nur eine Vermutung. Um unter dieser Voraussetzung den pas-
Nachfolgekonfiguration ein verbundener Graph ist oder nicht. senden Vorfaktor fq zu ermitteln, wurde in vorangegangenen
Dies kann mittels einer einfachen Tiefensuche in m Schritten Arbeiten [5], [12] stets eine indirekte empirische Methode ver-
entschieden werden. Davon abhängig gilt der Kantentausch wendet. Das Prinzip beruht darauf, sich eine Startkonfiguration
dann entweder als gültig, oder aber man geht wieder zur ur- mit einer sehr ungewöhnlich ausgeprägten Metrik zu nehmen,
sprünglichen Konfiguration zurück und versucht erneut einen davon ausgehend wiederholt Kantentausche durchzuführen,
Kantentausch, ohne den vorangegangenen mitzuzählen. Dies und zu messen, ab welcher Schrittzahl die Metrik sich beim
führt insgesamt zu einer Laufzeit des Verfahrens in O(m2 ). erwarteten Durchschnittswert einpendelt. Hieraus wird dann
Viger und Latapy haben diese Methode weiterentwickelt, und eine ausreichende Unifomität des Verfahrens geschlussfolgert.
nachweislich eine Erhöhung um nur O(log m) für die Ver- Abbildung 3 aus [5] zeigt eine solche Bestimmung anhand
bundenheitsprüfung erreicht, so dass ihr optimierter MCMC- des Transkriptionsnetzwerkes des E.Coli-Bakteriums. Als Me-
Algorithmus verbundene Netzwerke mit einer Laufzeit in trik wurde die gefundene Anzahl des Motivs „Feed-Forward
O(m · log m) generiert. Loop“ gewählt. Man sieht recht gut, dass der Erwartungsswert
Bestünde nun Gewissheit über die für die Uniformität tat- gleichartiger Zufallsnetzwerke in diesem Beispiel schon mit
sächlich notwendige Schrittzahl, so würde dieser Algorithmus fq = 1 erreicht wird, dennoch ist es die Schlussfolgerung der
zuverlässig und schnell die gewünschten verbundenen Netz- Autoren, im allgemeinen Fall lieber fq = 100 zu wählen.
werke generieren. Tatsächlich wird dieser Algorithmus aber Das Problem dieser Art der Bestimmung sind die Aus-
bis heute in keinem der Standardwerkzeuge und -bibliotheken wahl der Metrik und einer dazugehörigen außergewöhnlichen
angeboten. Stattdessen findet man stets eine Implementierung Startkonfiguration. Nun haben schon Watts und Strogatz 1998
des Konfigurationsmpdells vor, trotz der oben beschriebenen gezeigt, dass verschiedene Metriken verschieden schnell auf
Unzulänglichkeiten. Im nächsten Kapitel werden wir unsere Kantentausche reagieren [3], eine unter allen Umständen
Ideen für eine bessere Bestimmung der Schrittzahl vorstel- „trägste“ Metrik ist jedoch nicht bekannt. Dennoch erscheint es
len, um so einen Beitrag für die Etablierung der MCMC- fragwürdig, eine besonders dynamische Metrik wie den Durch-
Algorithmen zu leisten. messer eines Netzwerkes für solch einen Test heranzuziehen,
wie in Vorarbeiten geschehen [12].
III. D IE S CHRITTZAHL DES MCMC-A LGORITHMUS Das andere Problem betrifft die Startkonfiguration. Hat das
In diesem Kapitel stellen wir den Stand der Wissenschft Transkriptionsnetzwerk zwar mit 42 Motiven einen z-Wert von
bezüglich der Bestimmung der Schrittzahl für den MCMC- ca. 10 bei der Abweichung von der erwarteten Motivanzahl,
TABLE I
so lassen sich bei der gegebenen Sequenz dennoch auch leicht
E XAKT BERECHNETE S CHRITTZAHLEN
Konfigurationen mit über 100 Motiven realisieren, was das
Konvergieren aus einer solchen Konfiguration heraus weiter Netzwerk q fq ±δ
verlangsamen würde. Auch die Größen der Netzwerke bleiben
negativ korreliert 61 ∼5 0.009
unzureichend berücksichtigt, da diese Art der Bestimmung positiv korreliert 89 ∼7 0.02
sehr zeitaufwändig ist. Das kommunizierte Ergebnis ist hier zufällig 78 ∼7 0.15
immer, dass „für eine Vielzahl verschiedener Netzwerke und Toy-Netzwerk 21 ∼2 0
verschiedener Metriken sich fq = 100 immer als ausreichend
groß herausgestellt hat“.
Wir sind mit diesem Ergebnis bezüglich der Zuverlässigkeit benutzten „toy network“, welches über eine sehr spezielle,
des Verfahrens nicht zufrieden, und die Zurückhaltung bei für die Realität untypische Sequenz verfügt, aber nur 91
der Akzeptanz dieses Verfahrens scheint dies zu bestätigen. Konfigurationen erlaubt. Zum anderen haben wir uns, unserem
Wir stellen in den folgenden Abschnitten unseren alternative Interesse an real vorkommenden Sequenzen folgend, eine
Ansatz für die Bestimmung der Schrittzahl q vor. kleine heterogene Powerlaw-Verteilung (siehe [8] Abschnitt
III.C.1) mit 12 Kanten generiert, wie sie in einem skalenfreien
B. Die Markov-Kette Netzwerk vorkommen würde. Wir haben α = 1, 7 gewählt
Zu Beginn unserer Überlegungen beschäftigen wir uns mit und damit die Knotengrade (3, 2, 2, 1, 1, 1, 1, 1) für 8 Knoten
der dem MCMC-Algorithmus zu Grunde liegenden Markov- erhalten. Um eine Gradsequenz für einen gerichteten Graphen
Kette. Jede mögliche Konfiguration einer Gradsequenz ist mit Ein- und Ausgangsgraden zu erhalten, haben wir diese
ein Knoten der Markov-Kette, den wir zur besseren Unter- einmal positiv, einmal negativ, und einmal nicht korreliert, also
scheidung Konfigurationsknoten nennen werden. Jeder gültige zufällig, auf die acht Knoten verteilt.
Kantentausch führt zu einem anderen Konfigurationsknoten, Diese vier Sequenzen haben wir mit dem Havel-Hakimi-
und die Umkehroperation auch immer wieder zurück, so dass Algorithmus in einem Netzwerk realisiert, von diesen Kon-
immer bidirektionale Verbindungen zwischen zwei Konfigu- figurationen aus jeweils den Zustandsraum der Markov-Kette
rationsknoten bestehen. Alle ungültigen Kantentausche zählen durch Verfolgung aller jeweils möglichen 66 Kantenpaare voll-
ebenfalls als Schritt des Algorithmus, da sie aber zu keiner ständig generiert und als Netzwerk gespeichert. Die Markov-
neuen Konfiguration führen, werden sie deshalb in einer Kette des Toy-Netzwerks verfügt wie bekannt über 91 Kon-
Selbst-Kante mit entsprechender Gewichtung zusammenge- figurationsknoten, die Markov-Ketten der drei skalenfreien
fasst. Netzwerke über 90.000 bis 120.000 Konfigurationsknoten.
2
Es gibt insgesamt m 2+m ungeordnete Kantenpaare, so dass Tabelle I listet die errechneten Schrittzahlen q für die vier
jeder Konfigurationsknoten diesen Wert als Ein- und Aus- Beispielnetzwerke auf. Abbruchbedingung war hier, dass sich
gangsgrad besitzt. Da auch die Verbundenheit der Markov- die Werte nicht mehr ändern, was bei der 32-Bit-Darstellung
Kette bewiesen ist, führt dies theoretisch zu einer perfek- schon vor Erreichen der Gleichverteilung eintreten kann. Der
ten Uniformität. Entscheidend hierfür ist in der Praxis aber δ-Wert gibt hierzu die maximale Abweichung eines Konfigu-
die notwendige Schrittzahl, bis zum sogenannten Mixing der rationsknotens vom Wert 1 an. Unter Annahme einer von m
Markov-Kette. linear abhängigen Schrittzahl des MCMC-Algorithmus würde
der entsprechend angegebene Vorfaktor fq gelten.
C. Exakte Berechnung im Einzelfall In allen Fällen liegt fq weit unter 100, aber auch höher als
Für gegebene Gradsequenzen und sehr kleine Netzwerke 1, wie es in Abbildung 3 möglicherweise suggeriert wurde.
lässt sich die Markov-Kette mit normaler Hardware noch Dies sind aber Einzelfallbetrachtungen, aus denen man noch
vollständig erzeugen. Verfügt man über diese Markov-Kette, keine Verallgemeinerungen folgern kann.
so kann man die für deren Mixing notwendige Schrittzahl
mit einer Variante des einfachen ungedämpften PageRank- D. Wege zur Verallgemeinerung
Algorithmus [13] exakt berechnen. Hierfür wird initial nicht Die exakte Berechnung der Schrittweite ist schon bei klei-
jedem Knoten der Wert 1 gegeben, sondern der Startkonfi- nen Werten von m aufgrund der exponentiell steigenden
gurationsknoten erhält den Wert m, und alle anderen Konfi- Anzahl an Konfigurationen unpraktikabel. Um mit dieser
gurationsknoten den Wert 0. Nun werden soviele Iterationen Methode dennoch verallgemeinerbare Aussagen, zumindest
q des ungedämpften PageRank-Algorithmus durchgeführt, bis für bestimmte Klassen von Netzwerken, wie z.B. die ska-
der Wert aller Knoten 1 ± δ beträgt. lenfreien Netze, treffen zu können, ist noch ein weiterer
Die Werte entsprechen der Wahrscheinlichkeit geteilt durch Schritt notwendig. Mit einem Verständnis für die Struktur der
m, nach dem jeweiligen Schritt des MCMC-Algorithmus bei zugrundeliegenden Markov-Ketten ließe sich die Schrittzahl
dieser Konfiguration zu sein. Der Wert δ gibt die maximal für das Mixing dieser Ketten über das modifizierte PageRank-
auftretende bzw. tolerierte Abweichung einer Konfiguration Verfahren direkt abschätzen und simulieren, anstatt sie indirekt
von der geforderten Wahrscheinlichkeit an. über das beschriebene empirische Verfahren zu bestimmen.
Wir untersuchen dies für vier Gradsequenzen mit 12 Kanten. Hierbei indentifizieren wir 3 wichtige Punkte, welche für die
Zum Einen die des zur Messung der Uniformität in [5] Geschwindigkeit des Kovergieren des PageRank-Verfahrens
von entscheidender Bedeutung sind.
1) die Anzahl der externen Verbindungen eines Konfigura-
tionsknotens, d.h. die Anzahl der Nachbarkonfiguratio-
nen und deren Verhältnis zum Gewicht der Selbst-Kante
2) den Clustering-Koeffizienten der Markov-Kette
3) den Durchmesser der Markov-Kette
Wären diese drei Ausprägungen abhängig von der zu
Grunde liegenden Gradsequenz abschätzbar, so ließe sich
für eine Klasse von Gradsequenzen ein Modell der Markov-
Kette aufstellen, und anhand von Simulationen auf verschieden
großen Instanzen dieses Modells die notwendige Schrittzahl
abschätzen oder gar ohne Simulation direkt berechnen.
Aus unseren bisherigen Erkenntnissen können wir bereits
erste Hypothesen aufstellen, deren genauere Untersuchung
unsere zukünftige Arbeit sein wird.
Fig. 4. Gradverteilung in der Markov-Kette des nicht-korrelierten skalen-
Die Topologie der in Abschnitt III-C untersuchten Markov- freien Gradsequenz
Ketten der skalenfreien Netze bilden ein mehrdimensionales
relativ regelmäßiges Gitter, welches entlang der Dimensionen
rundum verbunden ist, ähnlich wie die Oberfläche einer Kugel
in zweidimensionaler Sicht. Dies ist offensichlich im allgemei- reduziert werden könnte. Wir werden versuchen, die dafür not-
nen Fall so, bedarf jedoch noch eines Nachweises. Definiert wendigen Kenngrößen in Zukunft in ausgiebigen Simulationen
wird diese regelmäßige Struktur durch die oben genannten 3 abschätzen zu können, und damit eine für jede Netzwerkgröße
Eigenschaften. dieser Klasse sichere und vor allem effiziente Wahl von q
Beispielsweise zeigt Abbildung 4 die Verteilung der ex- ermöglichen zu können.
ternen Verbindungen der Konfigurationsknoten der Markov- R EFERENCES
Kette der nicht-korrelierten skalenfreien Gradsequenz, welche
[1] S. Wasserman, K. Faust, and D. Iacobucci, Social Network Analysis :
eine nur geringe Schwankung um den Wert 32 aufweist. Methods and Applications (Structural Analysis in the Social Sciences).
Die Anzahl ungültiger Kantentausche ließe sich allgemein Cambridge University Press, 1994.
gut aus der Sequenz abschätzen, da Kantenpaare, welche [2] L. C. Freeman, The Development of Social Network Analysis: A Study
in the Sociology of Science. Empirical Press, 2004.
nur 3 Knoten involvieren, nie getauscht werden können. [3] D. Watts and S. Strogatz, “Collective dynamics of small-world net-
Der theoretisch maximal mögliche Durchmesser von m − 1 works,” Nature, no. 393, pp. 440–442, 1998.
scheint von den skalenfreien Netzen voll ausgereizt zu werden, [4] D. Obradovic and S. Baumann, “A journey to the core of the blogos-
phere,” in Proceedings of the International Conference on Advances in
unsere Beispielsequenzen hatten hier alle den Wert 10. Der Social Network Analysis and Mining (ASONAM 2009). IEEE, 2009,
Clustering-Koeffizient ist mit ca. 0, 1 vergleichsweise hoch, pp. 1–6, best paper award.
was durch den hohen Durchmesser bedingt ist, da benachbarte [5] R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, and U. Alon,
“On the uniform generation of random graphs with prescribed degree
Konfigurationen viele Nachbarn gemeinsam haben. sequences,” Arxiv preprint cond-mat/0312028, 2003.
Diese beiden Metriken lassen sich, die gewisse Regelmäßig- [6] A. L. Barabasi and R. Albert, “Emergence of scaling in random
keit vorausgesetzt, durch Stichproben-Generierunge einzelner networks,” Science, vol. 286, pp. 509–512, 1999.
[7] T. Snijders, “Enumeration and simulation methods for 0-1 matrices with
Konfigurationen und deren Nachbarschaft ermitteln und statis- given marginals,” Psychometrika, vol. 56, no. 3, pp. 397–417, September
tisch abschätzen. Dies wäre in vertretbarer Zeit berechenbar, 1991.
und würde ebenfalls eine Abschätzung erlauben, und somit [8] M. E. J. Newman, “The structure and function of complex networks,”
SIAM Review, vol. 45, pp. 167–256, 2003.
eine empirische Ermittlung der notwendigen Schrittzahl auf [9] M. Molloy and B. Reed, “A critical point for random graphs with a
dem Modell erlauben. given degree sequence,” Random Structures and Algorithms, vol. 6, pp.
161–179, 1995.
[10] ——, “The size of the giant component of a random graph with a given
IV. Z USAMMENFASSUNG degree sequence,” vol. 7, p. 295–305, November 1998.
[11] P. L. Erdős, I. Miklós, and Z. Toroczkai, “A simple Havel-Hakimi type
In diesem Papier haben wir den Stand der Wissenschaft algorithm to realize graphical degree sequences of directed graphs,”
bezüglich der Evaluationsmethoden von konkreten realen Electronic Journal of Combinatorics, vol. 17, no. 1, p. R66, 2010.
Netzwerken zusammengefasst, und die unserer Meinung nach [12] F. Viger and M. Latapy, “Efficient and simple generation of random sim-
ple connected graphs with prescribed degree sequence.” in Proceedings
vorzuziehende Methode, der Evaluation mittels gleichartiger of the 11th international conference on Computing and Combinatorics,
Zufallsnetzwerke kritisch analysiert. Die aufgezeigten Proble- ser. Lecture Notes in Computer Science, L. Wang, Ed., vol. 3595.
me bei der Zuverlässigkeit der gängigen Methoden wurden be- Springer, 2005, pp. 440–449.
[13] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation
wertet, und für das unserer Meinung nach überlegene MCMC- ranking: Bringing order to the web,” Stanford University,” Technical
Verfahren haben wir einen Ansatz vorgestellt, mit welchem Report, 1998.
das letzte offene Problem, der zu wählenden Schrittzahl q
zumindest für bestimmte Klassen von Netzwerken deutlich