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