Networking - A Statistical Physics Perspective
arXiv:1110.2931 · doi:10.1088/1751-8113/46/10/103001
Abstract
Efficient networking has a substantial economic and societal impact in a broad range of areas including transportation systems, wired and wireless communications and a range of Internet applications. As transportation and communication networks become increasingly more complex, the ever increasing demand for congestion control, higher traffic capacity, quality of service, robustness and reduced energy consumption require new tools and methods to meet these conflicting requirements. The new methodology should serve for gaining better understanding of the properties of networking systems at the macroscopic level, as well as for the development of new principled optimization and management algorithms at the microscopic level. Methods of statistical physics seem best placed to provide new approaches as they have been developed specifically to deal with non-linear large scale systems. This paper aims at presenting an overview of tools and methods that have been developed within the statistical physics community and that can be readily applied to address the emerging problems in networking. These include diffusion processes, methods from disordered systems and polymer physics, probabilistic inference, which have direct relevance to network routing, file and frequency distribution, the exploration of network structures and vulnerability, and various other practical networking applications.
arXiv comment(Review article) 71 pages, 14 figures
References in corpus (99)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Epidemic spreading in scale-free networks
- Assortative mixing in networks
- Catastrophic cascade of failures in interdependent networks
- Functional cartography of complex metabolic networks
- Random graphs with arbitrary degree distributions and their applications
- Synchronization in complex networks
- The spread of epidemic disease on networks
- Message Passing Algorithms for Compressed Sensing
- Resilience of the Internet to random breakdowns
- Critical phenomena in complex networks
- Cascade-based attacks on complex networks
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Self-similarity of complex networks
- Dynamical and correlation properties of the Internet
- Loopy Belief Propagation for Approximate Inference: An Empirical Study
- Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
- Search in Power-Law Networks
- Community structure in directed networks
- Epidemics and percolation in small-world networks
- Scale-free topology of e-mail networks
- The Bethe lattice spin glass revisited
- Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition
- Cascade control and defense in complex networks
- New Model of Internet Topology Using k-shell Decomposition
- MEDUSA - New Model of Internet Topology Using k-shell Decomposition
- Generation of uncorrelated random scale-free networks
- Thresholds for epidemic spreading in networks
- Robustness of a Network of Networks
- Optimal network topologies for local search with congestion
- Suppressing cascades of load in interdependent networks
- Epidemic spreading in correlated complex networks
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Communication in networks with hierarchical branching
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Epidemic threshold in structured scale-free networks
- Optimal search strategies for hidden targets
- Cut-offs and finite size effects in scale-free networks
- Phase Transitions in the Coloring of Random Graphs
- Skeleton and fractal scaling in complex networks
- Modularity and Extreme Edges of the Internet
- Critical load and congestion instabilities in scale-free networks
- Coloring random graphs
- Survey propagation: an algorithm for satisfiability
- Statistical physics-based reconstruction in compressed sensing
- LinkRank: Finding communities in directed networks
- Path finding strategies in scale-free networks
- A Landscape Analysis of Constraint Satisfaction Problems
- First-passage times for random walks in bounded domains
- Transport in weighted networks: Partition into superhighways and roads
- A typical reconstruction limit of compressed sensing based on Lp-norm minimization
- Hierarchy Measures in Complex Networks
- Structure, Scaling and Phase Transition in the Optimal Transport Network
- Structure of shells in complex networks
- Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
- The Nishimori line and Bayesian Statistics
- Scale-free trees: the skeletons of complex networks
- Polynomial iterative algorithms for coloring and analyzing random graphs
- Loopy Belief Propagation as a Basis for Communication in Sensor Networks
- How to Compute Loop Corrections to Bethe Approximation
- Random walks on complex trees
- Random spread on the family of small-world networks
- Scaling Properties of Random Walks on Small-World Networks
- Replicated Transfer Matrix Analysis of Ising Spin Models on `Small World' Lattices
- Loops structure of the Internet at the Autonomous System Level
- Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model
- Statistical Mechanics of Steiner trees
- Spin Glass Phase Transition on Scale-Free Networks
- The interplay of microscopic and mesoscopic structure in complex networks
- On the number of circuits in random graphs
- Random Graph Coloring - a Statistical Physics Approach
- The Competition for Shortest Paths on Sparse Graphs
- Network inference using asynchronously updated kinetic Ising Model
- Scaling and Universality in Continuous Length Combinatorial Optimization
- Partition function loop series for a general graphical model: free energy corrections and message-passing equations
- Circuits in random graphs: from local trees to global loops
- Impact of hierarchical modular structure on ranking of individual nodes in directed networks
- A rigorous analysis of the cavity equations for the minimum spanning tree
- Equilibration through local information exchange in networks
- Inference and Optimization of Real Edges on Sparse Graphs - A Statistical Physics Perspective
- Finding long cycles in graphs
- Tracing the Evolution of Physics on the Backbone of Citation Networks
- Branching fraction and CP-violation charge asymmetry measurements for B-meson decays to eta K+-, etapi+-, eta'K, eta'pi+-, omega K, and omegapi+-
- Random walks on networks: cumulative distribution of cover time
- Percolation and Loop Statistics in Complex Networks
- Minimizing Unsatisfaction in Colourful Neighbourhoods
- Optimal Resource Allocation in Random Networks with Transportation Bandwidths
- Optimal Location of Sources in Transportation Networks
- Next nearest neighbour Ising models on random graphs
- Extremal Properties of Complex Networks
- Random Walks in Local Dynamics of Network Losses
- Self-Organization of Balanced Nodes in Random Networks with Transportation Bandwidths
- Random Walks on Complex Networks
Cited by in corpus (11)
- Percolation on complex networks: Theory and application
- Quasi-equilibrium in glassy dynamics: an algebraic view
- Solving the undirected feedback vertex set problem by local search
- The average number of distinct sites visited by a random walker on random graphs
- Agent-Based Models in Social Physics
- Designing optimal networks for multi-commodity transport problem
- Multicommodity routing optimization for engineering networks
- Cohesive urban bicycle infrastructure design through optimal transport routing in multilayer networks
- Complete Visitation Statistics of 1d Random Walks
- Infrastructure adaptation and emergence of loops in network routing with time-dependent loads
- Learning the optimally coordinated routes from the statistical mechanics of polymers