Optimal network topologies for local search with congestion
arXiv:cond-mat/0206410 · doi:10.1103/PhysRevLett.89.248701
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 obtain expressions for the average search cost--written in terms of the search algorithm and the topological properties of the network--both in presence and abscence 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: star-like configurations, when the number of parallel searches is small, and homogeneous-isotropic configurations, when the number of parallel searches is large.
4 pages. Final version accepted in PRL
References in corpus (5)
Cited by in corpus (141)
- The structure and dynamics of multilayer networks
- Link Prediction in Complex Networks: A Survey
- Spatial Networks
- Characterization of complex networks: A survey of measurements
- Critical phenomena in complex networks
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Missing and spurious interactions and the reconstruction of complex networks
- Cascade control and defense in complex networks
- The physics of spreading processes in multilayer networks
- Efficient routing on complex networks
- Random Walks on Multiplex Networks
- Centrality in Interconnected Multilayer Networks
- Entangled networks, synchronization, and optimal network topology
- Optimal routing on complex networks
- Integrating static and dynamic information for routing traffic
- Explosive Phenomena in Complex Networks
- Traffic-driven Epidemic Spreading in Finite-size Scale-Free Networks
- Designing optimal transport networks
- Congestion induced by the structure of multiplex networks
- Congestion phenomena on complex networks
- Exploring complex networks by walking on them
- Communication Bottlenecks in Scale-Free Networks
- A spectrum of routing strategies for brain networks
- Network Landscape from a Brownian Particle's Perspective
- Traffic congestion in interconnected complex networks
- Transport on Complex Networks: Flow, Jamming and Optimization
- Random walk centrality in interconnected multilayer networks
- Efficient routing on scale-free networks based on local information
- Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
- On the universality of the scaling of fluctuations in traffic on complex networks
- Scaling breakdown in flow fluctuations on complex networks
- Transport optimization on complex networks
- Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that
- Optimal Traffic Networks
- An adaptive routing strategy for packet delivery in complex networks
- Synchronization in weighed scale-free networks with degree-degree correlation
- Removing spurious interactions in complex networks
- Traffic optimization in transport networks based on local routing
- Random walk centrality for temporal networks
- Effect of congestion costs on shortest paths through complex networks
- Self-avoiding walks on scale-free networks
- Congestion and decongestion in a communication network
- An efficient approach of controlling traffic congestion in scale-free networks
- Efficient routing strategies in scale-free networks with limited bandwidth
- Synchronization in Weighted Uncorrelated Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency
- Statistical mechanics of topological phase transitions in networks
- Impact of community structure on information transfer
- Mobility and Congestion in Dynamical Multilayer Networks with Finite Storage Capacity
- Efficient routing on multilayered communication networks
- Congestion-gradient driven transport on complex networks
- Urban traffic from the perspective of dual graph
- A model to identify urban traffic congestion hotspots in complex networks
- Interplay between function and structure in complex networks
- Suppressing traffic-driven epidemic spreading by edge-removal strategies
- Traffic dynamics in scale-free networks with limited packet-delivering capacity
- Steady state and mean recurrence time for random walks on stochastic temporal networks
- Comprehensive routing strategy on multilayer networks
- Networking - A Statistical Physics Perspective
- Collectively optimal routing for congested traffic limited by link capacity
- Large-scale structural organization of social networks
- Congestion diffusion and decongestion strategy in networked traffic
- Centrality scaling in large networks
- Modular networks emerge from multiconstraint optimization
- The effect of bandwidth in scale-free network traffic
- A statistical mechanics approach for scale-free networks and finite-scale networks
- Load distribution in weighted complex networks
- Local Empathy provides Global Minimization of Congestion in Communication Networks
- Random Multi-Hopper Model. Super-Fast Random Walks on Graphs
- Comment on ``Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality"
- A minimal model for congestion phenomena on complex networks
- Critical behaviour in charging of electric vehicles
- Optimization in Networks
- Walks on Apollonian networks
- Effect of edge removal on topological and functional robustness of complex networks
- Traffic-driven epidemic spreading in correlated networks
- Effect of shortest path multiplicity on congestion of multiplex networks
- Preferential Behaviour and Scaling in Diffusive Dynamics on Networks
- Optimized network structure and routing metric in wireless multihop ad hoc communication
- Hopping in the crowd to unveil network topology
- Suppressing traffic-driven epidemic spreading by adaptive routing strategy
- Suppressing traffic-driven epidemic spreading by use of the efficient routing protocol
- Optimal transport on wireless networks
- Distributed flow optimization and cascading effects in weighted complex networks
- Multiple abrupt phase transitions in urban transport congestion
- Optimization of transport protocols with path-length constraints in complex networks
- Network synchronization: Optimal and Pessimal Scale-Free Topologies
- Controlling congestion on complex networks: fairness, efficiency and network structure
- Scaling behavior of an artificial traffic model on scale-free networks
- Network extraction by routing optimization
- Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps
- Kinetic growth walks on complex networks
- Exploring complex networks by means of adaptive walkers
- Jamming and Correlation Patterns in Traffic of Information on Sparse Modular Networks
- Effects of reciprocity on random walks in weighted networks
- Random walks on networks: cumulative distribution of cover time
- Diffusive capture processes for information search
- On cost-effective communication network designing
- Customer mobility and congestion in supermarkets
- Diffusion-annihilation proecesses in weighted scale-free networks with identical degree sequence
- The Gradient Mechanism in a Communication Network
- Critical behavior and correlations on scale-free small-world networks. Application to network design
- Optimal transport on supply-demand networks
- Information transfer in community structured multiplex networks
- Complex Grid Computing
- Kinetic-growth self-avoiding walks on small-world networks
- Enhancing the robustness of a multiplex network leads to multiple discontinuous percolation transitions
- Balancing building and maintenance costs in growing transport networks
- Geographical networks stochastically constructed by a self-similar tiling according to population
- Enhancing Transport Efficiency by Hybrid Routing Strategy
- Preferential Detachment in Broadcast Signaling Networks: Connectivity and Cost Trade-off
- Can car density in a two-lane section depend on the position of the latter in a single-lane road?
- Binary dynamics on star networks under external perturbations
- Emergence of spatial transitions in urban congestion dynamics
- Modeling and Performance Studies of Data Communication Networks using Dynamic Complex Networks
- Transitions in spatial networks
- Traffic-driven epidemic spreading on scale-free networks with tunable degree distribution
- Integrating fluctuations into distribution of resources in transportation networks
- Diffusion Processes on Small-World Networks with Distance-Dependent Random-Links
- Centralities for Networks with Consumable Resources
- Theoretical approach and impact of correlations on the critical packet generation rate in traffic dynamics on complex networks
- A link model approach to identify congestion hotspots
- Information transmission on hybrid networks
- On the decentralized navigation of multiple packages on transportation networks
- Quantifying navigation complexity in transportation networks
- Role of connectivity in congestion and decongestion in networks
- The effect of network structure on phase transitions in queuing networks
- Generalised thresholding of hidden variable network models with scale-free property
- Link power coordination for energy conservation in complex communication networks
- Networks and Our Limited Information Horizon
- Network modules help the identification of key transport routes, signaling pathways in cellular and other networks
- Temporal-varying failures of nodes in networks
- Rare events statistics of random walks on networks: localization and other dynamical phase transitions
- Analytically solvable processes on networks
- Temporal Correlations of Local Network Losses
- Mean First Hitting Time of Searching for Path Through Random Walks on Complex Networks
- A scientific understanding of network designing
- Controlling Communication Field of Complex Networks by Transformation Method
- Synchronization in Network Structures: Entangled Topology as Optimal Architecture for Network Design
- Symbolic walk in regular networks
- Random Walks on Complex Networks
- Complex Design Networks: Structure and Dynamics