Erzeugen eines Graphen mit bestimmter Gradverteilung?

Wenn Sie das Konfigurationsmodell verwenden möchten, sollte so etwas in NetworkX funktionieren:

Sie müssen möglicherweise den Mittelwert der Sequenz z abhängig von Parametern in der Gammaverteilung anpassen. Auch muss z nicht grafisch sein (du bekommst ein Multigraph), aber es braucht eine gerade Summe, also musst du vielleicht ein paar zufällige Sequenzen ausprobieren (oder 1 hinzufügen) ...

Die NetworkX Dokumentationsnotizen für configuration_model geben ein anderes Beispiel, eine Referenz und wie man parallele Kanten und Selbstschleifen entfernt:

Hier ist ein Beispiel ähnlich dem in Ссылка , das eine Zeichnung einschließlich eines Diagrammlayouts erstellt die größte zusammenhängende Komponente:

Ich habe das vor einer Weile in der Basis Python ... IIRC, habe ich die folgende Methode verwendet. Aus dem Gedächtnis, also ist das vielleicht nicht ganz genau, aber hoffentlich ist es etwas wert:

1. Wählen Sie die Anzahl der Knoten, N, in Ihrem Diagramm und die Dichte (vorhandene Kanten über mögliche Kanten), D. Dies impliziert die Anzahl der Kanten, E.
2. Ordnen Sie für jeden Knoten seinen Grad zu, indem Sie zuerst eine zufällige positive Zahl x auswählen und P (x) finden, wobei P Ihre PDF ist. Der Grad des Knotens ist (P (x) * E / 2) -1.
3. Wählen Sie einen Knoten zufällig und verbinden Sie ihn mit einem anderen zufälligen Knoten. Wenn einer der Knoten seinen zugewiesenen Grad erreicht hat, eliminiere ihn aus der weiteren Auswahl. Wiederhole E mal.

N.B. dass dies im Allgemeinen keinen verbundenen Graphen erzeugt.

Ich weiß, dass es sehr spät ist, aber Sie können dasselbe, wenn auch ein wenig direkter, mit Mathematica machen.

RandomGraph [DegreeGraphDistribution [{3, 3, 3, 3, 3, 3, 3, 3}], 4]

Dies erzeugt 4 zufällige Graphen, wobei jeder Knoten einen vorgeschriebenen Grad aufweist.

Einschließlich der oben genannten, bietet networkx 4 Algorithmen, die die grad_distribution als Eingabe erhält:

• configuration_model : Erklären Sie mit @eric
• expected_degree_graph : Verwenden Sie einen probabilistischen Ansatz basierend auf dem erwarteten Grad jedes Knotens. Es gibt Ihnen nicht die genauen Grade, sondern eine Annäherung.
• havel_hakimi_graph : dieser versucht zuerst die Knoten mit dem höchsten Grad zu verbinden
• random_degree_sequence_graph : Soweit ich sehen kann, ist dies ähnlich dem, was @ JonC vorgeschlagen hat; Es hat einen trials -Parameter, da es keine Garantie gibt, eine geeignete Konfiguration zu finden.

Die vollständige Liste (einschließlich einiger Versionen der Algorithmen für gerichtete Graphen) ist hier .

Ich habe auch ein paar Papiere gefunden:

• Effizientes und genaues Sampling von einfachen Graphen mit beliebiger Gradfolge
• Ein Sequential Importance Sampling-Algorithmus zum Erzeugen von Zufallsgraphen mit vorgegebenen Abstufungen