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])