Zufälliges Generieren eines Diagramms basierend auf der Anzahl der Verbindungen auf jedem Knoten

Question

Ich versuche, ein Diagramm basierend auf einigen Daten zu erstellen, die ich habe.

Dieses Diagramm sollte haben N Knoten, bei denen die Anzahl der Kanten jedes Knotens einer Zufallszahl entspricht P(k), wobei k der „Index“ des Knotens ist (meist willkürlich).

Meine Frage ist, gibt es eine tatsächliche Möglichkeit, dies zu tun?Ich denke, dass ich mehr Daten benötige, die entweder die Dichte oder einen anderen Grad der Verbindungen bestimmen (N1->N2->N3), aber ich bin mir nicht ganz sicher.

Answer 1

Sie möchten im Wesentlichen ein Diagramm mit einer gewissen Gradfolge erstellen (die zufällig sein soll, aber das ist nicht relevant);das nennt man Problem der Graphenrealisierung was gelöst wird z.B.bis zum Havel-Hakimi-Algorithmus in dem Sinne, dass der Algorithmus einen (einfachen) Graphen mit der gewünschten Gradfolge zurückgibt, sofern dies möglich ist (solche Folgen werden aufgerufen Grafik).Beachten Sie, dass nicht alle endlichen Folgen vorbei sind $\mathbb N$ sind grafisch wie z.B.Jede Folge, deren Mitglieder in der Summe eine ungerade Zahl ergeben, kann nicht grafisch dargestellt werden Handshake-Lemma (was besagt, dass die Summe aller Grade in einem Diagramm gleich dem Zweifachen der Anzahl der Kanten in einem Diagramm und somit gerade ist).Darüber hinaus werden die Lösungen im Allgemeinen nicht eindeutig sein:Die Abschlussfolge $(2, 2, 2, 2, 2, 2)$ kann beispielsweise durch den Zyklusgraphen realisiert werden $C_6$ der Größe $6$ oder die disjunkte Vereinigung $C_3 \mathop{\dot\cup} C_3$ von zwei Zyklusgraphen $C_3$ der Größe $3$ jede.

Viele Graphbibliotheken für Programmiersprachen verfügen über Implementierungen von Algorithmen für dieses Problem, beispielsweise die Python-Bibliothek Netzwerkx.