Optimal Network Topologies for Local Search with Congestion Export

@article{Guimera_PRL02, abstract = {The problem of searchability in decentralized complex networks is of great importance in computer science; economy; and sociology. We present a formalism that is able to cope simultaneously with the problem of search and the congestion effects that arise when parallel searches are performed; and we obtain expressions for the average search cost both in the presence and the absence of congestion. This formalism is used to obtain optimal network structures for a system using a local search algorithm. It is found that only two classes of networks can be optimal: starlike configurations; when the number of parallel searches is small; and homogeneous-isotropic configurations; when it is large.}, author = {Guimer\`{a}, R. and D\'{\i}az-Guilera, A. and Vega-Redondo, F. and Cabrales, A. and Arenas, A.}, citeulike-article-id = {3798405}, citeulike-linkout-0 = {http://dx.doi.org/10.1103/PhysRevLett.89.248701}, citeulike-linkout-1 = {http://link.aps.org/abstract/PRL/v89/i24/e248701}, citeulike-linkout-2 = {http://link.aps.org/pdf/PRL/v89/i24/e248701}, day = {21}, doi = {10.1103/PhysRevLett.89.248701}, journal = {Physical Review Letters}, keywords = {congestion, network, physics, theory}, month = {Nov}, number = {24}, pages = {248701}, posted-at = {2008-12-16 17:36:17}, priority = {2}, publisher = {American Physical Society}, title = {Optimal Network Topologies for Local Search with Congestion}, url = {http://dx.doi.org/10.1103/PhysRevLett.89.248701}, volume = {89}, year = {2002} }

TY - JOUR ID - Guimera_PRL02 L3 - citeulike-article-id:3798405 N2 - The problem of searchability in decentralized complex networks is of great importance in computer science; economy; and sociology. We present a formalism that is able to cope simultaneously with the problem of search and the congestion effects that arise when parallel searches are performed; and we obtain expressions for the average search cost both in the presence and the absence of congestion. This formalism is used to obtain optimal network structures for a system using a local search algorithm. It is found that only two classes of networks can be optimal: starlike configurations; when the number of parallel searches is small; and homogeneous-isotropic configurations; when it is large. IS - 24 JF - Physical Review Letters EP - 248701 TI - Optimal Network Topologies for Local Search with Congestion PB - American Physical Society VL - 89 SP - 248701 KW - congestion KW - network KW - physics KW - theory AU - Guimerà, R AU - Díaz-Guilera, A AU - Vega-Redondo, F AU - Cabrales, A AU - Arenas, A PY - 2002/Nov/21/ UR - http://dx.doi.org/10.1103/PhysRevLett.89.248701 ER -