python - 如何在 igraph 中提取某些路径类型？

Question

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

---

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

• 个人接触暴露(来源 -> 仅限接触)
• 共享类曝光(源 -> 房间周期 -> 联系人)
• 下一期风险敞口(来源 -> 123 室第 1 期 -> 123 室期 2 -> 联系人)
• 通 Storm 露(来源 -> 123 室第 1 期 -> 125 室期间 1 -> 联系人)

每条边都有一个属性，指示它是人对人暴露、同室不同时期还是通风边。

作为在此网络上建模感染的中间步骤，我想简单地计算一下学生接触过的每种类型的次数。例如，一个学生可能与源共享一个类(class)，然后在一段时间后进入了源所在的房间，也许第二天又进入了一个与通风设备相邻的房间。该学生的指标将是:

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

不过，我不确定如何最好地获取此类信息 - 我看到了获取最短路径的函数，这使得识别个人联系链接变得容易，但我认为我需要评估 < em>所有路径(在典型的社交网络上要求这似乎是一件疯狂的事情，但当只有源和房间周期有边缘时就没那么疯狂了)。如果我能达到每个源到接触路径都由边缘类型的有序向量表示的地步，我想我可以轻松地将它们子集化到我的标准。我只是不知道如何到达那里。如果 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)

Answer 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 的模型，并且只在学生节点之间设置多条边。您可以做一些很酷的事情，比如运行广度优先搜索以查看疾病如何传播，或者找到最小生成树来估计时间，或者找到最小切割来隔离正在进行的感染或其他事情。