Interpolating between Random Walks and Shortest Paths: a Path Functional Approach

Abstract. General models of network navigation must contain a deter-ministic or drift component, encouraging the agent to follow routes of least cost, as well as a random or diffusive component, enabling free wan-dering. This paper proposes a thermodynamic formalism involving two path functionals, namely an energy functional governing the drift and an entropy functional governing the diffusion. A freely adjustable param-eter, the temperature, arbitrates between the conflicting objectives of minimising travel costs and maximising spatial exploration. The theory is illustrated on various graphs and various temperatures. The resulting optimal paths, together with presumably new associated edges and nodes centrality indices, are analytically and numerically investigated