Optimal network topologies for local search with congestion

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.

• Publication year

  2002

• Venue

  Physical Review Letters

• Publication date

  2002-06-21

• Fields of study

  Sociology, Physics, Computer Science, Medicine

• Identifiers
  DOI 10.1103/PhysRevLett.89.248701arXiv cond-mat/0206410PMID 12484988
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Probability, Statistics and Queueing Theory with Computer Science Applications

  2014cited by this paper
• Γ and B

  2004cited by this paper
• Identity and Search in Social Networks

  2002cited by this paper
• Dynamical properties of model communication networks.

  2002cited by this paper
• Search in Power-Law Networks

  2001cited by this paper
• Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality.

  2000cited by this paper
• Navigation in a small world

  2000cited by this paper
• Classes of small-world networks.

  2000cited by this paper
• Communication in networks with hierarchical branching.

  2000cited by this paper
• Emergence of scaling in random networks

  1999cited by this paper
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• Traveling salesman problem and Tsallis statistics.

  1995cited by this paper
• Probability, statistics and queueing theory - with computer science applications (2. ed.)

  1990cited by this paper
• Nature (London

  1975cited by this paper
• Invention in the Industrial Research Laboratory

  1963cited by this paper
• THE QUARTERLY JOURNAL OF ECONOMICS

  year unknowncited by this paper

• China leads scientific trends; the West launches new ones

  2026cites this paper
• Latent space-based network analysis for brain–behavior linking in neuroimaging

  2025cites this paper
• Mapping the multiplex structure of global liner shipping: Connectivity profiles and competitive positioning of carriers

  2025cites this paper
• Targeted Avoidance in Complex Networks.

  2025cites this paper
• Novel phase transition on charging networks of electric vehicles

  2025cites this paper
• Coarse-graining network flow through statistical physics and machine learning

  2025cites this paper
• Slower searching yields higher efficiency: A case study of taxi drivers

  2025cites this paper
• Understanding route choice behaviors' impact on traffic throughput in a dynamic transportation network

  2024cites this paper
• Rail Transit Networks and Network Motifs: A Review and Research Agenda

  2024cites this paper
• Sidewalk networks: Review and outlook

  2023cites this paper
• Fracture network flow prediction with uncertainty using physics-informed graph features

  2023cites this paper
• Inference-based statistical network analysis uncovers star-like brain functional architectures for internalizing psychopathology in children

  2023cites this paper
• Efficient Routing in Manet AdHoc Networks Using Metaheuristic Optimization Algorithm

  2023cites this paper
• Optimizing the geometry of transportation networks in the presence of congestion.

  2023cites this paper
• Multi-Objective Optimization of Transport Processes on Complex Networks

  2023cites this paper
• Identifying influential nodes by leveraging redundant ties

  2023cites this paper
• Motif analysis of urban rail transit network

  2023cites this paper
• Traffic dynamics on community networks with heterogeneity

  2022cites this paper
• Network formation with NIMBY constraints

  2022cites this paper
• Hitting Times of Random Walks on Edge Corona Product Graphs

  2022cites this paper
• Modeling congestion considering sequential coupling applications: A network-cell-based method

  2022cites this paper
• Key Repairing Node Identification in Double-Layer Logistic Networks

  2022cites this paper
• A link model approach to identify congestion hotspots

  2022cites this paper
• Quantifying navigation complexity in transportation networks

  2022cites this paper
• An Improved Optimal Routing Strategy on Scale-Free Networks

  2022cites this paper
• Enhancing traffic capacity of two-layer networks by link deletion

  2021cites this paper
• Towards understanding network topology and robustness of logistics systems

  2021cites this paper
• Emergence of spatial transitions in urban congestion dynamics

  2021cites this paper
• A sustainable strategy for Open Streets in (post)pandemic cities

  2021cites this paper
• The self-adaptive routing strategy to alleviate packet loss in finite buffer networks

  2021cites this paper
• Synthetic criticality in cellular brains

  2021cites this paper
• Enhance the Transfer Capacity of Multiplex Networks

  2021cites this paper
• Guiding propagation to localized target nodes in complex networks.

  2021cites this paper
• Factors affecting congestion-aware routing in complex networks

  2021cites this paper
• Network topology and robustness of Physical Internet

  2021cites this paper
• NC-MOPSO: Network centrality guided multi-objective particle swarm optimization for transport optimization on networks

  2020cites this paper
• Multiple abrupt phase transitions in urban transport congestion

  2020cites this paper
• Hitting Times for Random Walks on Sierpiński Graphs and Hierarchical Graphs

  2020cites this paper
• Delivering capacity allocation strategy for traffic dynamics on scale-free networks

  2020cites this paper
• Small-World Regular Networks for Communication

  2020cites this paper
• NC-MOPSO: A network centrality guided multi-objective particle swarm optimization for transport optimization on networks

  2020cites this paper
• Impact of colored motif characteristics on the survivability of passenger airline networks in China

  2020cites this paper
• Engineering self-organized criticality in living cells

  2020cites this paper
• An efficient improved routing strategy for multilayer networks

  2020cites this paper
• Network extraction by routing optimization

  2020cites this paper
• Hybrid traffic dynamics on coupled networks

  2019cites this paper
• Traffic dynamics on two-layer multiplex networks with limited queue resource

  2019cites this paper
• Minimizing Multicast Routing Delay in Multiple Multicast Trees With Shared Links for Smart Grid

  2019cites this paper
• Enhancing the robustness of a multiplex network leads to multiple discontinuous percolation transitions.

  2019cites this paper
• Multiplex PageRank in Multilayer Networks Considering Shunt

  2019cites this paper
• Low-Mean Hitting Time for Random Walks on Heterogeneous Networks

  2019cites this paper
• Traffic-driven epidemic spreading and its control strategies

  2019cites this paper
• Centralities for networks with consumable resources

  2019cites this paper
• End user–oriented node resource allocation: An application‐based method

  2019cites this paper
• Surprising combinations of research contents and contexts are related to impact and emerge with scientific outsiders from distant disciplines

  2019cites this paper
• Routing optimization considering real-time traffic condition and travel distance

  2019cites this paper
• Explosive phenomena in complex networks

  2019cites this paper
• Customer mobility and congestion in supermarkets

  2019cites this paper
• A new metric to quantify influence of nodes in social networks

  2019cites this paper
• Multi-priority routing algorithm based on source node importance in complex networks

  2019cites this paper
• A maximum algebraic connectivity increment edge-based strategy for capacity enhancement in scale-free networks

  2019cites this paper
• Centrality in Networks: Finding the Most Important Nodes

  2019cites this paper
• Congestion Avoidance on Networks Using Independent Memory Information

  2019cites this paper
• An optimal routing strategy for transport networks with minimal transmission cost and high network capacity

  2019cites this paper
• Effect of heterogeneous weights on the average trapping time and two types of random walks in weighted directed networks

  2019cites this paper
• Generalised thresholding of hidden variable network models with scale-free property

  2019cites this paper
• Transportation dynamics on networks of heterogeneous mobile agents

  2019cites this paper
• Local routing protocols performance for computer virus elimination in complex networks

  2019cites this paper
• Effective use of congestion in complex networks

  2018cites this paper
• Identifying influential nodes in complex networks based on Neighbours and edges

  2018cites this paper
• An efficient routing strategy for traffic dynamics on two-layer complex networks

  2018cites this paper
• Implementing beneficial prioritization of traffic flow in complex networks

  2018cites this paper
• A spectrum of routing strategies for brain networks

  2018cites this paper
• Network capacity enhancement with various link rewiring strategies

  2018cites this paper
• Novel Multiplex PageRank in Multilayer Networks

  2018cites this paper
• Time-varying Network Modeling and its Optimal Routing Strategy

  2018cites this paper
• Mobility and Congestion in Dynamical Multilayer Networks with Finite Storage Capacity.

  2018cites this paper
• Transitions in spatial networks

  2018cites this paper
• Suppress traffic-driven epidemic spreading in weighted network

  2018cites this paper
• Models for Networks with Consumable Resources: Applications to Smart Cities

  2018cites this paper
• Generalized synchronization in a conservative and nearly conservative systems of star network.

  2018cites this paper
• Framework for Anonymous Secure Data Transfer in Vehicular Ad-Hoc Networks

  2018cites this paper
• Centrality ranking in multiplex networks using topologically biased random walks

  2018cites this paper
• Structural Properties of multilayer Software Networks: a Case Study in Tomcat

  2018cites this paper
• Decentralized navigation of multiple packages on transportation networks

  2018cites this paper
• Effect of shortest path multiplicity on congestion of multiplex networks

  2018cites this paper
• Improving the throughput of transportation networks with a time-optimization routing strategy

  2018cites this paper
• Optimal topologies for maximizing network transmission capacity

  2018cites this paper
• Selective epidemic vaccination under the performant routing algorithms

  2018cites this paper
• Efficient edge rewiring strategies for enhancement in network capacity

  2018cites this paper
• Information transmission on hybrid networks

  2017cites this paper
• Check-in based routing strategy in scale-free networks

  2017cites this paper
• Traffic congestion and the lifetime of networks with moving nodes.

  2017cites this paper
• Hopping in the Crowd to Unveil Network Topology.

  2017cites this paper
• Effective hybrid link-adding strategy to enhance network transport efficiency for scale-free networks

  2017cites this paper
• Statistical Modeling of the Default Mode Brain Network Reveals a Segregated Highway Structure

  2017cites this paper
• Optimal topology to minimizing congestion in connected communication complex network

  2017cites this paper
• Symmetries in the time-averaged dynamics of networks: Reducing unnecessary complexity through minimal network models.

  2017cites this paper
• Effects of packet retransmission with finite packet lifetime on traffic capacity in scale-free networks

  2017cites this paper
• Routing optimization in networks based on traffic gravitational field model

  2017cites this paper