12 - Introducing weights: bandwidth allocation and multimedia broadcasting

Summary

Introduction

In this chapter we present studies of the optimal distance in networks, l_opt, defined as the length of the path minimizing the total weight, in the presence of disorder [BBC⁺03]. Disorder is introduced by assigning random weights to the links or nodes. These weights may represent properties of the links and the transport in them. These properties may include the bandwidth of links in communication networks, delays in the transport of data or material, or the cost of traversing the link. Many real-world networks may be better described by introducing link weights, an example is the airline network where the frequency of flights is an important property (see, e.g., [BBPV04]).

An important quantity characterizing networks is the average distance (minimal hopping) l_min between two nodes in a network containing N nodes. For the Erdős- Rényi networks [ER59, ER60], and the related, more realistic Watts–Strogatz (WS) network [WS98], l_min scales as ln N [Bol85], which leads to the concepts of small world and “six degrees of separation,” while for scale-free networks l_min scales as ln ln N. See Chapter 6 for details.

In most studies, all links in the network are regarded as identical and thus the relevant parameter for information flow including efficient routing, searching, and transport is l_min. In practice, however, the weights (for example, the quality or cost) of links are usually not equal, and thus the length of the optimal path, l_opt, minimizing the sum of weights is usually longer than the distance l_min.