Interpolating between Random Walks and Optimal transportation routes

MLG and Big Data Seminar

Event Speaker: Guillaume Guex
Event Place: Salle Paul Otlet
Event Date: 10/26/2016 - 14:00

In recent articles about graphs, different models proposed a formalism to find a type of path between two nodes, the source and the target, at crossroads between the shortest-path and the random-walk path. These models include a freely adjustable parameter, allowing to tune the behavior of the path towards randomized movements or direct routes. In this talk, a natural generalization of these models is presented, namely a model with multiple sources and targets. In this context, source nodes can be viewed as locations with a supply of a certain good (e.g. people, money, information) and target nodes as locations with a demand of the same good. An algorithm is constructed to display the flow of goods in the network between sources and targets. With again a freely adjustable parameter, this flow can be tuned to follow routes of minimum cost, thus displaying the flow in the context of the optimal transportation problem or, by contrast, a random flow, known to be similar to the electrical current flow if the random-walk is reversible. Moreover, a source-target coupling can be retrieved from this flow, offering an optimal assignment to the transportation problem. This algorithm is described in the first part of the talk and then illustrated with case studies