Erzeugen eines Graphen mit bestimmten Gradverteilung?

Question

Ich versuche, einen Zufallsgraphen zu erzeugen, die kleine Welt Eigenschaften (zeigt eine Potenzgesetz Verteilung). Ich habe gerade angefangen, das NetworkX Paket mit und entdeckt, dass es eine Vielzahl von Zufallsgraphen Generation bietet. Kann mir jemand sagen, ob es möglich, ein Diagramm, in dem ein gegebenen Knoten-Abschluss folgt eine Gammaverteilung (entweder in R oder mit Python NetworkX Paket)?

zu erzeugen,

Answer 1

Wenn Sie das Konfigurationsmodell so etwas wie dies sollte in NetworkX arbeiten verwenden möchten:

import random 
import networkx as nx
z=[int(random.gammavariate(alpha=9.0,beta=2.0)) for i in range(100)]
G=nx.configuration_model(z)

Unter Umständen müssen Sie den Mittelwert der Folge z einzustellen auf Parameter in der Gammaverteilung abhängig. Auch z nicht grafische sein muss (es eine Multigraph erhalten), aber es hat eine noch Summe benötigen, so müssen Sie vielleicht ein paar Zufallssequenzen versuchen (oder fügen Sie 1) ...

Die Dokumentation NetworkX Hinweise für configuration_model geben ein weiteres Beispiel einer Referenz und wie entfernen parallelen Kanten und Selbstschleifen:

Notes
-----
As described by Newman [1]_.

A non-graphical degree sequence (not realizable by some simple
graph) is allowed since this function returns graphs with self
loops and parallel edges.  An exception is raised if the degree
sequence does not have an even sum.

This configuration model construction process can lead to
duplicate edges and loops.  You can remove the self-loops and
parallel edges (see below) which will likely result in a graph
that doesn't have the exact degree sequence specified.  This
"finite-size effect" decreases as the size of the graph increases.

References
----------
.. [1] M.E.J. Newman, "The structure and function
       of complex networks", SIAM REVIEW 45-2, pp 167-256, 2003.

Examples
--------
>>> from networkx.utils import powerlaw_sequence
>>> z=nx.create_degree_sequence(100,powerlaw_sequence)
>>> G=nx.configuration_model(z)

To remove parallel edges:

>>> G=nx.Graph(G)

To remove self loops:

>>> G.remove_edges_from(G.selfloop_edges())

Hier ist ein Beispiel ähnlich dem unter http://networkx.lanl.gov /examples/drawing/degree_histogram.html , die eine Zeichnung, die eine grafische Darstellung Layout der größten zusammenhängenden Komponente macht:

#!/usr/bin/env python
import random
import matplotlib.pyplot as plt
import networkx as nx

def seq(n):
    return [random.gammavariate(alpha=2.0,beta=1.0) for i in range(100)]    
z=nx.create_degree_sequence(100,seq)
nx.is_valid_degree_sequence(z)
G=nx.configuration_model(z)  # configuration model

degree_sequence=sorted(nx.degree(G).values(),reverse=True) # degree sequence
print "Degree sequence", degree_sequence
dmax=max(degree_sequence)

plt.hist(degree_sequence,bins=dmax)
plt.title("Degree histogram")
plt.ylabel("count")
plt.xlabel("degree")

# draw graph in inset 
plt.axes([0.45,0.45,0.45,0.45])
Gcc=nx.connected_component_subgraphs(G)[0]
pos=nx.spring_layout(Gcc)
plt.axis('off')
nx.draw_networkx_nodes(Gcc,pos,node_size=20)
nx.draw_networkx_edges(Gcc,pos,alpha=0.4)

plt.savefig("degree_histogram.png")
plt.show()

Answer 2

Ich habe diese vor einer Weile in der Basis Python ... IIRC, ich die folgende Methode verwendet. Aus dem Gedächtnis, so dass dies nicht ganz korrekt sein, 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 bedeutet, die Anzahl der Kanten, E.
2. Für jeden Knoten zuweisen seinen Grad, indem zuerst eine zufällige positive Zahl x der Auswahl und der Suche nach P (x), wobei P Ihr pdf ist. Die Knoten-Abschluss ist (P (x) * E / 2) -1.
3. Wählen Sie einen Knoten nach dem Zufallsprinzip, und verbinden Sie es mit einem anderen zufälligen Knoten. Wenn entweder Knoten seinen zugewiesenen Grad realisiert hat, beseitigen sie von der weiteren Auswahl. Wiederholen E Zeiten.

N. B. dass dies nicht eine zusammenhängende Graph im Allgemeinen erstellen.

Answer 3

Ich weiß, das ist sehr spät, aber Sie können das gleiche tun, wenn auch ein wenig einfacher, mit Mathematica.

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

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

Answer 4

einschließlich der oben erwähnten, networkx stellt 4-Algorithmen, die die degree_distribution als Eingang empfängt:

• configuration_model : erklären, durch @eric
• expected_degree_graph : einen probabilistischen Ansatz auf dem erwartete Grad jeden Knotens basierte. Es wird Sie nicht die genauen Grad geben, sondern eine Annäherung.
• havel_hakimi_graph : diese versucht man die Knoten mit dem höchsten Grad verbinden ersten
• random_degree_sequence_graph : soweit ich sehen kann, ist dies ähnlich dem, was @JonC vorgeschlagen; es hat einen trials Parameter, da es keine Garantie für die Suche nach einer geeigneten Konfiguration ist.

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

Ich fand auch ein paar Papiere:

• Effiziente und exakte Probenahme von einfachen Graphen mit bestimmtem beliebigem Grad Folge
• A Sequential Importance Sampling-Algorithmus zur Erzeugung von Zufallsgraphen mit Vorgeschrieben Degrees