Maximum flow and topological structure of complex networksD.-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 is for large 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