I wanted some random examples of graphs where every vertex has degree between two given parameters, minDegree and maxDegree. Like this one:
The approach I took was very simple (and not suitable for construction of very large or very regular graphs). Each edge appears with probability p. If the minimal degree is too small, this probability is multiplied by 1.1. If the maximal degree is too big, the probability is divided by 1.1. Either way, the process repeats until success.
So far, this blog had too much Matlab/Scilab and not enough Python. I’ll try to restore the balance. Here, numpy generates random matrices and takes care of degree restrictions; networkx lays out the graph.
import numpy as np import networkx as nx import matplotlib.pyplot as plt vertices = 15 minDegree = 3 maxDegree = 4 p = 0.5 success = False while not success: a = (np.random.random((vertices, vertices)) < p).astype(int) a = np.maximum(a, np.matrix.transpose(a)) np.fill_diagonal(a, 0) s = a.sum(axis=1) success = True if min(s) < minDegree: success = False p = p * 1.1 if max(s) > maxDegree: success = False p = p / 1.1 g = nx.Graph(a) nx.draw_networkx(g) plt.show()
One more time: