IGRAPH IN R:找到顶点之间的路径，以最大化边缘属性的乘积 [英] IGRAPH IN R: Find the path between vertices that maximizes the product of edge attributes

问题描述

我需要找到一种方法来找到两个顶点之间的路径，以最大化边缘属性的乘积.在我的情况下，edge属性是连接的概率. 假设在下面的示例中，我想找到顶点1和顶点4之间的最大概率路径:

I need to find a way to find the path between two vertices that maximizes the product of edge attributes. In my case the edge attribute is a probability of connection. Let's assume I want to find the maximum probability path between the vertex 1 and 4 in the following example:

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

In this example, the path which maximizes the connection is through the vertex 5, in fact the product of the probabilities is equal to 0.36 (0.6*0.6). Shortest path function seems to gives priority on the basis of the sum of the attributes, but not the product. In fact, in the example above, either I use probabilities or the inverse of probabilities, it suggests two paths whose probability of connection is lower (0.25 and 0.315).

有什么方法可以找到使产品最大化的途径吗??? 谢谢

Is there any way to find the path which maximizes the product??? thanks

推荐答案

您正在使用最短路径算法来获取最长路径.因此，权重反转是必要的.同时，您想最大化乘积而不是求和.结合-

You are using shortest path algorithm to get longest path. So inverting weights is necessary. At the same time you want to maximize product and not sum. Combining -

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

这篇关于IGRAPH IN R:找到顶点之间的路径，以最大化边缘属性的乘积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！