图重连边且保留节点度数的高效随机实现方案问询

Great question! Generating a valid edge list that matches a given degree sequence (with no self-loops) while handling large graphs efficiently is a classic graph theory problem—your earlier attempts hit exactly the pain points of naive approaches, so let's fix this with a robust, optimized solution.

Why Your Previous Methods Struggle #

• Random permutation + post-checks: For large graphs (thousands of nodes, high degrees), you're essentially gambling on getting a valid split on the first try. The odds plummet as the graph scales, leading to endless retries.
• Iterative resampling: This can get stuck in loops where you can't fix self-loops without breaking degree counts, especially for dense graphs.

The Better Approach: Use the igraph Library #

The igraph package has built-in, highly optimized functions for generating random graphs from degree sequences. It uses algorithms like the Viger-Latapy method (designed specifically for efficiency with large graphs) that directly construct valid edge lists without post-hoc filtering.

Here's a step-by-step implementation tailored to your needs:

Step 1: Install and Load igraph

install.packages("igraph")
library(igraph)

Step 2: Convert Your Node Vector to a Degree Sequence

Your input vector E is just each node repeated equal to its degree. We first convert this to a formal degree sequence:

# Your original node vector
E <- c(1,1,1,1,2,2,2,3,3,4,4,4,5,5)

# Calculate degree sequence (count occurrences of each node)
deg_seq <- table(E)
# Convert to a numeric vector with node names (igraph uses this to map nodes correctly)
deg_seq <- as.numeric(deg_seq)
names(deg_seq) <- names(table(E))

Step 3: Generate a Valid Random Graph

Use sample_degseq() to create a graph with your degree sequence, enforcing no self-loops (and allowing multiple edges if needed, like your example):

set.seed(123) # For reproducible results
g <- sample_degseq(
  deg_seq,
  method = "vl",          # Viger-Latapy algorithm: fast for large graphs
  no.multiple = FALSE,    # Allow duplicate edges (matches your valid example)
  no.loops = TRUE         # Strictly avoid self-loops
)

Step 4: Extract Your Edge Lists V1 and V2

Convert the graph to an edge list and split into your desired vectors:

# Extract edge list as a matrix
edge_list <- as_edgelist(g, names = TRUE)

# Split into V1 and V2
V1 <- edge_list[, 1]
V2 <- edge_list[, 2]

# Check the output
cat("V1:", paste(V1, collapse = ", "), "\n")
cat("V2:", paste(V2, collapse = ", "), "\n")

# Verify degrees match the original
cat("\nOriginal degrees:", paste(deg_seq, collapse = ", "), "\n")
cat("Generated degrees:", paste(table(V1) + table(V2), collapse = ", "), "\n")

Key Advantages for Large Graphs #

• Efficiency: The Viger-Latapy algorithm runs in linear time relative to the number of edges, so it handles thousands of nodes with degrees over 100 easily.
• Guaranteed Validity: Unlike naive methods, this will always produce a valid edge list (as long as your input degree sequence is "graphical"—which it is, since it comes from an existing graph).
• Flexibility: Adjust no.multiple = TRUE if you need a simple graph with no duplicate edges, or keep it FALSE to allow repeats like your example.

If You Start with an Original Edge List #

If you have the original graph's edge list instead of the node vector E, you can skip the degree sequence calculation step and pull degrees directly from the graph:

# Example: If you have an original edge list
original_edge_list <- matrix(c(1,2, 1,3, 1,4, 1,5, 2,3, 2,4, 4,5), ncol = 2)
original_g <- graph_from_edgelist(original_edge_list)

# Get degree sequence from the original graph
deg_seq <- degree(original_g)

# Generate new random graph
g <- sample_degseq(deg_seq, method = "vl", no.multiple = FALSE, no.loops = TRUE)

This approach eliminates the inefficiencies of your previous attempts and gives you a reliable, scalable solution for generating valid edge lists.

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