Algorithmen zur Graphengenerierung unter Verwendung vorgegebener Eigenschaften

Es kann eine große Anzahl von Algorithmen vorgeschlagen werden, um Graphen zu erzeugen, die einige gemeinsame Eigenschaften erfüllen (z. B. Clusterkoeffizient, durchschnittliche kürzeste Weglänge, Gradverteilung usw.).

Meine Frage betrifft einen bestimmten Fall: Ich möchte einige ungerichtete reguläre Diagramme (dh jeder Knoten in diesen Diagrammen hat die gleiche Anzahl von Nachbarn) mit unterschiedlichen Clusterkoeffizienten und durchschnittlichen kürzesten Pfadlängen generieren. Im Allgemeinen möchte ich durch Festlegen einer Gradverteilung Diagramme mit unterschiedlichen Clusterkoeffizienten und durchschnittlichen kürzesten Pfadlängen erstellen.

Ich frage mich, welche Algorithmen dafür bekannt sind (oder gibt es tatsächlich welche?) Und welche Software für denselben Zweck empfohlen wird.

Es gibt keine allgemeinen Algorithmen für Ihr Problem, aber was man normalerweise tut (für Diagramme kleiner Aufträge), ist

1. Verwenden Sie nauty , um Diagramme zu erstellen , die einige grobe Einschränkungen erfüllen (Sie können nauty nur (bi) verbundene Diagramme, reguläre Diagramme, dreieck- / viereckfreie Diagramme usw. erstellen lassen.)

2. Verwenden Sie ein externes Programm, um nur die Diagramme zu extrahieren, die Sie in Bezug auf einige zusätzliche Eigenschaften benötigen, die Sie möchten.

Sie können sowohl 1 als auch 2 in Salbei tun ! Angenommen, Sie möchten alle verbundenen 5-regulären Graphen der Ordnung 20 generieren, die einen durchschnittlichen Abstand 10 (Wiener-Index ??) und einen Clustering-Koeffizienten haben. Sie machen folgendes

for G in graphs.nauty_geng(" 20 -c -d5 -D5" ):
    if G.wiener_index() == 10 and G.clustering_coeff() == SOMETHING:
       print G.adjacency_matrix()

Lassen Sie mich wissen, wenn Sie spezifischere Antworten in Bezug auf Salbei benötigen.