Date: 11:30am, November 2, 2017
Location: CS Conference Room
Speaker: Daniel Ratton Figueiredo, Department of Computer and Systems Engineering (PESC/COPPE) The Federal University of Rio de Janeiro (UFRJ), Brazil
We address this problem in the context of directed graphs where path traversals between a source/destination pair play the role of function and edge weighs the role of structure. Edge reinforced biased random walks embodies the system dynamics, reinforcing paths according to their corresponding quality, and thus biasing future paths. Under very mild conditions, we show that biased random walks create structure such that in the limit only optimal paths are traversed. We also characterize the transient regime showing that the probability to traverse non-optimal paths decays according to a power-law. However, we also provide examples where optimal paths may not emerge, illustrating the importance of the definition of optimal paths. For example, while shortest paths always emerge, longest paths may not always emerge.
Last, beyond applying the model to different scenarios, we believe the proposed model and results can be of interest to domains such as reinforcement learning and optimization as it provides a new framework and tool (Polya urns) to investigate stochastic convergence.