如何迭代定义igraph中contract函数的mapping参数以收缩度为2的顶点链？

Great question—manual mapping gets tedious fast, especially with larger graphs. Let's build an automated solution to smooth your graph (contract degree-2 vertices) while preserving the original layout.

Core Logic for Smoothing #

When you smooth a graph, degree-2 vertices act as "bridges" between two neighbors. The goal is to remove these bridge vertices and connect their neighbors directly. For chains of degree-2 vertices (like u-v-w-x), we want to collapse the entire chain into a single connection between the endpoints (u-x).

Step 1: Automated Mapping Generation #

First, let's write a function that generates the mapping vector automatically. This function will:

1. Initialize each vertex to map to itself (so non-degree-2 vertices stay intact).
2. Traverse each degree-2 vertex, and map it to one of its neighbors.
3. Handle chains of degree-2 vertices by propagating the mapping to the entire chain.

library(igraph)

generate_smoothing_mapping <- function(g) {
  # Start with each vertex mapping to itself
  mapping <- V(g)$name
  names(mapping) <- V(g)$name
  
  # Get all degree-2 vertices
  deg2_verts <- V(g)[degree(g) == 2]
  processed <- logical(vcount(g))
  
  for (v in deg2_verts) {
    if (processed[v$name]) next
    
    # Grab the two neighbors of the degree-2 vertex
    neighbors_v <- neighbors(g, v)
    # Pick one neighbor as the target to map to (we'll use the first one here)
    target <- neighbors_v[1]$name
    
    # Map the current vertex to the target
    mapping[v$name] <- target
    processed[v$name] <- TRUE
    
    # Follow the chain: if the next vertex in the chain is also degree-2, map it to the same target
    current_vert <- v
    while (TRUE) {
      # Find the other neighbor (not the one we mapped to)
      next_candidate <- neighbors(g, current_vert)[which(neighbors(g, current_vert)$name != mapping[current_vert$name])]
      
      # Check if this candidate is a degree-2 vertex we haven't processed yet
      if (length(next_candidate) == 1 && degree(g, next_candidate) == 2 && !processed[next_candidate$name]) {
        mapping[next_candidate$name] <- mapping[current_vert$name]
        processed[next_candidate$name] <- TRUE
        current_vert <- next_candidate
      } else {
        break
      }
    }
  }
  
  # Convert mapping to numeric (igraph's contract expects numeric indices/names)
  mapping <- as.numeric(mapping)
  return(mapping)
}

Step 2: Apply Mapping & Preserve Layout #

Now let's integrate this function with your original code, and fix the layout issue so the smoothed graph uses the original positions.

set.seed(1)
# Preprocessing (your original code)
g <- sample_gnp(40, 1/20)
V(g)$name <- seq(1:vcount(g))
components <- clusters(g, mode="weak")
biggest_cluster_id <- which.max(components$csize)
vert_ids <- V(g)[components$membership == biggest_cluster_id]
g <- induced_subgraph(g, vert_ids)
LO <- layout.fruchterman.reingold(g)

# Plot original graph
plot(g, vertex.color = ifelse(degree(g)==2, "red", "green"), main ="Original Graph", layout = LO)

# Generate mapping and contract the graph
mapping <- generate_smoothing_mapping(g)
g2 <- simplify(contract(g, mapping = mapping, vertex.attr.comb = toString))

# Preserve original layout: keep positions of vertices that weren't contracted
# Find vertices in the original graph that mapped to themselves (non-bridge vertices)
original_kept <- V(g)[mapping == V(g)$name]
# Match these to the smoothed graph's vertices to get the correct layout
LO2 <- LO[match(V(g2)$name, original_kept$name), ]

# Plot smoothed graph with original layout
plot(g2, vertex.color = ifelse(degree(g2)==2, "red", "green"), main ="Smoothed Graph", layout = LO2)

Step 3: Iterative Smoothing (Optional) #

If contracting degree-2 vertices creates new degree-2 vertices, you can run the process iteratively until no degree-2 vertices remain:

# Iterate until no degree-2 vertices are left
current_g <- g
current_layout <- LO

while (any(degree(current_g) == 2)) {
  prev_g <- current_g
  mapping <- generate_smoothing_mapping(prev_g)
  current_g <- simplify(contract(prev_g, mapping = mapping, vertex.attr.comb = toString))
  
  # Update layout to match the new graph
  kept_verts <- V(prev_g)[mapping == V(prev_g)$name]
  current_layout <- current_layout[match(V(current_g)$name, kept_verts$name), ]
}

# Plot fully smoothed graph
plot(current_g, main = "Fully Smoothed Graph", layout = current_layout, vertex.color = "green")

Key Notes #

• The function handles chains of degree-2 vertices correctly, collapsing the entire chain into a single connection between the endpoints.
• The layout preservation step ensures the smoothed graph retains the spatial structure of your original graph.
• The vertex.attr.comb = toString parameter keeps track of which original vertices were merged (you can adjust this if you need different attribute handling).

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