Competition for shortest paths on sparse graphs

Abstract

Optimal paths connecting randomly selected network nodes and fixed routers are studied analytically in the presence of a nonlinear overlap cost that penalizes congestion. Routing becomes more difficult as the number of selected nodes increases and exhibits ergodicity breaking in the case of multiple routers. The ground state of such systems reveals nonmonotonic complex behaviors in average path length and algorithmic convergence, depending on the network topology, and densities of communicating nodes and routers. A distributed linearly scalable routing algorithm is also devised. © 2012 American Physical Society.

Publication DOI: https://doi.org/10.1103/PhysRevLett.108.208701
Divisions: College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
Additional Information: © APS
Uncontrolled Keywords: Physics and Astronomy(all)
Publication ISSN: 1079-7114
Last Modified: 03 Jan 2024 08:05
Date Deposited: 25 Jun 2013 14:09
Full Text Link: http://link.aps ... Lett.108.208701
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
PURE Output Type: Article
Published Date: 2012-05-14
Authors: Yeung, Chi
Saad, David (ORCID Profile 0000-0001-9821-2623)

Download

[img]

Version: Accepted Version


Export / Share Citation


Statistics

Additional statistics for this record