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

Question

我想知道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.

我不完全确定命名法,但我正在寻找的矩阵元素将是连接顶点之间每一步的转移概率的乘积.基本上用产品替换shortest.paths中的sum函数.

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

Answer 1

如果路径的链接具有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),p_i连接成功的概率,以及一对节点之间的最短路径(由shortest.paths函数计算igraph)将是最大化连接概率的路径.您可以根据向量构建图形作为单行,ProbConn并downstream切换到graph.data.frame:

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