4

TLDR：我想提取 igraph 中两个顶点之间的每条路径的边缘类型。有没有相对健全的方法来做到这一点？

我工作的诊所最近在一所高中进行了一项相当大的（1400 人）肺结核接触者调查。我有所有学生和老师的课程表（！）并将它们放入一个网络（使用 R 中的 igraph），每个学生和每个房间周期组合作为一个顶点（例如，123 房间的班级在周期1 是一个顶点，其边指向第 2 期房间 123 中的类）。我也知道哪些房间共用通风系统——这是一种看似合理但不太可能的感染机制。该图是从唯一的源案例中导出的，因此网络上的每条路径中只有两个人——源和联系人，由可变数量的房间周期顶点分隔。从概念上讲，有四种路径：

  • 个人接触曝光（来源 -> 仅限联系人）
  • 共享类暴露（来源 -> 房间期间 -> 联系人）
  • 下一期风险敞口（来源-> Room 123 Period 1 -> Room 123 Period 2 -> 联系方式）
  • 通风暴露（来源 -> Room 123 Period 1 -> Room 125 Period 1 -> 接触）

每个边缘都有一个属性，指示它是人与人之间的暴露、同室不同时期还是通风边缘。

作为在该网络上对感染进行建模的中间步骤，我想简单地计算一下学生每种类型的暴露次数。例如，一个学生可能与源共享一个班级，然后在一段时间后进入了源曾所在的房间，并且可能在第二天进入了通风相邻的房间。该学生的指标将是：

personal.contact: 0
shared.class:     1
next.period:      1
vent:             1

不过，我不确定如何最好地获取此类信息 - 我看到了获取最短路径的功能，这使得识别个人联系链接变得容易，但我认为我需要评估所有路径（这似乎是一个疯狂的问题在一个典型的社交网络上，但当只有源和房间周期有外缘时并不那么疯狂）。如果我能达到每个源到接触路径都由边缘类型的有序向量表示的地步，我想我可以轻松地将它们子集到我的标准中。我只是不知道怎么去那里。如果 igraph 不适合这个框架，我只需要在学生的日程安排上写一些可怕的大循环，就这样吧！但在我深入那个洞之前，我会很感激一些指导。

这是与三个间接路径中的每一个的接触的示例图：

# Strings ain't factors
options(stringsAsFactors = FALSE)  
library(igraph)

# Create a sample case
edgelist <- data.frame(out.id = c("source", "source", 
                                  "source", "Rm 123 Period 1", 
                                  "Rm 125 Period 2", "Rm 125 Period 3", 
                                  "Rm 127 Period 4", "Rm 129 Period 4"),
                       in.id = c("Rm 123 Period 1", "Rm 125 Period 2", 
                                 "Rm 127 Period 4", "contact", 
                                 "Rm 125 Period 3", "contact", 
                                 "Rm 129 Period 4", "contact"),
                       edge.type = c("Source in class", "Source in class",
                                     "Source in class", "Student in class",
                                     "Class-to-class", 
                                     "Student in class", "Vent link",
                                     "Student in class"
                                     )
)

samp.graph <- graph.data.frame(edgelist, directed = TRUE)

# Label the vertices with meaningful names
V(samp.graph)$label <- V(samp.graph)$name

plot(samp.graph, layout = layout.fruchterman.reingold)
4

1 回答 1

1

我不完全确定我了解您的图形模型，但如果问题是：

I have two vertices and I wish to extract every path between them,
then extract the edge attributes of those edges.

那么也许这可能会奏效。

进行广度优先搜索。Igraph 包含一个，但它很容易推出您自己的，这将使您更灵活地了解您想要获取的信息。我假设您的图表中没有循环 - 否则您将获得无限数量的路径。我不太了解 Python（尽管我确实在 R 中使用了 igraph），所以这里有一些伪代码。

list <- empty

allSimplePaths(u, v, thisPath)
  if (u == v) return
  for (n in neighborhood(u))
    if (n in thisPath)
      next
    if (u == v)
      list <- list + (thisPath + v)
  for (n in neighborhood(u))
    thisPath <- thisPath + n
    allSimplePaths(n, v, thisPath)
    thisPath <- thisPath - thisPath.end

基本上它说“从每个顶点，尝试所有可能的扩展路径以到达终点。” 添加另一个 thisPathEdges 并插入边，将其传递给函数以及顶点是一件简单的事情。当然，如果它不是递归的，它会运行得更好。小心，因为这个算法可能会用足够多的节点来破坏你的堆栈。

您可能仍然想使用@PaulG 的模型，并且在学生节点之间只有多个边。您可以做一些很酷的事情，例如运行广度优先搜索以查看疾病如何传播或找到最小生成树以获得时间估计，或找到最小切割来隔离正在进行的感染或其他东西。

于 2012-07-31T07:18:19.733 回答