r - 如何知道图中的哪些节点是可移动的

Question

我有一个图 g 大约有 200 个顶点和一些属性，我想知道哪些节点可以被删除，也就是说，这意味着 g 仍然是一个连接的删除它们后的子网，我也想知道哪个节点将产生我需要的属性的最高增长。

举个例子可能更容易理解

g <- erdos.renyi.game(200, 0.03)
V(g)$name <- 1:vcount(my_graph) 
V(g)$weight <- rnorm(200) 
V(g)$RWRNodeweight <- runif(200, min=0, max=0.05)

#Criteria to meet
cumsum <- sum(V(g)$weight*V(g)$RWRNodeweight)/sqrt(sum(V(g)$RWRNodeweight^2))

我想知道哪些节点是“可移动的”，即在删除它们之后，图仍然是完全连接的，然后如果删除“可移动”节点 cumsum 增加，则删除带有增幅最大。一旦删除了具有最高增加量的“可移动”节点，我想再次开始该过程，直到删除“可移动”节点时 cumsum 没有增加

Answer 1

I would like to know which nodes are "removable", i.e, after removing them the graph is still fully connected

articulation.points告诉您删除这些节点会增加连通分量数的节点列表。任何不在此列表中的节点都可以安全删除。然后你必须遍历这个列表并计算 cumsum 的新值(一一排除每个节点)以找到最好删除的一个。