Как я могу умножить взвешенную матрицу shorttest_path на другой атрибут веса ребра? - PullRequest
0 голосов
/ 03 июля 2019

У меня есть сеть в igraph с двумя атрибутами веса ребра.Одним из них является время в пути между вершинами сети.Второе - это число людей, путешествующих между каждой парой вершин.

Я вычислил матрицу кратчайшего пути с traveltime в качестве весов ребер.Теперь я хочу умножить матрицу на количество людей, путешествующих между вершинами.

edgelist выглядит так:

from  to  traveltime   commuters
 2     3      2           10
 4     5      3           20
 1     2      1           12
 5     6      4           14

Мой подход пока:

sp<-shortest.paths(mynetwork, v=V(mynetwork) ,to=V(mynetwork), mode="all",weights = edgelist$traveltime)

это дает мне матрицу с временем прохождения между всеми парами вершин

Я бы поступил так:

results <- sapply(sp[,1], function(x){shortest_paths(mynetwork, from = x, to = V(mynetwork)[setdiff(sp[,2],x)])$vpath})

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

Я не могу умножить traveltime x commuters заранее, а затем вычислить shortest.path, потому что dijkstra-algorithm пытается минимизировать дорожные расходы, верно?Выбор маршрута не должен зависеть от количества пассажиров.Выбор маршрута должен зависеть от времени в пути.Так есть ли более простой способ умножить commuters на traveltime в матрице shortest_path?

РЕДАКТИРОВАТЬ:

Прежде всего, спасибо за идеи!Может быть, мне нужно уточнить некоторые моменты:

  1. Чего я хочу достичь?Я хочу вычислить показатель производительности моей сети.Средневзвешенное время в пути пассажиров по кратчайшим маршрутам должно работать как эталон.После вычисления этого теста я хочу удалить границы моей сети и снова вычислить меру.Разница дает мне подсказку, какие края должны быть обработаны по приоритетам.

  2. Какие данные о поездках у меня есть?У меня есть индивидуальный od-data, который состоит из начального и целевого узла.Используя алгоритм shortest_path, я выяснил, какие ребра используются в моей сети для достижения целевого узла.Я знаю, что этот подход имеет некоторые методологические последствия, но он должен подойти для моего исследования.Благодаря этим предположениям у меня есть знания о том, сколько путешествует примерно по краям моей сети.

1 Ответ

0 голосов
/ 05 июля 2019

Вы не можете умножить traveltime на commuters заранее: правильно. Это мешало бы весам кратчайшего пути.

После того, как вы отредактируете, я согласен, что ваши необработанные данные дадут вам хорошее представление о том, сколько и куда путешествует.

Однако я подумал о следующих проблемах:

Сколько пассажиров путешествует в каждом направлении между двумя станциями? Я предполагаю из вашей mode="all", что ваша сеть не является направленной. Должны ли мы считать, что это половина количества пассажиров между двумя станциями, которые движутся в каждом направлении?

Как относиться к общему количеству путешественников?

Если 20 человек - это совокупный путешественник между А и В и 23 человека между В и С, сколько человек прошло между А и С? Я не верю, что после агрегирования ваших индивидуальных do_data $traveltime и $commuters обеспечивает лучшую точность, чем: от 0 до 20 человек .

Что касается фактического вопроса, есть ли более простой вариант умножения пассажиров на время поездки в матрице кратчайшего пути? , или действительно, если вы можете выполнить любую операцию атрибутов ребра по кратчайшим путям В сети я прошу прощения за мой ошибочный ответ и надеюсь, что на этот раз я все понял правильно. Это не красиво и не быстро, но оно делает свою работу:

library(igraph)

# Create random connected graph
g <- erdos.renyi.game(100,150,"gnm", directed=FALSE)
g <- g %>% delete_vertices(degree(g) == 0)
E(g)$traveltime <- sample(3:10, length(E(g)), replace=T)
E(g)$commuters <- sample(20:35, length(E(g)), replace=T)
E(g)$weight <- E(g)$traveltime

# This is uggly, slow, and grose but sure to do what you wish. It calculates
# a matrix of all shortest paths (using the graph-$weight for "friction" in
# the network, and then sums all the $comuters along each registred path)
commuters <- lapply(1:length(V(g)), function(i){
  # It loops the adjacency-matrix.
  # First, this gets the paths which constitute the shortest path from i to
  # every other vertecy.
  paths_from_i <- (shortest_paths(g, i, V(g), 'all', weights=E(g)$traveltime))$vpath
  # Here you can build any per-shortest-path opperation of edge-attributes along
  # each of those paths. In this case we're multiplying the number of commuters
  # with the travelling time for each shortest path.
  sapply(paths_from_i, function(x) sum( E(g)$commuters[x] * E(g)$traveltime[x]) ) 
}
)
# Convert list to matrix: Each value in the matrix is produced by the
# $traveltime * $commuters attributes of all edges in the shortest paths
# between every pair of nodes in the network g.
commute_matrix <- do.call(rbind, commuters)
...