Phys. Rev. Lett. 108, 208701 (2012) [5 pages]Competition for Shortest Paths on Sparse GraphsReceived 1 February 2012; published 14 May 2012 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 URL:
http://link.aps.org/doi/10.1103/PhysRevLett.108.208701
DOI:
10.1103/PhysRevLett.108.208701
PACS:
89.75.Hc, 02.50.-r, 05.20.-y, 89.20.-a
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.