Parts | Days | Selection | Search | Downloads | Help
DY: Dynamik und Statistische Physik
DY 10: Statistical Physics of Complex Networks I
DY 10.4: Talk
Monday, March 27, 2006, 10:30–10:45, H\"UL 186
Maximum flow and topological structure of complex networks — •Deok-Sun Lee and Heiko Rieger — Theoretische Physik, Universität des Saarlandes, 66041 Saarbrücken, Germany
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 kmin is ⟨ q⟩kmin ≃ c kmin for large kmin 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 edge-biconnected links, 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.