创建一个随机连接的子图

Question

我在 R 中制作了这个随机图/网络：

set.seed(123)
library(igraph)

# Create random graph
graph <- erdos.renyi.game(21, 0.3, type=c("gnp", "gnm"), directed = FALSE, loops = FALSE)

然后，我尝试创建一个随机连接的子图：

# Get the edges of the random subgraph
random_edges <- sample(E(graph), 10)

# Create subgraph from the random edges
subgraph <- subgraph.edges(graph, random_edges)


par(mfrow = c(1,2))

# Plot the subgraph
plot(subgraph, main = "random subgraph")
plot(graph, main = "original graph")

我的问题： 当我查看随机子图时，我看到“节点 4”连接到“节点 10”——但在原始图中，“节点 4”和“节点 10”没有相互连接.

有人可以告诉我如何解决这个问题吗？

谢谢！

Answer 1

如果你想使用

subgraph.edges

的子图，你应该有 ids：

将保留在结果图中的边的边 ID。

您可以使用

V

获取顶点的 ID，如下所示：

set.seed(123)
library(igraph)

# Create random graph
graph <- erdos.renyi.game(21, 0.3, type=c("gnp", "gnm"), directed = FALSE, loops = FALSE)

# Get the edges of the random subgraph
# random_edges <- sample(E(graph), 10)
random_vertices <- sample(V(graph), 10)

# Create subgraph from the random edges
subgraph <- subgraph.edges(graph, random_vertices)

par(mfrow = c(1,2))

# Plot the subgraph
plot(subgraph, main = "random subgraph")
plot(graph, main = "original graph")

^{创建于 2023-03-11 与 reprex v2.0.2}

Answer 2

我认为解决方法是在进行

name

之前向顶点添加

induced.subgraph属性。否则，顶点“标签”（将在子图的图中显示）的索引不同，而不是在原始

vid

.

中保持相同的

graph

---

例如，你可以做

graph %>%
  set.vertex.attribute(name = "name", value = V(.)) %>%
  induced.subgraph(unique(c(ends(., random_edges))))

然后你会得到如下图

IGRAPH da87a26 UN-- 10 16 -- Erdos-Renyi (gnp) graph
+ attr: name (g/c), type (g/c), loops (g/l), p (g/n), name (v/n)
+ edges from da87a26 (vertex names):
 [1]  5--10  1--14  3--14  1--15 14--15  3--16 14--16 14--17  1--18  5--18
[11] 14--18 15--18 17--18  3--20 10--20 16--20

Answer 3

你需要非常小心“随机子图”的意思。这意味着您希望以相等的概率生成每个可接受的子图。您认为可以接受哪种“子图”仍然是一个重要问题。

解决此类问题通常在数学上很难。您对子图施加的每种类型的约束都需要一种不同的方法。因此，您不太可能在现有软件库中找到现成的方法。

---

对于some实际用例，放宽均匀采样的要求（即每个子图以相等的概率生成）。但是要非常小心你从数值实验中得出的结论。

获得随机连通子图的一种相当常见的方法，在不保证均匀性的情况下，是从随机起点随机游走，并记录您遍历的边或顶点（取决于您是否想要导出子图）。请参阅 igraph 中的

random_walk()

和

random_edge_walk()

函数。