Modelle von Zufallsgraphen für echte Computernetzwerke

Ich interessiere mich für Modelle von Zufallsgraphen, die den Graphen realer Computernetzwerke ähnlich sind. Ich bin nicht sicher, ob das allgemein gut untersuchte -Modell ( n Eckpunkte, jede mögliche Kante wird mit der Wahrscheinlichkeit p ausgewählt ) für die Untersuchung realer Computernetzwerke geeignet ist (oder?).$G(n,p)$$n$$p$

Welche Modelle von Zufallsgraphen sind nützlich, um die in der Praxis auftretenden Computernetzwerke zu verstehen?

Welche anderen Modelle endlicher Zufallsgraphen (die nicht dem -Modell entsprechen) wurden in der Literatur allgemein untersucht? (Eine ideale Antwort wäre ein Hinweis auf eine Umfrage für untersuchte Modelle endlicher Zufallsgraphen.)$G(n,p)$

In den letzten Jahren hat die Untersuchung von Zufallsgraphen mit "natürlichen" strukturellen Einschränkungen an Bedeutung gewonnen. Zum Beispiel kann man einen ebenen Graphen betrachten, der aus der Klasse aller ebenen Graphen mit Eckpunkten stammt, und untersuchen, wie er sich verhält$n$. Im Gegensatz zu den Erdős-Rényi-Zufallsgraphen oder ähnlichen Modellen sind die Kanten in diesen Graphen stark abhängig. Eine der Pseudomotivationen für die Untersuchung solcher Verteilungen ist die Analyse von Netzwerkmodellen mit sehr begrenzter Unabhängigkeit zwischen Kanten.$n \rightarrow \infty$

Vielleicht scheint dieses Ziel derzeit jedoch ziemlich weit entfernt zu sein, da die eingeschränkte Unabhängigkeit die Analyse der Eigenschaften solcher Diagramme erheblich erschwert. In der Tat, einige grundlegende Fragen, die für G sehr einfach beantwortet werden können (, wie die Verteilung der Gradfolge, erst in jüngster Zeit für planare Zufallsgraphen gelöst worden.$G(n, p)$

Für eine endgültige Bezugnahme siehe die Papiere von Konstantinos Panagiotou und die darin enthaltenen Zitate. Der Einfachheit halber finden Sie hier eine kleine Auswahl relevanter Artikel:

• Zur Gradverteilung von planaren Zufallsgraphen . Konstantinos Panagiotou und Angelika Steger . Erscheint in den Proceedings des 22. jährlichen ACM-SIAM-Symposiums über diskrete Algorithmen (SODA '11).
• Über Eigenschaften zufälliger Präparationen und Triangulationen . Nicla Bernasconi, Konstantinos Panagiotou und Angelika Steger . In Proceedings of the 19th Annual ACM-SIAM-Symposium über diskrete Algorithmen (SODA '08), p. 132-141. [http://www.mpi-inf.mpg.de/~kpanagio/Dissections.pdf]
• Zu den Gradfolgen zufälliger äußerer und seriell-paralleler Graphen . Nicla Bernasconi, Konstantinos Panagiotou und Angelika Steger . In Proceedings of the 12. Internationaler Workshop über randomisierte Techniken in der Berechnung (RANDOM'08), p. 303-316. [http://www.mpi-inf.mpg.de/~kpanagio/OPSP.pdf]

Diese Umfrage, Die Struktur und Funktion komplexer Netzwerke von Newman, untersucht Techniken und Modelle für real komplexe Netzwerke, einschließlich Konzepten wie Small-World-Effekt, Gradverteilungen und Zufallsgraphenmodellen. Derselbe Autor hat auch eine schöne Abhandlung, Zufallsgraphen als Modelle von Netzwerken , über Anpassungen von Zufallsgraphen zur Modellierung realer Netzwerke.

Verweise:

1) Zufallsgraphen als Modelle von Netzwerken, MEJ Newman, in Handbook of Graphs and Networks, S. Bornholdt und HG Schuster (Hrsg.), Wiley-VCH, Berlin (2003)

2) Struktur und Funktion komplexer Netzwerke, MEJ Newman, SIAM Review 45, 167-256 (2003)

Echte Computernetzwerke auf welcher Ebene? Das Internet ist auf AS-Ebene (wohl die oberste Ebene) ein kleines Netzwerk mit einigen extrem hochgradigen Knoten. Je näher die Ebenen an den tatsächlichen Drähten liegen, desto mehr ist die Grafik mit der Geographie und weniger mit der sozialen Ebene verknüpft (sozial ist eine Art falsches Wort - ist es wirklich ein soziales Netzwerk, wenn die Einheiten, die "Freunde" sind, multinationale Unternehmen?) . Im Extremfall ist ein lokales Ethernet ein logischer Baum, der (wahrscheinlich) ein Subgraph des physikalischen Musters von Drahtverbindungen ist, und dieses Muster von Drahtverbindungen besteht wahrscheinlich nicht aus zu vielen Drähten als einem Baum.

"Echte Computernetzwerke" gibt es in vielen Geschmacksrichtungen und Schichten. Einige von ihnen sehen aus wie soziale Netzwerke, andere nicht. Für mehr Informationen verweise ich unbescheiden auf Kapitel 2 meiner Dissertation - http://home.manhattan.edu/~peter.boothe/thesis.pdf

$n$$u$$v$$\beta e^{-d/(L\alpha)}$$d$$L$ der maximale Abstand ist zwischen einem beliebigen Paar von Eckpunkten. Zegura et al. (1996) vergleichen das Waxman-Diagramm mit mehreren anderen Netzwerkmodellen.

Waxman, Routing von Mehrpunktverbindungen , IEEE J. Select. Bereiche Commun. 6 (9), 1617-1622, 1988. Zegura, Calvert, Bhattacharjee, How to Model an Internetwork , Proc. IEEE INFOCOM '96, 1996.

Walter Willinger hat eine Karriere in der Verwendung von skalierungsfreien Graphen zur Modellierung von Netzwerken aufgebaut. Da es zu viel zu zitieren gibt, verweise ich Sie auf seinen DBLP-Eintrag . Der entscheidende Punkt in diesen Modellen ist, dass sie ähnliche Eigenschaften wie "echte" Netzwerke haben, die nicht von G (n, p) erfasst werden.

Vielleicht möchten Sie sich Durretts Buch ansehen . Ich glaube, Sie haben viel zu lesen.

Anstatt mühsam ein bestimmtes Modell zu finden, zu rechtfertigen und zu analysieren, möchten Sie möglicherweise die vorhandenen realen Daten verwenden (sofern vorhanden). Das bedeutet, ein generisches Wahrscheinlichkeitsmodell zu definieren und seine Parameter anhand Ihrer Daten zu trainieren (z. B. durch Maximum-Likelihood-Schätzung).

Beispielsweise können Sie eine SCFG für Bäume beschreiben (z $S \rightarrow p_1 : (S)S \mid p_2 : \varepsilon$) und weisen Wahrscheinlichkeiten ($p_1, p_2$) basierend auf relativen Vorkommen in Ihrem realen Datensatz, was nachweislich einen MLE ergibt. Sie können Wahrscheinlichkeiten sogar mit dem Inside-Outside-Algorithmus trainieren. Als Bonus haben Sie sogar eine kurze Beschreibung für Ihr Modell, die für eine Vielzahl von Analysen verwendet werden kann.

Offensichtlich kann (und sollte!) Die spezifische Grammatik Domänenwissen verwenden. Betrachten Sie beispielsweise verschiedene Grammatiken, die in Dowell, Eddy (2004) für die Vorhersage der Sekundärstruktur von RNA verwendet wurden , als Geschmacksrichtung.

Details zu dieser Technik finden Sie in Weinberg, Nebel (2010) . Ich weiß jedoch nicht, wie (gut) es auf allgemeine Graphen angewendet werden kann.

Wenn Sie mehr Leistung benötigen, können Sie zu mehrdimensionalen (S) CFGs (z. B. Seki, Kato (2008) ) oder längen- / positionsabhängigen SCFGs ( Weinberg, Nebel (2010) ) wechseln .

Das Problem bei der Verwendung von Erdos-Renyi-Zufallsgraphen ($G(n,p)$ oder $G(n,m)$) ist, dass sie einer Poisson-Gradverteilung folgen, die ihnen einen endlichen zweiten Moment gibt. Viele reale Diagramme, einschließlich des "Web-Diagramms" oder des "Internet-Diagramms", tendieren dazu, dieser Gradverteilung nicht zu folgen, und zwar zugunsten einer Gradverteilung, die im zweiten Moment eine viel größere Variabilität aufweist. Meiner Meinung nach ist einer der größten Unterschiede die Verteilung der Potenzgesetze, die viele von ihnen haben. Siehe beispielsweise Entstehung der Skalierung in zufälligen Netzwerken .

Wie Sie wahrscheinlich wissen, scheint es einen Unterschied zwischen dem Konnektivitätsdiagramm für das World Wide Web und dem Konnektivitätsdiagramm für die Internetinfrastruktur zu geben. Ich behaupte sicherlich nicht, ein Experte zu sein, aber ich habe Li, Alderson, Tanaka, Doyle und Willingers Aufsatz "Auf dem Weg zu einer Theorie von maßstabsfreien Graphen: Definition, Eigenschaften und Implikationen" gesehen , die eine s-Metrik einführen 'um die' Skalenfreiheit 'eines Graphen zu messen (mit der Definition von skalierungsfreien Graphen, über die meines Wissens noch diskutiert wird), der behauptet, ein Graphenmodell zu haben, das Graphen erzeugt, die der Internet-Konnektivität eines Routers ähneln Niveau.

Hier sind einige weitere generative Modelle, die von Interesse sein könnten:

Berger, Borgs, Chayes, D'Souza und Kleinbergs Arbeit "Competition-Induced Preferential Attachment"

Carlson und Doyles hochoptimierte Toleranz: Ein Mechanismus für Potenzgesetze in entworfenen Systemen

Molloy und Reeds kritischer Punkt für zufällige Graphen mit einer vorgegebenen Gradfolge, die das "Modell der gelöschten Konfiguration" einführt

Newmans Clustering und bevorzugte Bindung in wachsenden Netzwerken (was bereits erwähnt wurde)

Man könnte auch explizit eine Gradverteilung generieren und auf diese Weise ein Diagramm erstellen, aber mir ist nicht klar, wie nahe dies dem Internetdiagramm auf Routerebene kommt.

Natürlich gibt es viel mehr Literatur zu diesem Thema, und ich habe nur einige der Höhepunkte genannt (was ich für wichtig halte).

Soweit ich weiß, haben viele Ergebnisse für die Erdos-Renyi-Modelle von Zufallsgraphen ($G(n,p)$ oder $G(n,m)$) Funktioniert nicht , gerade weil die skalenfreie oder Potenzgesetz Grad Zufallsgraphen divergierende zweiten Moment in der Gradverteilung verteilt. Ich behaupte nicht genug über das Thema zu wissen , kategorisch Ansprüche geltend machen , um „ die meisten“ Beweise, aber von dem, was ich gesehen habe, eine der ersten Zeilen von Beweisen für Eigenschaften auf Erdos-RENYI Zufallsgraphen geht davon explizit ein endliche zweiter Moment in der Gradverteilung. Aus meiner Sicht ist dies sinnvoll als ein endlicher zweiter Moment macht Erdos-RENYI Graphen viel mehr lokal baumartig (siehe Mertens und Montanari der Informationen, Physik und Berechnung), Die effektiv Unabhängigkeit Eigenschaften / Wege / Strukturen gibt. Da verteilte Zufallsgraphen nach dem Potenzgesetz ein divergierendes zweites Moment haben, wird diese lokale baumartige Struktur zerstört (und erfordert daher unterschiedliche Beweistechniken?). Ich würde mich freuen, wenn diese Intuition ungültig würde, wenn jemand mit mehr Wissen oder Einsicht zeigen würde, warum dies nicht so ist.

Hoffentlich hilft das.

Obwohl es ein altes Thema ist, antworte ich, da es viele Leute gibt, die solche Posts noch besuchen. Ich bin motiviert von einem Kommentar in einer anderen Antwort.

Das Barabasi-Albert-Modell und andere Modelle, die skalierungsfreie Graphen erzeugen, wurden vorgeschlagen, um das Internet auf der Router-Ebene und auf der Ebene des autonomen Systems zu modellieren. Obwohl anfangs solche Modelle als genau angesehen wurden, stellte sich heraus, dass wir aufgrund von Schwierigkeiten beim Auffinden aller Links kein vollständiges Bild der Internet-Topologie haben. Obwohl angenommen wird, dass es sich um einen schweren Schwanz handelt, ist er noch in Arbeit.

Zu Ihrer Information können Sie lesen: RG Clegg, C Di Cairano-Gilfedder, S Zhou, einen kritischen Blick auf Potenzgesetz des Internet Modellierung

Es gibt mehrere Bücher über zufällige Graphen, wie Bollobás' Buch und es gibt mehrere Modelle von Zufallsgraphen wie kleine Welt Wikipedias Link oder bevorzugte Bindung Wikipedias Link , um Modell - Netzwerke mit kleinen Abständen zwischen Computern oder diejenigen , die mit Gradverteilung nach einem Potenzgesetz , beziehungsweise.

Ich glaube, es gibt keine einfache Möglichkeit, ein echtes Computernetzwerk zu modellieren, aber ich bin mir ziemlich sicher, dass G (n, p) es nicht sehr gut modellieren würde. Es sei denn, Sie mit einem sehr spezifischen organisierten Netzwerk arbeiten.

Meine Empfehlung ist das von den Erfindern des R-MAT-Zufallsgraphengenerators verfasste Umfragepapier. http://portal.acm.org/citation.cfm?id=1132954

Der R-MAT Zufallsgraphen Generator ist sehr einfach und weit verbreitet. Beispielsweise wird dieser Generator im Graph500 Benchmark angenommen ( http://www.graph500.org/ ).