使用最短路径计算连接概率

我想知道 igraph 中是否有一个函数可以计算加权图中顶点之间的连接概率，其中边的权重是相邻顶点的连接概率。

我基于这样的邻接矩阵构建了一个图，其中相邻连接概率形成权重（这是针对河流网络，因此图的每个节点仅连接到单个下游节点）。

我本来希望使用类似的东西shortest.pathsigraph 中的函数，但它对权重求和而不是计算它们的乘积，我无法找到改变它的方法。

下面的例子展示了我如何从我拥有的数据构建邻接矩阵，这是顶点连接到其下游顶点（ProbConn）的概率，然后是下游顶点（下游）的标识。最下游的顶点是河口，因此它不与其他顶点相连（因此称为下游的向量以 NA 开头）。

library(igraph)

# vector of probability of connectivity to downstream vertex
ProbConn <- c(0, 1, 0.945881098491627, 0.997349787519144, 0.891475447373691,
0.993221681072185, 0.48071450525165, 0.0292543433507856, 0.0248645581575872,
1, 0.00540807765075205, 0.661465657844344, 0.108524549747512,
0.383311676351655, 0.708853495942148, 0.00150109592270933, 0.463859846404347,
0.0011491165581467, 2.87879700370202e-09, 0.536140153595653,
0.00831752330277812, 0.00185182893416988, 0.0186237313262708,
0.398961560996748, 0.582414707676981, 0.338534342155656, 1, 0.00137024127706289,
0.291146504057852, 1, 0.0743301054564134, 0.0514743607033332,
1, 1)

# the downstream vertex of each node
downstream <- c(NA, 1, 2, 3, 4, 5, 6, 2, 2, 7, 5, 8, 4, 6, 10, 3, 11, 3, 4,
11, 6, 6, 9, 9, 9, 8, 12, 5, 10, 13, 6, 6, 14, 15)

# Create the adjacency matrix from these vectors
adjacPI <- matrix(0, nrow=length(downstream), ncol=length(downstream)) # Set up the adjacency matrix to build the distance matrix

for (i in 1:length(downstream)) {
  adjacPI[i, downstream[i]] <- ProbConn[i]  # Fill the adjacency matrix
}

# create the graph reflecting the downstream connectivity
PIgraph <- graph.adjacency(adjacPI, weighted=T)
plot(PIgraph) # visualise the graph 

PIpath <- shortest.paths(PIgraph, mode="out") 
# creates  the shortest paths matrix based on summing the distances of each step along each path   

为了从最短路径矩阵 PIpath 中提取示例，顶点 10 和 34 通过顶点 15 连接。根据 PIpath 中的计算，顶点 10 和 34 之间的路径距离 (PIpath[34,10]) 为 1.708，它是顶点 34 和 15 (PIpath[34,15] = 1) 以及顶点 15 和 10 (PIpath[15, 10] = 0.708) 之间的连接概率 我希望它是一个乘积，因此之间的路径“距离” 10 和 34 是 1*0.708。

我不完全确定术语，但我正在寻找的矩阵元素将是连接顶点之间每个步骤的转移概率的乘积。本质上用乘积替换最短路径中的求和函数。

是否可以使用 igraph 中的函数来计算，或者我是否需要单独编写一些代码来执行此操作？

如果路径的链接有概率p_1, p_2, ..., p_n成功，那么（假设链接成功概率独立，我将在整个答案中这样做）整个路径成功的概率是p_1 * p_2 * ... * p_n。正如您所注意到的，这是一个产品，但最短路径可以最小化总和；将乘积转换为和的常见技巧是取对数。路径成功概率的对数为log(p_1) + log(p_2) + ... + log(p_n)。最大化（我们的目标）相当于最小化(-log(p_1)) + (-log(p_2)) + ... (-log(p_n))。由于所有概率都在 0 和 1 之间，因此它们的对数是非正的，因此它们的对数的负数也是非负的。

总之，您可以将所有权重设置为-log(p_i), where p_i是连接成功的概率，以及一对节点之间的最短路径（通过以下公式计算）shortest.paths函数于igraph）将是最大化连接概率的路径。您可以根据给定的向量将图表构建为单行图ProbConn and downstream通过切换到graph.data.frame:

PIgraph <- graph.data.frame(na.omit(cbind(from=seq_along(downstream), to=downstream,
                                          weight=-log(ProbConn))),
                            vertices=seq_along(downstream))