2

我需要找到一种方法来找到最大化边缘属性乘积的两个顶点之间的路径。在我的例子中，边缘属性是连接的概率。假设我想在以下示例中找到顶点 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）。

有没有办法找到最大化产品的路径？？？谢谢

4

1 回答 1

2

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

x<-get.shortest.paths(G,1,4, weights=-log(E(G)$weight), output="epath")[[1]]
E(G)[x]
prod(E(G)$weight[x])
于 2013-04-16T09:54:22.960 回答