- Die Analyse von Netzwerken hat in der Soziologie seit dem 20. Jahrhundert einen hohen Stellenwert, ist aber auch für andere Disziplinen interessant. Zum Beispiel bei der Untersuchung von neuronale Netzen oder DNA-Transkriptionen in der Biologie. Für die Evaluation von Mustern gibt es verschiedene Methoden, wobei wir in dieser Arbeit den Fokus auf den statistischen Vergleich des realen Netzwerks mit gleichartigen Zufallsnetzwerken legen, da diese in besonderem Maße objetive Aussagen liefern kann. Für diese Methode existieren zwei Verfahren mit verschiedenen Unzulänglichkeiten, welche beide nicht in allen Fällen zuverlässig machen. Für das Markov-Ketten Monte-Carlo Verfahren versuchen wir, das offene Problem einer effizienten, aber auch zuverlässigen Schrittzahl mit einem neuen Ansatz anzugehen. Das Idee besteht darin, eine möglichst exakte Berechnung dieser Schrittzahl für bestimmte KLassen von Netzwerken über ein Modell der Markov-Kette zu erreichen. Sollte uns das in unserer zukünftigen Arbeit fundiert gelingen, wäre dies der bisherigen empirischen Methode deutlich überlegen.
In diesem Papier beschäftigen wir uns mit der Analyse
von Netzwerkstrukturen, welche theoretisch stark in der
Graphentheorie der Mathematik verwurzelt ist, praktisch aber vor
allem durch die Untersuchung von sozialen Netzwerken
vorangetrieben wird [
Ende der 1930er Jahre tauchte bei John Moreno erstmals das Konzept des Soziogramms auf, mit dem er soziale Beziehungen formalisierte, um sie danach methodisch zu untersuchen. Im Jahre 1954 wurde der Term „Soziales Netzwerk“von J. A. Barnes als ein feststehender Ausdruck verwendet, um sich wiederholende Strukturen in verschiedenen Gruppierungen zu beschreiben, zum Beispiel in Stämmen, Familien oder auch in sozialen Kategorien.
Seitdem ging es mit der Untersuchung von sozialen Netzwerken langsam, aber stetig, weiter. Einerseits untersuchte Harrison White mit seiner Studiengruppe an der Harvard University, Department of Social Relations, dieses Themengebiet auf einer sozialen Ebene, während Charles Tilly sich mit sozialen Bewegungen und politischen Netzwerken beschäftigte. Besondere Erwähnung verdient insbesondere Stanley Milgram, der mit der These des Kleinen-Welt-Phänomens die Untersuchung der sozialen Netzwerke vorantrieb und durch die These, dass in den USA jeder Mensch mit jedem anderen über durchschnittlich sechs Verbindungen bekannt sei, großes Interesse erweckte, auch wenn dieses Experiment methodisch stark umstritten ist.
Durch Duncan J. Watts und Steven H. Strogatz wurde
das Kleine-Welt-Phänomen 1998 weiter untersucht [
Bei der Analyse von realen Netzwerken sind zwei grundlegende Methoden stark verbreitet.
Zum Einen die explorative Analyse, bei welcher der Forscher eine graphische Darstellung des Netzwerks interaktiv durchsieht, oder spezielle Layouts betrachtet, um auffällige Muster oder Eigenschaften zu entdecken. Diese Entdeckungen sind dann das Ergebnis der Analyse. Hierfür existieren eine Vielzahl von Tools wie bspw. GUESS.
se, bei welcher Metriken auf dem Netzwerk (z.B. Dichte, Durchmesser, ...) oder Metriken für einzelne Knoten (z.B. Zentralität, Clustering-Koeffizient, ...) im Durchschnitt oder in ihrer Verteilung betrachtet werden. Hier können aber auch Algorithmen zur Suche bestimmter quantifizierbarer Muster zum Einsatz kommen (z.B. Clustering, Motive, ...).
Die explorative Methode ist bei vielen Forschern, die anwendungsorientiert arbeiten, sehr beliebt, da man mit Standardwerkzeugen sehr schnell und einfach zu Ergebnissen kommen kann. Diesen Ergebnissen haftet jedoch stets ein Anschein der Subjektivität an, wo man in der Wissenschaft doch aber stets um Objektivierungen bemüht ist. Folglich ist die Metriken-basierte Analyse nach allgemeiner Ansicht die aussagekräftigere und stärkere Methode. Für viele Standardmetriken gibt es heute auch schon mächtige Werkzeuge wie z.B. Pajek. Diese stoßen zwar an ihre Grenzen, wenn das Repertoire der Standardmetriken zur Beantwortung der Forschungsfragen nicht ausreicht, und erfordern dann weitreichende Programmierfähigkeiten. Dennoch hat sich die Metrikenbasierte Methode heute für wissenschaftliche Untersuchungen weitgehend durchgesetzt, auch in Kombination mit der explorativen Methode.
Eine dritte, recht neue Methode ist die
statistischstochastische Analyse, welche die Metriken-basierte Analyse
erweitert. Die Objektivität der Metriken-basierten Analyse
ist nämlich an jener Stelle nicht mehr gegeben, an welcher
die numerischen Ergebnisse durch den Forscher interpretiert
werden. Problematisch sind hier Aussagen, welche die
Besonderheit von Mustern, bzw. deren erwartetes Auftreten subjektiv
bewerten. Dies wurde in einem sehr bedeutenden Artikel
von Watts und Strogatz 1998 erstmals eindrücklich durch
die Untersuchung von Zufallsnetzwerken demonstriert [
Diese Beobachtung machten sich Forscher dann auch erstmals zu Nutze, um Interpretationen von Metriken zu objektivieren. Hierfür wird eine Anzahl vergleichbarer1 Zufallsnetzwerke generiert, und die gewünschte Metrik für diese ermittelt. Somit erhält man einen Anhaltspunkt, welchen Wert der Metrik man statistisch in gleichartigen Netzwerken erwarten kann.
So wies beispielsweise Alon 2007 nach, dass bestimmte Motive in biologischen Netzen um die vielfache Standardabweichung öfter auftauchen, als im Durchschnitt von gleichartigen Zufallsnetzwerken. Erst jetzt ist also die Aussage, dass die gemessene Ausprägung einer Metrik ungewöhnlich sei, tatsächlich objektiv nachgewiesen.
Die statistisch-stochastische metrik-basierte
Untersuchungsmethode für reale Netzwerke ist eine recht junge, aber sehr
vielversprechende Methode, wie die Rückmeldungen aus der
Forschergemeinschaft zeigen. So erregte damals die Arbeit von
Watts and Strogatz schon viel Aufmerksamkeit, die Ergebnisse
Alons aus der Praxis wurden ebefalls renommiert publiziert.
Und auch wir haben für Analysen der Blogosphäre mit Hilfe
dieser Methode viel Anerkennung erhalten [
Als kritischer Punkt hat sich hierbei jedoch die Wahl
des Algorithmus zur Generierung dieser gleichartigen
Zufallsnetzwerke erwiesen. Die Gleichartigkeit wird zuallererst
natürlich über die Anzahl an Knoten und Kanten definiert,
nach allgemeinem Konsens aber auch über die Knotengrade
der einzelnen Knoten, welche eine vorgegebene
Knotengradsequenz für das Netzwerk zur Folge hat. Nun gibt es zwei
Algorithmen zur Generierung eines Zufallsnetzwerkes mit
einer solchen vorgeschriebenen Sequenz, welche in [
Eine lineare Größenordnung dieser Schrittzahl, welche für die Praktikabilität des Verfahrens von entscheidender Bedeutung ist, wird bisher nur vermutet, und für den Vorfaktor gibt es nur indirekte empirische Untersuchungen. Tatsächlich bewiesen wurde bisher nur eine quadratische Größenordnung abhängig von der zu generierenden Kantenzahl. Diese Situation führt bei uns, und möglicherweise auch bei anderen Forschern, noch zu einer Zurückhaltung vor der Anwendung.
In diesem Papier präsentieren wir unsere Idee und erste
Experimente, um die Schrittzahl in Einzelfällen exakt zu
bestimmen. Indem wir dies für verschieden große Netzwerke
einer bestimmten, sehr weit verbreiteten Klasse von
Knotengradsequenzen, den sogenannten skalenfreien Netzen [
In diesem Kapitel gehen wir im Detail auf die bereits erwähnte statistisch-stochastische Untersuchungsmethode für Netzwerke ein, und beschreiben die daraus resultierenden Anforderungen an entsprechende Generierungsverfahren für Zufallsnetzwerke. Danach werden die bekannten Verfahren erläutert, kritisch betrachtet und verglichen.
In diesem Abschnitt wollen wir genauer auf die in Kapitel I-B beschriebene statistisch-stochastische metrik-basierte Untersuchungsmethode für reale Netzwerke eingehen. Ausgangspunkt sind hierbei zum Einen das reale Netzwerk als Gegenstand der Untersuchung, und zum Anderen die vom Forscher ausgewählte Metrik, über welche er Aussagen treffen möchte.
Neben der Berechnung der Metriken auf dem realen Netzwerk, wird diese auch mit ihren erwarteten Ausprägungen bei gleichartigen Zufallsnetzwerken verglichen. Diese Gleichartigkeit definiert sich über die Anzahl der Knoten und Kanten, und zusätzlich auch über die Knotengradsequenz des Netzwerkes. D.h. dass zu jedem Knoten des realen Netzwerkes im Zufallsnetzwerk ein Pendant mit exakt der gleichen Zahl an ein- und ausgehenden Kanten existiert.
Verfügt man gedanklich über eine Urne, welche alle möglichen Netzwerke enthält, die in Größe und Gradsequenz dem realen Netzwerk entsprechen, so kann man nun eine hinreichend große Anzahl s dieser Netzwerke mit jeweils gleicher Wahrscheinlichkeit ziehen, und erhält somit eine repräsentative Teilmenge. Üblich sind hier alles zwischen 30 und 1000 Ziehungen. Für jedes gezogene Netzwerk wird nun die Metrik berechnet, und für die Menge insgesamt kann man nun die deskriptive statistische Verteilung der Ausprägung ermitteln. Dies resultiert in einem Durchschnittswert mit einer Standardabweichung.
Für das reale Netzwerk kann man nun den absoluten Abstand der Metrik zum statistischen Mittel der Zufallsnetzwerke berechnen, und gibt diesen geteilt durch die Standardabweichung als z-Wert an. Hat die Metrik auf dem realen Netzwerk ein z < 1 so ist die Eigenschaft im Rahmen des zu Erwartenden, weist sie allerdings ein z > 3 auf, so kann man davon ausgehen, eine Besonderheit des realen Netzwerks im Vergleich zu gleichartigen Zufallsnetzwerken entdeckt zu haben. Die Interpretation der Bedeutung dieser Besonderheit ist nun natürlich wieder subjektiv, stützt sich mittlerweile aber auf schon zwei objektivierte Aussagen. Im Normalfall wird damit eine vorher entsprechend aufgestellte Hypothese überprüft.
Ein konkretes Netzwerk, welches eine gegebene
Knotengradsequenz realisiert, nennt man eine Konfiguration dieser
Sequenz. Nun übersteigt schon bei kleinen Sequenzen die
Anzahl der Konfigurationen aufgrund der kombinatorischen
Explosion alle Speichermöglichkeiten [
Aufgrund der Beschaffenheit fast aller realer Netzwerke kommen noch folgende Einschränkungen an die Menge der Konfigurationen hinzu. Erstens soll die Gesamtmenge aller Konfigurationen nur einfache Graphen enthalten, d.h. sie sollen weder parallele Kanten noch Kanten zwischen ein und demselben Knoten, welche wir hier Selbst-Kanten nennen, enthalten. Zweitens sind oftmals auch nur zusammenhängende Graphen gewünscht, also Graphen ohne vollständig isolierte Subgraphen. Diese Anforderungen sollen die statistischstochastischen Werte auf Grundlage der real überhaupt nur in Frage kommenden Netzwerke ermitteln.
Das Konfigurationsmodell ist ein sehr einfaches, direkt
generierendes Verfahren (siehe [
A C
Um dennoch einfache Graphen zu erhalten, werden in der
Praxis parallele Kanten und Selbst-Kanten einfach gelöscht,
was aber sowohl die Anzahl der Kanten als auch die
Gradsequenz des damit generierten Netzwerkes verfälscht. Dies wird
in der Praxis bei großen Netzwerken gerne als
vernachlässigbar dargestellt. Zwar mag dies oftmals stimmen, dennoch gibt
es Erkenntnisse, welche Probleme bei der Uniformität des
Verfahrens nachweisen [
Die Verbundenheit der Graphen kann in keinster Weise
garantiert werden, aber auch der Versuch, alle nicht
verbundenen generierten Graphen zu verwerfen ist für fast alle real
vorkommenden Gradsequenzen hoffnungslos, wie fundierte
Abschätzungen über den Anteil nicht verbundener Graphen für
gegebene Sequenzen zeigen [
Von Uniformität kann man bei diesem Verfahren kaum noch sprechen, da die generierten Netzwerke gar nicht in der vorgegebenen Menge der Konfigurationen liegen. Hier werden stattdessen die statistischen Werte bestimmter Metriken als Vergleich herangezogen, die Uniformität also rein empirisch betrachtet.
Der Markov-Ketten Monte-Carlo Algorithmus ist ebenfalls ein Verfahren für die Generierung entsprechender Konfigurationen. Die Idee ist hierbei, aus einer Startkonfiguration heraus solange zwei zufällig ausgewählte Kanten miteinander zu vertauschen, bis jede Konfiguration mit der gleichen Wahrscheinlichkeit erreicht wird.
Als Startkonfiguration für das Verfahren nimmt man
entweder das reale Netzwerk, oder, falls nur eine Gradsequenz
gegeben ist, generiert man eine Konfiguration mit dem
HavelHakimi-Algorithmus [
C B B
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.
Empirische Tests legen gar eine lineare Größenordnung nahe,
und schlagen einen Vorfaktor fq von 100 dazu vor [
Vorab wollen wir noch kurz auf die Generierung von ausschließlich verbundenen Graphen eingehen, welche mit dem MCMC-Algorithmus unter Wahrung der Uniformität möglich ist, was das Verfahren deswegen auch so attraktiv macht. Nehmen wir an, die Schrittzahl liege tatsächlich in O(m). Man kann nun nach jedem Kantentausch überprüfen, ob die Nachfolgekonfiguration ein verbundener Graph ist oder nicht. Dies kann mittels einer einfachen Tiefensuche in m Schritten entschieden werden. Davon abhängig gilt der Kantentausch dann entweder als gültig, oder aber man geht wieder zur ursprünglichen Konfiguration zurück und versucht erneut einen Kantentausch, ohne den vorangegangenen mitzuzählen. Dies führt insgesamt zu einer Laufzeit des Verfahrens in O(m2). Viger und Latapy haben diese Methode weiterentwickelt, und nachweislich eine Erhöhung um nur O(log m) für die Verbundenheitsprüfung erreicht, so dass ihr optimierter MCMCAlgorithmus verbundene Netzwerke mit einer Laufzeit in O(m log m) generiert.
Bestünde nun Gewissheit über die für die Uniformität tatsächlich notwendige Schrittzahl, so würde dieser Algorithmus zuverlässig und schnell die gewünschten verbundenen Netzwerke generieren. Tatsächlich wird dieser Algorithmus aber bis heute in keinem der Standardwerkzeuge und -bibliotheken angeboten. Stattdessen findet man stets eine Implementierung des Konfigurationsmpdells vor, trotz der oben beschriebenen Unzulänglichkeiten. Im nächsten Kapitel werden wir unsere Ideen für eine bessere Bestimmung der Schrittzahl vorstellen, um so einen Beitrag für die Etablierung der MCMCAlgorithmen zu leisten.
Algorithmus vor, so dass dieser möglichst uniforme Ergebnisse liefert, aber nicht übermäßig viel Zeit braucht. Wir hinterfragen diesen kritisch und zeigen anhand einiger Beispiele Unzulänglichkeiten und mögliche Lösungswege hierfür auf.
Dass die Schrittzahl q für den MCMC-Algorithmus linear
von der Anzahl der Kanten m abhängt ist bisher wie gesagt
nur eine Vermutung. Um unter dieser Voraussetzung den
passenden Vorfaktor fq zu ermitteln, wurde in vorangegangenen
Arbeiten [
Abbildung 3 aus [
Das Problem dieser Art der Bestimmung sind die
Auswahl der Metrik und einer dazugehörigen außergewöhnlichen
Startkonfiguration. Nun haben schon Watts und Strogatz 1998
gezeigt, dass verschiedene Metriken verschieden schnell auf
Kantentausche reagieren [
Das andere Problem betrifft die Startkonfiguration. Hat das Transkriptionsnetzwerk zwar mit 42 Motiven einen z-Wert von ca. 10 bei der Abweichung von der erwarteten Motivanzahl, so lassen sich bei der gegebenen Sequenz dennoch auch leicht Konfigurationen mit über 100 Motiven realisieren, was das Konvergieren aus einer solchen Konfiguration heraus weiter verlangsamen würde. Auch die Größen der Netzwerke bleiben unzureichend berücksichtigt, da diese Art der Bestimmung sehr zeitaufwändig ist. Das kommunizierte Ergebnis ist hier immer, dass „für eine Vielzahl verschiedener Netzwerke und verschiedener Metriken sich fq = 100 immer als ausreichend groß herausgestellt hat“.
Wir sind mit diesem Ergebnis bezüglich der Zuverlässigkeit des Verfahrens nicht zufrieden, und die Zurückhaltung bei der Akzeptanz dieses Verfahrens scheint dies zu bestätigen. Wir stellen in den folgenden Abschnitten unseren alternative Ansatz für die Bestimmung der Schrittzahl q vor.
Zu Beginn unserer Überlegungen beschäftigen wir uns mit der dem MCMC-Algorithmus zu Grunde liegenden MarkovKette. Jede mögliche Konfiguration einer Gradsequenz ist ein Knoten der Markov-Kette, den wir zur besseren Unterscheidung Konfigurationsknoten nennen werden. Jeder gültige Kantentausch führt zu einem anderen Konfigurationsknoten, und die Umkehroperation auch immer wieder zurück, so dass immer bidirektionale Verbindungen zwischen zwei Konfigurationsknoten bestehen. Alle ungültigen Kantentausche zählen ebenfalls als Schritt des Algorithmus, da sie aber zu keiner neuen Konfiguration führen, werden sie deshalb in einer Selbst-Kante mit entsprechender Gewichtung zusammengefasst.
Es gibt insgesamt m2+m ungeordnete Kantenpaare, so dass 2 jeder Konfigurationsknoten diesen Wert als Ein- und Ausgangsgrad besitzt. Da auch die Verbundenheit der MarkovKette bewiesen ist, führt dies theoretisch zu einer perfekten Uniformität. Entscheidend hierfür ist in der Praxis aber die notwendige Schrittzahl, bis zum sogenannten Mixing der Markov-Kette.
Für gegebene Gradsequenzen und sehr kleine Netzwerke
lässt sich die Markov-Kette mit normaler Hardware noch
vollständig erzeugen. Verfügt man über diese Markov-Kette,
so kann man die für deren Mixing notwendige Schrittzahl
mit einer Variante des einfachen ungedämpften
PageRankAlgorithmus [
Die Werte entsprechen der Wahrscheinlichkeit geteilt durch m, nach dem jeweiligen Schritt des MCMC-Algorithmus bei dieser Konfiguration zu sein. Der Wert gibt die maximal auftretende bzw. tolerierte Abweichung einer Konfiguration von der geforderten Wahrscheinlichkeit an.
Wir untersuchen dies für vier Gradsequenzen mit 12 Kanten.
Zum Einen die des zur Messung der Uniformität in [
Diese vier Sequenzen haben wir mit dem Havel-HakimiAlgorithmus in einem Netzwerk realisiert, von diesen Konfigurationen aus jeweils den Zustandsraum der Markov-Kette durch Verfolgung aller jeweils möglichen 66 Kantenpaare vollständig generiert und als Netzwerk gespeichert. Die MarkovKette des Toy-Netzwerks verfügt wie bekannt über 91 Konfigurationsknoten, die Markov-Ketten der drei skalenfreien Netzwerke über 90.000 bis 120.000 Konfigurationsknoten.
Tabelle I listet die errechneten Schrittzahlen q für die vier Beispielnetzwerke auf. Abbruchbedingung war hier, dass sich die Werte nicht mehr ändern, was bei der 32-Bit-Darstellung schon vor Erreichen der Gleichverteilung eintreten kann. Der -Wert gibt hierzu die maximale Abweichung eines Konfigurationsknotens vom Wert 1 an. Unter Annahme einer von m linear abhängigen Schrittzahl des MCMC-Algorithmus würde der entsprechend angegebene Vorfaktor fq gelten.
In allen Fällen liegt fq weit unter 100, aber auch höher als 1, wie es in Abbildung 3 möglicherweise suggeriert wurde. Dies sind aber Einzelfallbetrachtungen, aus denen man noch keine Verallgemeinerungen folgern kann.
Die exakte Berechnung der Schrittweite ist schon bei kleinen Werten von m aufgrund der exponentiell steigenden Anzahl an Konfigurationen unpraktikabel. Um mit dieser Methode dennoch verallgemeinerbare Aussagen, zumindest für bestimmte Klassen von Netzwerken, wie z.B. die skalenfreien Netze, treffen zu können, ist noch ein weiterer Schritt notwendig. Mit einem Verständnis für die Struktur der zugrundeliegenden Markov-Ketten ließe sich die Schrittzahl für das Mixing dieser Ketten über das modifizierte PageRankVerfahren direkt abschätzen und simulieren, anstatt sie indirekt über das beschriebene empirische Verfahren zu bestimmen.
Hierbei indentifizieren wir 3 wichtige Punkte, welche für die Geschwindigkeit des Kovergieren des PageRank-Verfahrens
In diesem Papier haben wir den Stand der Wissenschaft bezüglich der Evaluationsmethoden von konkreten realen Netzwerken zusammengefasst, und die unserer Meinung nach vorzuziehende Methode, der Evaluation mittels gleichartiger Zufallsnetzwerke kritisch analysiert. Die aufgezeigten Probleme bei der Zuverlässigkeit der gängigen Methoden wurden bewertet, und für das unserer Meinung nach überlegene MCMCVerfahren haben wir einen Ansatz vorgestellt, mit welchem das letzte offene Problem, der zu wählenden Schrittzahl q zumindest für bestimmte Klassen von Netzwerken deutlich reduziert werden könnte. Wir werden versuchen, die dafür notwendigen Kenngrößen in Zukunft in ausgiebigen Simulationen abschätzen zu können, und damit eine für jede Netzwerkgröße dieser Klasse sichere und vor allem effiziente Wahl von q ermöglichen zu können.