Mixing
Generate random graphs with specific mean degree and mean edge weight
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.
graph-theory random random-graphs python
asked Jan 17 at 4:32
reynoldsnlpreynoldsnlp
1286
$endgroup$
add a comment |
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.
graph-theory random random-graphs python
asked Jan 17 at 4:32
reynoldsnlpreynoldsnlp
1286
$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
add a comment |
1
1
1
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.
graph-theory random random-graphs python
asked Jan 17 at 4:32
reynoldsnlpreynoldsnlp
1286
$endgroup$
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.
graph-theory random random-graphs python
graph-theory random random-graphs python
asked Jan 17 at 4:32
reynoldsnlpreynoldsnlp
1286
asked Jan 17 at 4:32
reynoldsnlpreynoldsnlp
1286
asked Jan 17 at 4:32
reynoldsnlpreynoldsnlp
1286
asked Jan 17 at 4:32
reynoldsnlpreynoldsnlp
1286
asked Jan 17 at 4:32
reynoldsnlpreynoldsnlp
1286
1286
$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
add a comment |
$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
$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$
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$
@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
$begingroup$
Please check my answer
$endgroup$
– Oldboy
Jan 17 at 15:06
add a comment |
2 Answers
2
active
oldest
votes
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) tuplesn", graph.getEdges())
print("Nodes connected to node 1, with weights, list of (node, weigh) tuplesn", graph.getNode(1))
print("Complete node info, list of getNode(i) values for all nodesn", graph.getNodes())
print("Matrix representation, element a[i][j] has the weight of connecting edge, 0 otherwisen", graph.getMatrix())
print("Average degree of noden", graph.avgDegree())
print("Average edge weightn", graph.avgWeight())
answered Jan 17 at 11:24
OldboyOldboy
8,4521936
$endgroup$
$begingroup$
Thanks! I made an implementation of your code below usingnetworkx.
$endgroup$
– reynoldsnlp
Jan 18 at 0:55
add a comment |
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)
answered Jan 18 at 0:54
reynoldsnlpreynoldsnlp
1286
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3076596%2fgenerate-random-graphs-with-specific-mean-degree-and-mean-edge-weight%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
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) tuplesn", graph.getEdges())
print("Nodes connected to node 1, with weights, list of (node, weigh) tuplesn", graph.getNode(1))
print("Complete node info, list of getNode(i) values for all nodesn", graph.getNodes())
print("Matrix representation, element a[i][j] has the weight of connecting edge, 0 otherwisen", graph.getMatrix())
print("Average degree of noden", graph.avgDegree())
print("Average edge weightn", graph.avgWeight())
answered Jan 17 at 11:24
OldboyOldboy
8,4521936
$endgroup$
$begingroup$
Thanks! I made an implementation of your code below usingnetworkx.
$endgroup$
– reynoldsnlp
Jan 18 at 0:55
add a comment |
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) tuplesn", graph.getEdges())
print("Nodes connected to node 1, with weights, list of (node, weigh) tuplesn", graph.getNode(1))
print("Complete node info, list of getNode(i) values for all nodesn", graph.getNodes())
print("Matrix representation, element a[i][j] has the weight of connecting edge, 0 otherwisen", graph.getMatrix())
print("Average degree of noden", graph.avgDegree())
print("Average edge weightn", graph.avgWeight())
answered Jan 17 at 11:24
OldboyOldboy
8,4521936
$endgroup$
$begingroup$
Thanks! I made an implementation of your code below usingnetworkx.
$endgroup$
– reynoldsnlp
Jan 18 at 0:55
add a comment |
2
2
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) tuplesn", graph.getEdges())
print("Nodes connected to node 1, with weights, list of (node, weigh) tuplesn", graph.getNode(1))
print("Complete node info, list of getNode(i) values for all nodesn", graph.getNodes())
print("Matrix representation, element a[i][j] has the weight of connecting edge, 0 otherwisen", graph.getMatrix())
print("Average degree of noden", graph.avgDegree())
print("Average edge weightn", graph.avgWeight())
answered Jan 17 at 11:24
OldboyOldboy
8,4521936
$endgroup$
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) tuplesn", graph.getEdges())
print("Nodes connected to node 1, with weights, list of (node, weigh) tuplesn", graph.getNode(1))
print("Complete node info, list of getNode(i) values for all nodesn", graph.getNodes())
print("Matrix representation, element a[i][j] has the weight of connecting edge, 0 otherwisen", graph.getMatrix())
print("Average degree of noden", graph.avgDegree())
print("Average edge weightn", graph.avgWeight())
answered Jan 17 at 11:24
OldboyOldboy
8,4521936
answered Jan 17 at 11:24
OldboyOldboy
8,4521936
answered Jan 17 at 11:24
OldboyOldboy
8,4521936
answered Jan 17 at 11:24
OldboyOldboy
8,4521936
8,4521936
$begingroup$
Thanks! I made an implementation of your code below usingnetworkx.
$endgroup$
– reynoldsnlp
Jan 18 at 0:55
add a comment |
$begingroup$
Thanks! I made an implementation of your code below usingnetworkx.
$endgroup$
– reynoldsnlp
Jan 18 at 0:55
$begingroup$
Thanks! I made an implementation of your code below using
networkx.$endgroup$
– reynoldsnlp
Jan 18 at 0:55
$begingroup$
Thanks! I made an implementation of your code below using
networkx.$endgroup$
– reynoldsnlp
Jan 18 at 0:55
add a comment |
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)
answered Jan 18 at 0:54
reynoldsnlpreynoldsnlp
1286
$endgroup$
add a comment |
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)
answered Jan 18 at 0:54
reynoldsnlpreynoldsnlp
1286
$endgroup$
add a comment |
1
1
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)
answered Jan 18 at 0:54
reynoldsnlpreynoldsnlp
1286
$endgroup$
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)
answered Jan 18 at 0:54
reynoldsnlpreynoldsnlp
1286
answered Jan 18 at 0:54
reynoldsnlpreynoldsnlp
1286
answered Jan 18 at 0:54
reynoldsnlpreynoldsnlp
1286
answered Jan 18 at 0:54
reynoldsnlpreynoldsnlp
1286
1286
add a comment |
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3076596%2fgenerate-random-graphs-with-specific-mean-degree-and-mean-edge-weight%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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