Europhys. Lett.
Volume 73, Number 3, February 2006
Page(s) 471 - 477
Section Interdisciplinary physics and related areas of science and technology
Published online 23 December 2005
Europhys. Lett., 73 (3), pp. 471-477 (2006)
DOI: 10.1209/epl/i2005-10407-5

Maximum flow and topological structure of complex networks

D.-S. Lee and H. Rieger

Theoretische Physik, Universität des Saarlandes - 66041 Saarbrücken, Germany

received 22 August 2005; accepted in final form 2 December 2005
published online 23 December 2005

The problem of sending the maximum amount of flow q between two arbitrary nodes s and t of complex networks along links with unit capacity is studied, which is equivalent to determining the number of link-disjoint paths between s and t. The average of q over all node pairs with smaller degree $k_{\min}$ is $\langle
q\rangle_{k_{\min}} \simeq c\, k_{\min}$ for large $k_{\min}$ with c a constant implying that the statistics of q is related to the degree distribution of the network. The disjoint paths between hub nodes are found to be distributed among the links belonging to the same edge-biconnected component, and q can be estimated by the number of pairs of edge-biconnected links incident to the start and terminal node. The relative size of the giant edge-biconnected component of a network approximates to the coefficient c. The applicability of our results to real-world networks is tested for the Internet at the autonomous system level.

89.70.+c - Information theory and communication theory.
89.75.Fb - Structures and organization in complex systems.
02.60.Pn - Numerical optimization.

© EDP Sciences 2006