Generieren Sie mit Barabasi-Albert skalierungsfreie Netzwerke mit Potenzgesetz-Gradverteilungen

11

Ich versuche, die in einigen Artikeln beschriebenen synthetischen Netzwerke (Grafiken) zu reproduzieren.

Es wird angegeben, dass das Barabasi-Albert- Modell verwendet wurde, um " skalierungsfreie Netzwerke mit Potenzgesetz- , " zu erstellen .PA(k)kλ

PA ist eine Wahrscheinlichkeitsverteilung, die die Wahrscheinlichkeit eines Knotens mit dem Grad k zurückgibt k. Zum Beispiel gibt PA(2) die Wahrscheinlichkeit an, einen Knoten zufällig aus dem Netzwerk auszuwählen und einen Knoten mit Grad 2 zu erhalten.

Der durchschnittliche Grad k Hub scheint 4 in einer Arbeit zu sein, mit einem Minimum von k von 2. Kein Wort über das Maximum von k . In dem anderen Papier ist es nicht angegeben. Es scheint nicht so wichtig zu sein, das Netzwerk zu definieren.

Lambda λ-Werte sind angegeben, ebenso wie die Anzahl der Knoten n . Kombinationen sind

  1. n = 50000, λ = 3, 2,7, 2,3, mit in einem Papier
  2. n = 4000 und λ = 2,5 oder n = 6000 und λ = 3 in der anderen Veröffentlichung

Ich habe nach Bibliotheken gesucht, die den Barabasi-Albert-Algorithmus implementieren, und sie scheinen andere Parameter als Lambda und den durchschnittlichen Grad zu erfordern. Eines ist NetworkX , ein anderes ist GraphStream (Implementierung hier ). Sie arbeiten auf ähnliche Weise und fragen nach:

  • n : int - Anzahl der Knoten
  • m : int - Anzahl der Kanten, die von einem neuen Knoten an vorhandene Knoten angehängt werden sollen; Die Anzahl der Kanten, die bei jedem Schritt hinzugefügt werden sollen

Wie kann ich die Einstellungen m berechnen, um ein vergleichbares Diagramm zu erstellen?

Hier einige Referenzen:

  • Katastrophale Kaskade von Ausfällen in voneinander abhängigen Netzwerken, Buldyrev et al. 2010 mit einer separat bereitgestellten Zusatzinformation
  • Kleiner Cluster in Cyber ​​Physical Systems, Huang et al. 2014
  • Katastrophale Kaskade von Ausfällen in voneinander abhängigen Netzwerken, Havlin et al. 2010 ist dies auf dem Arxiv und verdeutlicht etwas das erste

Beachten Sie, dass diese Artikel "Generierungsfunktionen" verwendeten, um einige Eigenschaften dieser Diagramme analytisch zu untersuchen. Sie führen jedoch auch Simulationen für diese Modelle durch, sodass sie diese Netzwerke irgendwie generiert haben müssen.

Vielen Dank.

Agostino
quelle
Mathematica macht das übrigens auch .
Juho

Antworten:

7

Die kurze Antwort lautet, dass Sie diese Software nicht unverändert verwenden können, um das zu erhalten, was Sie möchten. Für ein festes hat das Barabasi-Albert-Modell unabhängig von m immer die Gradverteilung P kk - 3 . Die genaue Formel für den Wahrscheinlichkeitsgrad dessen, was diese Softwareteile implementieren (welches das BA-Modell ist)mPkk3m

Pk=2m(m+1)k(k+1)(k+2)

Die Arbeiten (mit ) sprechen wahrscheinlich von einer Art verallgemeinertem BA-Modell, nehme ich an. Es wäre hilfreich, mehr Details (vollständige Zitate) zu ihnen zu geben.λ3

EDIT: OK, ich werde mir diese Refs ansehen. In der Zwischenzeit habe ich festgestellt, dass es ein R-Paket namens igraph gibt , das tun kann, was Sie wollen. Das dort verwendete relevante theoretische Papier / Zitat ist:

Pd(k)kλ

GpGc

λλλ=3λ=2.7 Diagramme aus Abb. 8. Ich kann sehen, wie Sie beim Lesen dieses Dokuments den Schluss ziehen können, dass BA solche Diagramme erstellen kann ... aber nicht.

PA(k)PB(k)/kλλλ=3λ

Fizz
quelle
Danke für den Fang. Sie hätten jedoch viel klarer sein können. Tatsächlich fehlt mir hier immer noch der Parameter m, es gibt nur einen durchschnittlichen Grad in Abb. 2.
Agostino
2
Sprechen Sie über das gleiche Papier? Ich kann die Zeichenfolge in arxiv.org/pdf/0907.1182v1.pdf
Fizz
Nein, das erste Papier von Buldyrev et al., Auf das ich mich beziehe, hat denselben Titel, wurde jedoch 2010 veröffentlicht und befindet sich leider nicht auf dem Arxiv. Es ist das mit einer Menge Zitate, wenn Sie auf Google suchen.
Agostino
@ Agostino: Ja, ich habe es gefunden und jetzt gelesen. siehe EDIT4.
Fizz