ИЗОБРАЖЕНИЕ В R: Найдите путь между вершинами, который максимизирует произведение атрибутов ребер.

Мне нужно найти способ найти путь между двумя вершинами, который максимизирует произведение атрибутов ребра. В моем случае атрибут края — это вероятность соединения. Предположим, я хочу найти путь с максимальной вероятностью между вершинами 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).

Есть ли способ найти путь, который максимизирует продукт??? спасибо


r probability igraph shortest-path
person Oritteropus    schedule 16.04.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вы используете алгоритм кратчайшего пути, чтобы получить самый длинный путь. Поэтому инвертировать веса необходимо. В то же время вы хотите максимизировать произведение, а не сумму. Объединение -

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