Maximum Multicommodity Flow of Small-World Networks

Abstract

This study investigates the capacity of small-world networks that are formulated as acquiring the Maximum Multicommodity Flows (MMF). The minimum multicut provides the upper bound of the MMF. Therefore, a heuristic algorithm, named Ring Lattice Min Multicut (RLMM) algorithm, is first designed to compare the capacity of Regular Ring Lattice Networks (RRLNs) and Small-world Ring Lattice Networks (SRLNs) constructed by rewiring the edges of the RRLNs with a certain probability. The rewired edges are considered shortcuts. Then, the asymptotic analysis is adopted to predict the capacity of SRLNs. Finally, the simulation results show that the MMF of the SRLNs has a capacity that is 10-50% greater than that of the RRLNs, and the capacity on the shortcut affects the MMF dramatically.