使用 igraph 从 R 中具有最大权重的邻居创建子图

Question

我正在尝试通过以下过程从图中的边对创建子图

a

：

library(igraph)
library(data.table)

dt <- data.table(from = c("A", "B", "C", "D", "E"),
                 to = c("B", "C", "D", "E", "A"),
                 weight1 = c(1, 2, 3, 4, 5),
                 weight2 = c(0, 0, 1, 0, 1))

a <- graph_from_data_frame(dt, directed = FALSE)

1. 用 weight2 == 1 查找所有

   对

   ，每一对都是新子图查找的开始，因此我们可以获得子图 g1、g2、g3 等的列表...:

G = {g1, g2, g3, ..., g_i} g_i ∈ a, nodes(gi) = 2

2. 对于每个

   g_i

   ，找到其所有邻居

   (n1, n2, n3, ..., n_i)

   ，对于ecah邻居计算连接到图

   weight1

   的所有边

   n_i

   的

   g_i

   之和，表示为

   sum_i

3. 如果某个邻居节点的所有邻居节点的 sum_i 的最大值，则将该节点及其所有边（连接到 g_i）添加到图 g_i

4. 重复步骤2-3 3次或没有发现新邻居

我尝试在 R 中使用

igraph

，但不起作用。

g <- a
for (i in 1:length(edges)) {
  g_a <- induced_subgraph(g, ends(g, edges[i]))
  
  for (j in 1:3) {
    neighbors <- unique(unlist(lapply(V(g)[V(g)$name %in% V(g_a)$name], \(x) neighbors(g, x))))
    
    if (length(neighbors) == 0) break
    
    s_values <- sapply(neighbors, function(x) sum(E(g_a, path = c(V(g)[V(g)$name %in% V(g_a)$name], x))$weight1))
    
    max_node <- neighbors[which.max(s_values)]
    
    g_a <- add_vertices(g_a, 1, name = max_node$name)
    new_edges <- E(g, path = c(V(g_a), max_node))
    g_a <- add_edges(g_a, t(as.data.frame(get.edgelist(g, new_edges))), attr = list(weight1 = new_edges$weight1))
  }
}

Answer 1

这可能就是你所追求的

edges <- E(a)[E(a)$weight2 == 1]
ag <- subgraph.edges(a, edges)
lapply(
    decompose(ag),
    \(h) {
        nbs <- setdiff(
            unique(names(unlist(ego(a, nodes = names(V(h)), mindist = 1)))),
            names(V(h))
        )
        p <- lapply(nbs, \(x) induced_subgraph(a, c(names(V(h)), x)))
        p[[which.max(sapply(p, \(s) sum(E(s)$weight1)))]]
    }
)

这给出了

[[1]]
IGRAPH 6913930 UN-- 3 2 --
+ attr: name (v/c), weight1 (e/n), weight2 (e/n)
+ edges from 6913930 (vertex names):
[1] D--E A--E

[[2]]
IGRAPH 6914fac UN-- 3 2 --
+ attr: name (v/c), weight1 (e/n), weight2 (e/n)
+ edges from 6914fac (vertex names):
[1] C--D D--E