Networking - a statistical physics perspective

Networking encompasses a variety of tasks related to the communication of information on networks; it has a substantial economic and societal impact on 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 requires 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 nonlinear large-scale systems. This review 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. © 2013 IOP Publishing Ltd.

From the physics of interacting polymers to optimizing routes on the London Underground

Optimizing paths on networks is crucial for many applications, ranging from subway traffic to Internet communication. Because global path optimization that takes account of all path choices simultaneously is computationally hard, most existing routing algorithms optimize paths individually, thus providing suboptimal solutions. We use the physics of interacting polymers and disordered systems to analyze macroscopic properties of generic path optimization problems and derive a simple, principled, generic, and distributed routing algorithm capable of considering all individual path choices simultaneously. We demonstrate the efficacy of the algorithm by applying it to: (i) random graphs resembling Internet overlay networks, (ii) travel on the London Underground network based on Oyster card data, and (iii ) the global airport network. Analytically derived macroscopic properties give rise to insightful new routing phenomena, including phase transitions and scaling laws, that facilitate better understanding of the appropriate operational regimes and their limitations, which are difficult to obtain otherwise.

The influence of external forces on a monopolistic market:a statistical physics perspective

DUE TO COPYRIGHT RESTRICTIONS ONLY AVAILABLE FOR CONSULTATION AT ASTON UNIVERSITY LIBRARY AND INFORMATION SERVICES WITH PRIOR ARRANGEMENT

Physics and mathematics of dispersion-managed optical solitons

We review the main physical and mathematical properties of dispersion-managed (DM) optical solitons. Theory of DM solitons can be presented at two levels of accuracy: first, simple, but nevertheless, quantitative models based on ordinary differential equations governing evolution of the soliton width and phase parameter (the so-called chirp); and second, a comprehensive path-average theory that is capable of describing in detail both the fine structure of DM soliton form and its evolution along the fiber line. An analogy between DM soliton and a macroscopic nonlinear quantum oscillator model is also discussed. © 2003 Académie des sciences/Éditions scientifiques et médicales Elsevier SAS. All rights reserved.

Physics-inspired methods for networking and communications

Advances in statistical physics relating to our understanding of large-scale complex systems have recently been successfully applied in the context of communication networks. Statistical mechanics methods can be used to decompose global system behavior into simple local interactions. Thus, large-scale problems can be solved or approximated in a distributed manner with iterative lightweight local messaging. This survey discusses how statistical physics methodology can provide efficient solutions to hard network problems that are intractable by classical methods. We highlight three typical examples in the realm of networking and communications. In each case we show how a fundamental idea of statistical physics helps solve the problem in an efficient manner. In particular, we discuss how to perform multicast scheduling with message passing methods, how to improve coding using the crystallization process, and how to compute optimal routing by representing routes as interacting polymers.

A statistical physics perspective on alignment-independent protein sequence comparison.

Motivation: Within bioinformatics, the textual alignment of amino acid sequences has long dominated the determination of similarity between proteins, with all that implies for shared structure, function, and evolutionary descent. Despite the relative success of modern-day sequence alignment algorithms, so-called alignment-free approaches offer a complementary means of determining and expressing similarity, with potential benefits in certain key applications, such as regression analysis of protein structure-function studies, where alignment-base similarity has performed poorly. Results: Here, we offer a fresh, statistical physics-based perspective focusing on the question of alignment-free comparison, in the process adapting results from “first passage probability distribution” to summarize statistics of ensemble averaged amino acid propensity values. In this paper, we introduce and elaborate this approach.

Coverage versus supply cost in facility location:physics of frustrated spin systems

A comprehensive coverage is crucial for communication, supply, and transportation networks, yet it is limited by the requirement of extensive infrastructure and heavy energy consumption. Here, we draw an analogy between spins in antiferromagnet and outlets in supply networks, and apply techniques from the studies of disordered systems to elucidate the effects of balancing the coverage and supply costs on the network behavior. A readily applicable, coverage optimization algorithm is derived. Simulation results show that magnetized and antiferromagnetic domains emerge and coexist to balance the need for coverage and energy saving. The scaling of parameters with system size agrees with the continuum approximation in two dimensions and the tree approximation in random graphs. Due to frustration caused by the competition between coverage and supply cost, a transition between easy and hard computation regimes is observed. We further suggest a local expansion approach to greatly simplify the message updates which shed light on simplifications in other problems. © 2014 American Physical Society.

Tracing the evolution of physics on the backbone of citation networks

Many innovations are inspired by past ideas in a nontrivial way. Tracing these origins and identifying scientific branches is crucial for research inspirations. In this paper, we use citation relations to identify the descendant chart, i.e., the family tree of research papers. Unlike other spanning trees that focus on cost or distance minimization, we make use of the nature of citations and identify the most important parent for each publication, leading to a treelike backbone of the citation network. Measures are introduced to validate the backbone as the descendant chart. We show that citation backbones can well characterize the hierarchical and fractal structure of scientific development, and lead to an accurate classification of fields and subfields. © 2011 American Physical Society.

Causality in crude oil prices

Crude oil markets witness growing disparity between the quality of crudes supplied and demanded in the market. The market share of low-quality crudes is increasing due to the depletion of old fields and increasing demand. This is unnerving the practitioners and affecting the relevance of the traditional benchmark crudes due to the lack of lower quality benchmarks (Montepeque, 2005). In this article, we apply Granger causality tests to study the price dependence of 32 crudes in order to establish which crudes drive other prices and which ones simply follow general market trends. Our results indicate that some of the old benchmarks are still relevant while others can be disregarded. Our results also interestingly show that the low-quality Mediterranean Russian Urals crude, introduced in the late 1990s, has emerged recently as a significant driver of global prices. © 2011 Taylor & Francis.