IGRAPH IN R：查找使边缘属性乘积最大化的顶点之间的路径

Question

我需要找到一种方法来查找使边缘属性乘积最大化的两个顶点之间的路径。在我的情况下，边缘属性是连接的可能性。 假设我想找到在下面的例子中的顶点1和4之间的最大概率路径：

require(igraph)  
G<-graph.data.frame(as.data.frame(cbind(id1=c(1,1,2,3,1,4),id2=c(2,3,4,4,5,5),weight=c(0.5,0.35,0.5,0.9,0.6,0.6))), directed=FALSE) 

plot(G, edge.label=paste(E(G),"=",signif(E(G)$weight, digits=1)), vertex.size=10) 

#weighted shortest path using connection probability 
a<-get.shortest.paths(G,1,4, weights=E(G)$weight, output="epath")[[1]] 
E(G)[a] 
prod(E(G)$weight[a]) 

#weighted shortest path using the inverse of connection probability 
b<-get.shortest.paths(G,1,4, weights=1-E(G)$weight, output="epath")[[1]] 
E(G)[b] 
prod(E(G)$weight[b]) 

在这个例子中，最大化的连接路径是通过顶点5，实际上的产品概率等于0.36（0.6 * 0.6）。 最短路径函数似乎在属性总和的基础上给予优先权，但不是产品。事实上，在上面的例子中，无论我使用概率还是概率的倒数，它都暗示两条路径的连接概率较低（0.25和0.315）。

有什么方法可以找到最大化产品的路径吗？ 谢谢

Answer 1

您正在使用最短路径算法来获得最长的路径。所以反转权重是必要的。同时你想最大化产品而不是总和。结合 -

x<-get.shortest.paths(G,1,4, weights=-log(E(G)$weight), output="epath")[[1]] 
E(G)[x] 
prod(E(G)$weight[x])