基于igraph生成同度小世界网络的高效方法咨询

Hey there! Let's tackle your problem with generating large k-regular small-world networks efficiently in igraph.

First: Use igraph's Built-in Graph.Watts_Strogatz() Function #

You don't need to roll your own implementation for this—igraph has a built-in function that generates exactly the kind of network you want, and it's optimized for speed (since it's implemented in C under the hood).

The Watts_Strogatz() function follows the original Watts-Strogatz small-world model: it starts with a regular lattice (just like your manual approach) and rewires edges with a given probability without changing node degrees—so every node stays k-regular.

Here's how to adapt it to your use case (matching your 5000-node, 16-degree example):

import igraph as ig

# Generate a 1D lattice-based small-world network with 5000 nodes, each connected to 8 left/8 right neighbors (total degree 16)
g = ig.Graph.Watts_Strogatz(dim=1, size=5000, nei=8, p=0.1)  # p is the rewiring probability (adjust as needed)

# Verify all nodes have the same degree
print(all(deg == 16 for deg in g.degree()))  # Should return True

Why Your Custom Implementation is Slow for Large Nodes #

Your manual approach (building a lattice then rewiring in Python loops) gets slow with 5000 nodes because Python loops have significant overhead compared to igraph's optimized C-level operations. Every time you modify the graph in a Python loop, you're crossing the Python-C boundary, which adds up quickly for large graphs.

Bonus: Customization Tips #

If you need more control over the rewiring process (e.g., stricter rules for avoiding self-loops or multiple edges, which Watts_Strogatz() already handles by default), you can still optimize your custom code by:

• Using igraph's vectorized operations instead of Python loops
• Batching rewiring operations to minimize Python-C boundary crossings
• Leveraging igraph's rewire() method with custom rules (though Watts_Strogatz() is still better for standard use cases)

Just remember: for standard k-regular small-world networks, the built-in Watts_Strogatz() function is your fastest and most reliable bet.

内容的提问来源于stack exchange，提问作者user299791