如何用R语言igraph包计算无向图中长度4的无弦环数量？

Hey there! Let's figure out how to count chordless 4-cycles (also called induced 4-cycles) in your undirected weighted graph using R's igraph package.

First, let's clarify what a chordless 4-cycle is: it's a cycle of 4 nodes where there are no "shortcut" edges (chords) between non-consecutive nodes in the cycle. For example, a cycle a-b-c-d-a is chordless only if a isn't connected to c, and b isn't connected to d.

Since your graph is weighted (edge weights represent shared objects), we only care about the existence of edges for cycle detection—not the weight values. Here are two reliable approaches to solve this:

Approach 1: Enumerate 4-node combinations (simple & straightforward for small graphs) #

Since your graph only has 7 nodes, we can check every possible group of 4 nodes to see if they form a chordless 4-cycle. A valid chordless 4-cycle's induced subgraph will have exactly 4 edges, and every node in the subgraph will have a degree of 2.

Here's the code:

library(igraph)

# Your provided adjacency matrix
A <- matrix(c(0L, 3L, 0L, 0L, 0L, 0L, 9L,
              8L, 1L, 0L, 0L, 0L, 0L, 4L,
              0L, 0L, 0L, 0L, 5L, 1L, 1L,
              10L, 0L, 0L, 0L, 0L, 0L, 1L,
              7L, 0L, 0L, 0L, 0L, 2L, 0L,
              11L, 0L, 0L, 0L, 0L, 0L, 0L,
              1L, 0L, 0L, 0L, 1L, 1L, 1L), 7, 7)

# Create undirected weighted graph
g <- graph.adjacency(A, mode = "undirected", diag = FALSE, weighted = TRUE)

# Convert to a simple unweighted graph (we only care if edges exist)
g_simple <- simplify(g, edge.attr.comb = "first")

# Get all nodes in the graph
nodes <- V(g_simple)$name

# Generate all unique 4-node combinations
four_node_groups <- combn(nodes, 4)

# Initialize counter for chordless 4-cycles
cycle_count <- 0

# Check each group of 4 nodes
for (i in 1:ncol(four_node_groups)) {
  # Extract the induced subgraph for the current group
  subgraph <- induced_subgraph(g_simple, four_node_groups[, i])
  
  # Check if the subgraph is a chordless 4-cycle:
  # - Exactly 4 edges (matches the cycle length)
  # - Every node has degree 2 (each node only connects to its two cycle neighbors)
  if (ecount(subgraph) == 4 && all(degree(subgraph) == 2)) {
    cycle_count <- cycle_count + 1
    # Optional: Print the detected cycle for verification
    cat("Found chordless 4-cycle:", paste(V(subgraph)$name, collapse = " - "), "\n")
  }
}

# Output the final count
cat("\nTotal chordless 4-cycles:", cycle_count, "\n")

Approach 2: Use cycles() function (for larger graphs) #

If you ever work with bigger graphs, you can use igraph's cycles() function to get all simple cycles of length 4, then filter out those with chords. Note that this method returns cycles in both directions, so we'll need to deduplicate them:

# Get all simple cycles of length 4
all_4cycles <- cycles(g_simple, length = 4)

# Filter out cycles with chords
chordless_cycles <- lapply(all_4cycles, function(cycle) {
  cycle_nodes <- as.integer(cycle)
  # Check if non-consecutive nodes (1&3, 2&4) are NOT connected
  if (!are.connected(g_simple, cycle_nodes[1], cycle_nodes[3]) && 
      !are.connected(g_simple, cycle_nodes[2], cycle_nodes[4])) {
    return(cycle)
  } else {
    return(NULL)
  }
})

# Remove NULL entries from the list
chordless_cycles <- Filter(Negate(is.null), chordless_cycles)

# Deduplicate cycles (since undirected cycles are counted twice in reverse)
unique_cycles <- unique(lapply(chordless_cycles, function(x) sort(as.integer(x))))

# Output the count
cat("Total chordless 4-cycles:", length(unique_cycles), "\n")

Key Notes #

• Both methods work for your graph, but Approach 1 is more intuitive for small graphs like yours.
• The weight values don't affect cycle detection here—we're only counting structural cycles. If you ever need to calculate weighted cycle totals (e.g., sum of edge weight products), you can modify the code to include weight calculations when a cycle is found.

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