There doesn't seem to be a NetworkX graph generator to directly generate a graph that fulfills such requirement.
However, you could tweak a little bit the approach used in nx.gnp_random_graph
, so that instead of setting an edge among all possible edge combinations with a random probability, we add one edge for each node randomly, and then add the remaining edges with a probability p
.
The following approach not only generates a graph where each node has at least one edge, but also results in a connected graph. This is explained bellow in Further notes -
def gnp_random_connected_graph(n, p):
"""
Generates a random undirected graph, similarly to an Erd?s-Rényi
graph, but enforcing that the resulting graph is conneted
"""
edges = combinations(range(n), 2)
G = nx.Graph()
G.add_nodes_from(range(n))
if p <= 0:
return G
if p >= 1:
return nx.complete_graph(n, create_using=G)
for _, node_edges in groupby(edges, key=lambda x: x[0]):
node_edges = list(node_edges)
random_edge = random.choice(node_edges)
G.add_edge(*random_edge)
for e in node_edges:
if random.random() < p:
G.add_edge(*e)
return G
Sample runs -
As shown in the following example, even assigning a very low probability, the resulting graph is connected:
from itertools import combinations, groupby
import networkx as nx
import random
nodes = random.randint(5,10)
seed = random.randint(1,10)
probability = 0.1
G = gnp_random_connected_graph(nodes,probability)
plt.figure(figsize=(8,5))
nx.draw(G, node_color='lightblue',
with_labels=True,
node_size=500)
nodes = 40
seed = random.randint(1,10)
probability = 0.001
G = gnp_random_connected_graph(nodes,probability)
plt.figure(figsize=(10,6))
nx.draw(G, node_color='lightblue',
with_labels=True,
node_size=500)
Further notes -
The above approach, not only ensures that each node has at least one edge, but also as mentioned that the resulting graph is connected. This is because we are setting at least one edge for each node using the result from itertools.combinations(range(n_nodes), 2)
. This might be clearer with an example:
edges = combinations(range(5), 2)
for _, node_edges in groupby(edges, key=lambda x: x[0]):
print(list(node_edges))
#[(0, 1), (0, 2), (0, 3), (0, 4)]
#[(1, 2), (1, 3), (1, 4)]
#[(2, 3), (2, 4)]
#[(3, 4)]
In this case, we are setting at least one edge in each case taking a random.choice
from the available edges on each iteration, which are edges that have not yet been set. This is a consequence of using the result of itertools.combinations
to set an edge. For undirected graphs it wouldn't make sense to iterate over all existing edges at each iteration, if those edges have previously already been added with a probability p
.
This is not the case of taking the permutations
(see source code for a directed graph case). In the case of a directed graph, connectivity cannot be guaranteed following this approach, since there could two nodes connected by two edges of opposite direction, and be isolated from the rest of the graph. So another approach (perhaps extending the above idea) should be followed.