CS/EE Networking Seminar: From Random to Optimal: Emergence of Optimal Paths through Reinforced Random Walks

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

Abstract: The co-evolution of structure and function is a fundamental and challenging problem in various systems due in part to the their intrinsic interdependent nature: structure constrains function, function demands structure. While clever algorithms can sometimes efficiently determine the optimal function/structure combination, the emergence of optimality through simple iterated dynamics finds application in biological and social systems.

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.  

Biography: Daniel Ratton Figueiredo received a BS cum laude degree in Computer Science and MSc degree in Computer and Systems Engineering from the Federal University of Rio de Janeiro (UFRJ) Brazil, in 1996 and 1999, respectively. He received a MSc and PhD degrees in Computer Science from the University of Massachusetts Amherst (UMass) in 2005. He worked as a post-doc researcher at the Swiss Federal Institute of Technology, Lausanne (EPFL). In 2007, he joined the Department of Computer and Systems Engineering (PESC/COPPE) at the Federal University of Rio de Janeiro (UFRJ), Brazil where he currently holds an Associate Professor position. He has a Research Fellowship granted by CNPq (since 2009) and is member of the Young Scientists Program granted by FAPERJ (since 2010), and is currently a Fulbright Scholar visiting Columbia University. His main interests are in Network Science, in particular modeling system dynamics in networks.
Hosted by Professor Dan Rubenstein

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University