Europhys. Lett.
Volume 72, Number 2, October 2005
Page(s) 308 - 314
Section Interdisciplinary physics and related areas of science and technology
Published online 14 September 2005
Europhys. Lett., 72 (2), pp. 308-314 (2005)
DOI: 10.1209/epl/i2005-10232-x

Minimum spanning trees of weighted scale-free networks

P. J. Macdonald, E. Almaas and A.-L. Barabási

Center for Network Research and Department of Physics, University of Notre Dame Notre Dame, IN 46556, USA

received 18 July 2005; accepted 26 August 2005
published online 14 September 2005

A complete characterization of real networks requires us to understand the consequences of the uneven interaction strengths between a system's components. Here we use minimum spanning trees (MSTs) to explore the effect of correlations between link weights and network topology on scale-free networks. Solely by changing the nature of the correlations between weights and network topology, the structure of the MSTs can change from scale-free to exponential. Additionally, for some choices of weight correlations, the efficiency of the MSTs increases with increasing network size, a result with potential implications for the design and scalability of communication networks.

89.75.Fb - Structures and organization in complex systems.
89.75.Hc - Networks and genealogical trees.
89.20.Hh - World Wide Web, Internet.

© EDP Sciences 2005