Eur. Phys. J. B 32, 249-263 (2003)
https://doi.org/10.1140/epjb/e2003-00095-5

Economic small-world behavior in weighted networks

¹ Dipartimento di Fisica e Astronomia, Universitá di Catania, and INFN, Via S. Sofia 64, 95123 Catania, Italy
² W3C and Lab. for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, USA
³ Dipartimento di Informatica, Universitá di Venezia, Via Torino 55, 30172 Mestre, Italy

Corresponding author: ^a latora@ct.infn.it

Received: 6 November 2002
Revised: 24 January 2003
Published online: 1 April 2003

Abstract

The small-world phenomenon has been already the subject of a huge variety of papers, showing its appeareance in a variety of systems. However, some big holes still remain to be filled, as the commonly adopted mathematical formulation is valid only for topological networks. In this paper we propose a generalization of the theory of small worlds based on two leading concepts, efficiency and cost, and valid also for weighted networks. Efficiency measures how well information propagates over the network, and cost measures how expensive it is to build a network. The combination of these factors leads us to introduce the concept of economic small worlds , that formalizes the idea of networks that are “cheap” to build, and nevertheless efficient in propagating information, both at global and local scale. In this way we provide an adequate tool to quantitatively analyze the behaviour of complex networks in the real world. Various complex systems are studied, ranging from the realm of neural networks, to social sciences, to communication and transportation networks. In each case, economic small worlds are found. Moreover, using the economic small-world framework, the construction principles of these networks can be quantitatively analyzed and compared, giving good insights on how efficiency and economy principles combine up to shape all these systems.