1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Oldboy Jan 17 at 7:01
  • $\begingroup$ @Oldboy any standard graph representation format would be fine. $\endgroup$ – reynoldsnlp Jan 17 at 14:17
  • $\begingroup$ Please check my answer $\endgroup$ – Oldboy Jan 17 at 15:06
2
$\begingroup$

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))

    def addWeight(self, i, j, add = 1):
        if self.graph[i][j] > 0:
            self.graph[i][j] += add
            self.graph[j][i] += add
            self.weight += add

    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:
                self.addEdge(i, i + 1)
        # 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:
               self.addEdge(i, i + 1)
        if self.avgDegree() < self.meanDegree:
            # Close the chain
            self.addEdge(0, self.nodes - 1)
        # 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]
            self.addEdge(i, j)
        # 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)
            self.addWeight(i, j)

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())
$\endgroup$
  • $\begingroup$ Thanks! I made an implementation of your code below using networkx. $\endgroup$ – reynoldsnlp Jan 18 at 0:55
1
$\begingroup$

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
        self.add_nodes_from(range(self.num_nodes))
        while self.avg_deg() < self.target_deg:
            n1, n2 = sample(self.nodes(), 2)
            self.add_edge(n1, n2, weight=1)
        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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.