Optimal network topologies for local search with congestion

By Roger Guimerà, Alex Arenas, Albert Díaz-Guilera, Fernando Vega-Redondo, Antonio Cabrales. Physical Review Letters, 2002

502 citations recorded by the source corpus.

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.

Subfields: Management Science and Operations Research, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/89e28ba4ff335b2c56204da8f953a6e97fc1d846

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Statistical and Nonlinear Physics

Citations in the corpus

Communication and influence (2015, background): “The works of Bolton and Dewatripont (1994), Van Zandt (1999a), Garicano (2000), Guimerà et al. (2002), and Dodds et al. (2003) highlight the importance of hierarchies, and more general network structures, to diminish the costs related to processing information that flows through the network of…”
Identifying influential nodes in complex networks (2012, background): “Betweenness is, in some sense, a measure of the influence of a node over the information spread through the network or the expected load of a node in a transportation network [15,16].”
Critical phenomena in complex networks (2007, background): “For more detail see books and reviews of Albert and Barabási (2002), Dorogovtsev and Mendes (2002, 2003), Newman (2003a), Bollobás and Riordan (2003), Pastor-Satorras and Vespignani (2004), Boccaletti et al.”
The H-index of a network node and its relation to degree and coreness (2016, background): “Betweenness is, in some sense, a measure of the inﬂuence of a node in terms of its role in spreading information 20,56 .”
Spatial Networks (2010, background): “[148] studied networks with minimal search cost and found two classes of networks: star-like and homogeneous networks.”
Characterization of complex networks: A survey of measurements (2005, methodology): “ a speciﬁc algor ithm. The effective distance between two vertices is thus generally larger than the shortest distance, and dependent on the algorithm used for navigation as well as network structure [68]. 4.2 Vulnerability In infrastructure networks (like WWW, the Internet, energy supply, etc), it ”