Maximum multicommodity flow of small-world networks

Je Wei Chang*, Chien Chen, Rong Hong Jan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publication2008 International Symposium on Information Theory and its Applications, ISITA2008
DOIs
StatePublished - 1 Dec 2008
Event2008 International Symposium on Information Theory and its Applications, ISITA2008 - Auckland, New Zealand
Duration: 7 Dec 200810 Dec 2008

Publication series

Name2008 International Symposium on Information Theory and its Applications, ISITA2008

Conference

Conference2008 International Symposium on Information Theory and its Applications, ISITA2008
CountryNew Zealand
CityAuckland
Period7/12/0810/12/08

Fingerprint Dive into the research topics of 'Maximum multicommodity flow of small-world networks'. Together they form a unique fingerprint.

Cite this