Related Experiment Videos
Optimal network topologies for local search with congestion
R Guimerà1, A Díaz-Guilera, F Vega-Redondo
1Departament d'Enginyeria Química, Universitat Rovira i Virgili, 43007 Tarragona, Spain.
Physical Review Letters
|December 18, 2002
Summary
We developed a new method to improve searchability in decentralized complex networks, considering parallel search congestion. Optimal network structures depend on the number of parallel searches, favoring starlike or homogeneous-isotropic configurations.
Area of Science:
- Computer Science
- Network Theory
- Algorithmic Complexity
Background:
- Decentralized complex networks pose significant searchability challenges.
- Congestion effects from parallel searches further complicate network performance.
- Understanding these issues is crucial for computer science, economics, and sociology.
Purpose of the Study:
- To present a unified formalism for analyzing searchability and congestion in decentralized networks.
- To derive expressions for average search costs under varying congestion levels.
- To identify optimal network structures for local search algorithms.
Main Methods:
- Developed a novel mathematical formalism to model search and congestion simultaneously.
- Derived analytical expressions for average search costs.
- Analyzed network structures using a local search algorithm.
Main Results:
- The formalism successfully accounts for both searchability and congestion effects.
- Expressions for average search cost were obtained, with and without congestion.
- Identified two classes of optimal network structures: starlike and homogeneous-isotropic.
Conclusions:
- Network structure significantly impacts search efficiency in decentralized systems.
- Starlike networks are optimal for low numbers of parallel searches.
- Homogeneous-isotropic networks are optimal for high numbers of parallel searches.