从邻接矩阵 r 和 igraph 中获取传播链。

Question

问：我有一个Erdos.Renyi图形。我感染了一个顶点，想看看疾病会遵循哪个顶点序列？igraph具有get.adjacency()、neighbors()等有用的函数。

详情：这是邻接矩阵，其中包含顶点名称而不是0,1标志，并且我正在尝试从中获取传染链。就像流行病通过图形的流程/序列一样，如果某个顶点被感染了。在这里，让我们不要担心感染概率（假设所有被击中的顶点都以1的概率被感染）。

因此，假设我击中顶点1（这里是第1行）。我们看到它向顶点4、5、18、22、23、24、25发出链接。然后，下一个顶点将是连接到4、5、18…25即行4、行5、行18…行25中的那些值的顶点。然后，根据模型，疾病将通过这些顶点传播，依此类推。

我知道我可以传递一个字符串来对矩阵行进行排序。我的问题是，我无法弄清楚如何生成该序列。

该矩阵如下所示：

    > channel
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
 [1,]    4    5   18   22   23   24   25   NA
 [2,]    6   10   11   18   25   NA   NA   NA
 [3,]    7   11   18   20   NA   NA   NA   NA
 [4,]   24   NA   NA   NA   NA   NA   NA   NA
 [5,]    1    3    9   13   14   NA   NA   NA
 [6,]    3    8    9   14   19   23   NA   NA
 [7,]    3    4    8   15   20   22   NA   NA
 [8,]    2    3   25   NA   NA   NA   NA   NA
 [9,]    3    4   11   13   20   NA   NA   NA
[10,]    4    5    8   15   19   20   21   22
[11,]    3   13   15   18   19   23   NA   NA
[12,]   11   13   16   NA   NA   NA   NA   NA
[13,]    4    6   14   15   16   17   19   21
[14,]    2    6   13   NA   NA   NA   NA   NA
[15,]    3   17   20   NA   NA   NA   NA   NA
[16,]    6   15   18   23   NA   NA   NA   NA
[17,]    2   25   NA   NA   NA   NA   NA   NA
[18,]    2    5   NA   NA   NA   NA   NA   NA
[19,]    3   11   NA   NA   NA   NA   NA   NA
[20,]    1    4    7   10   12   21   22   25
[21,]    2    4    6   13   14   16   18   NA
[22,]    1    3    4   15   23   NA   NA   NA
[23,]    1   16   24   NA   NA   NA   NA   NA
[24,]    7    8   19   20   22   NA   NA   NA
[25,]    7   12   13   17   NA   NA   NA   NA

我希望根据以下选择标准重新排列此矩阵：

R将非常有帮助（但我对算法感兴趣，因此任何Python、Ruby等都很好）。结果向量的长度为115（8x25=200-85个NAs=115），并且看起来像这样。这基本上是如果顶点1被感染，疾病会如何传播。

4,5,18,22,23,24,25,24,1,3,9,13,14,2,5,1,3,4,15,23,1,16,24,7,8,19,20,22,7,12,13,17,7,8,19,20,22, 4,5,18,22,23,24,25,7,11,18,20...

目前我所了解的是： 1. R有一个包**igraph**，它可以让我计算邻居(graph, vertex, "out") 2. 同样的包还可以生成get.adjlist(graph...), get.adjacency

- user2217564

---

有趣的评论。既然你们坚持。这个矩阵是邻接矩阵，但是使用向量名称而不是二进制标志。输出将是流行病流模型...只是它不是建模疾病，而是银行违约！！ :)至于提示...从过去两周的编码中，我发现对于像R / java这样的高级语言，与C ++中的老派字符类型相比，操作向量要好得多。 - user2217564

等等，这不就是对图进行广度优先搜索吗？ - Marius

广度优先搜索在无向图上工作，因为它维护了一个已访问节点的列表，这使得搜索不会无限制地进行下去，而只是到达所有可达的节点。 - Marius

@Marius，你太棒了！这正是我在寻找的东西！谢谢。 - user2217564

@jordan 当然，这是同样的问题。但不一定是相同的问题。那个（在编辑之前）是关于无论上下文或语言如何排序矩阵的问题。这是关于图论和广度优先搜索的问题。我尝试删除重复项，但需要更多的投票。仔细想想，我们可以留下这个问题，供那些想以不规则的方式对矩阵进行排序的人使用。解决方案将是对矩阵进行排序，而不是使用预定义函数。我找不到任何解决此类问题的排序算法。感谢大家的帮助。 - user2217564

Answer 1

找到这样的“传染链”等价于通过图进行广度优先搜索，例如：

library(igraph)
set.seed(50)
g = erdos.renyi.game(20, 0.1)
plot(g)
order = graph.bfs(g, root=14, order=TRUE, unreachable=FALSE)$order

输出：

> order
 [1]  14   1   2  11  16  18   4  19  12  17  20   7   8  15   5  13   9 NaN NaN NaN

- Marius

Answer 2

我不清楚你如何定义行的排序，所以......这里有一些提示：

你可以通过传递一个索引向量来选择行的排列组合：

> (m <- matrix(data=1:9, nrow=3))
     [,1] [,2] [,3]
[1,]    1    4    7
[2,]    2    5    8
[3,]    3    6    9
> m[c(2,3,1),]
     [,1] [,2] [,3]
[1,]    2    5    8
[2,]    3    6    9
[3,]    1    4    7

t()函数用于矩阵转置。

矩阵按列优先（或列主序）顺序存储：

> as.vector(m)
[1] 1 2 3 4 5 6 7 8 9

"

NA值可以通过子集操作进行删除：

"

> qq <- c(1,2,NA,5,7,NA,3,NA,NA)
> qq[!is.na(qq)]
[1] 1 2 5 7 3

此外，生物信息学的 graph 或 CRAN 的 igraph 包提供了图算法。

- krlmlr