# Generate random graphs with specific mean degree and mean edge weight

I need to generate random undirected graphs with the following characteristics:

• 24 nodes
• mean degree ranging between 1 and 23
• mean edge weight ranging between 1 and 5 (weights must be integers)

I have tried using the python module networkx's expected_degree_graph, but I am not getting anything near the desired result. I tried the example at the bottom of that doc page...

>>> z=[10 for i in range(100)]
>>> G=nx.expected_degree_graph(z)


...but I just get mostly disconnected graphs:

>>> G.degree()
DegreeView({0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0, 11: 0, 12: 0, 13: 0, 14: 0, 15: 0, 16: 0, 17: 0, 18: 0, 19: 0, 20: 0, 21: 0, 22: 0, 23: 0, 24: 0, 25: 0, 26: 0, 27: 0, 28: 0, 29: 0, 30: 0, 31: 0, 32: 0, 33: 0, 34: 0, 35: 0, 36: 0, 37: 0, 38: 0, 39: 0, 40: 0, 41: 0, 42: 0, 43: 0, 44: 0, 45: 0, 46: 0, 47: 0, 48: 0, 49: 0, 50: 0, 51: 0, 52: 0, 53: 0, 54: 0, 55: 0, 56: 0, 57: 0, 58: 0, 59: 0, 60: 0, 61: 0, 62: 0, 63: 0, 64: 0, 65: 0, 66: 0, 67: 0, 68: 0, 69: 0, 70: 0, 71: 0, 72: 0, 73: 0, 74: 0, 75: 0, 76: 0, 77: 0, 78: 0, 79: 0, 80: 0, 81: 0, 82: 0, 83: 0, 84: 0, 85: 0, 86: 0, 87: 0, 88: 0, 89: 0, 90: 0, 91: 0, 92: 0, 93: 0, 94: 0, 95: 0, 96: 0, 97: 0, 98: 0, 99: 0, 100: 2})


I prefer solutions using python, but I'll take anything.

• What is the prefererred format for your graph data? Is it ok to have matrix with values $w_{ij}$ representing weight of edge between nodes $i$ and $j$ and zero otherwise? In undirected graph matrix would be symmetrical, of course. I can easily create such matrix. – Oldboy Jan 17 at 7:01
• @Oldboy any standard graph representation format would be fine. – reynoldsnlp Jan 17 at 14:17

Fairly efficient, won't create disconnected graphs:

import random

class RandomGraph:
def __init__(self, nodes, meanDegree, meanWeight):
self.nodes = nodes
self.meanDegree = meanDegree
self.meanWeight = meanWeight
self.edges = 0
self.weight = 0
self.graph = [[0 for i in range(0, self.nodes)] for j in range(0, self.nodes)]
self.positions = [(i,j) for i in range(0, self.nodes) for j in range(0, self.nodes) if i < j]
random.shuffle(self.positions)

def avgDegree(self):
return (self.edges * 2.0) / self.nodes

def avgWeight(self):
return self.weight / self.edges

def addEdge(self, i, j, weight = 1):
if self.graph[i][j] == 0 and self.graph[j][i] == 0:
self.graph[i][j] = weight
self.graph[j][i] = weight
self.edges += 1
self.weight += weight
self.positions.remove((i, j))

if self.graph[i][j] > 0:

def removeEdge(self, i, j):
self.graph[i][j] = 0
self.graph[j][i] = 0

def getEdges(self):
return [(i, j, self.graph[i][j]) for i in range(0, self.nodes) for j in range(0, self.nodes) if i < j and self.graph[i][j] > 0]

def getMatrix(self):
return self.graph

def getNode(self, node):
return [(j, self.graph[node][j]) for j in range(0, self.nodes) if self.graph[node][j] > 0]

def getNodes(self):
return [(i, self.getNode(i)) for i in range(0, self.nodes)]

def createGraph(self):
# First connect even nodes with odd nodes
for i in range(0, self.nodes, 2):
if self.avgDegree() >= self.meanDegree:
break
if i + 1 < self.nodes:
# Now connect odd nodes with even nodes (make chain)
for i in range(1, self.nodes, 2):
if self.avgDegree() >= self.meanDegree:
break
if i + 1 < self.nodes:
if self.avgDegree() < self.meanDegree:
# Close the chain
# At this point we should start edges randomly until we have reach the average degree
while(len(self.positions) > 0):
if self.avgDegree() >= self.meanDegree:
break
(i, j) = self.positions[0]
# Now we have to increase weights until we reach the needed average
existingEdges = self.getEdges()
while(self.avgWeight() < self.meanWeight):
(i, j, weight) = random.choice(existingEdges)

graph = RandomGraph(24, 5, 3.3)
graph.createGraph()
print("All graph edges with weights, list of (node1, node2, weight) tuples\n", graph.getEdges())
print("Nodes connected to node 1, with weights, list of (node, weigh) tuples\n", graph.getNode(1))
print("Complete node info, list of getNode(i) values for all nodes\n", graph.getNodes())
print("Matrix representation, element a[i][j] has the weight of connecting edge, 0 otherwise\n", graph.getMatrix())
print("Average degree of node\n", graph.avgDegree())
print("Average edge weight\n", graph.avgWeight())

• Thanks! I made an implementation of your code below using networkx. – reynoldsnlp Jan 18 at 0:55

Inspired by the answer given by Oldboy, here is a solution using networkx.

from statistics import mean
from random import choice
from random import sample

import networkx as nx

class MyGraph(nx.Graph):
def __init__(self, num_nodes, target_deg, target_wght, max_wght=5):
super().__init__()
self.num_nodes = num_nodes
self.target_deg = target_deg
self.target_wght = target_wght
self.max_wght = max_wght
while self.avg_deg() < self.target_deg:
n1, n2 = sample(self.nodes(), 2)
while self.avg_wght() < self.target_wght:
n1, n2 = choice(list(self.edges()))
if self[n1][n2]['weight'] < self.max_wght:
self[n1][n2]['weight'] += 1

def avg_deg(self):
return self.number_of_edges() * 2 / self.num_nodes

def avg_wght(self):
wghts = []
for i in range(self.num_nodes):
for j in range(i + 1, self.num_nodes):
try:
wghts.append(self[i][j]['weight'])
except KeyError:
pass
return mean(wghts)