Maximum flow and topological structure of complex networks

Abstract

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 $<q{>}_{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.

7 pages, 4 figures

References in corpus (8)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• The diameter of the world wide web
• The large-scale organization of metabolic networks
• Evolution of networks
• Modeling the Internet's Large-Scale Topology
• Anomalous Transport in Complex Networks
• Evolution of scale-free random graphs: Potts model formulation

Cited by in corpus (11)

• Percolation on complex networks: Theory and application
• Synchronization in Weighted Uncorrelated Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency
• Enhanced Flow in Small-World Networks
• Large-deviation properties of the largest biconnected component for random graphs
• Transport on weighted Networks: when correlations are independent of degree
• Transport in networks with multiple sources and sinks
• Optimizing transport efficiency on scale-free networks through assortative or dissortative topology
• Distributed flow optimization and cascading effects in weighted complex networks
• Transport of multiple users in complex networks
• Anomalous electrical and frictionless flow conductance in complex networks
• Flows on Graphs with Random Capacities