Probabilistic Analysis on Minimum <I>s-t</I> Cut Capacity of Random Graphs with Specified Degree Distribution

Yuki FUJII; Tadashi WADAYAMA

doi:10.1587/transfun.E97.A.2317

Probabilistic Analysis on Minimum s-t Cut Capacity of Random Graphs with Specified Degree Distribution

Yuki FUJII, Tadashi WADAYAMA

Full Text Views

0

Cite this

Summary :

The capacity (i.e., maximum flow) of a unicast network is known to be equal to the minimum s-t cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or unknown, it is not so trivial to predict statistical properties on the maximum flow of the network. In this paper, we present a probabilistic analysis for evaluating the accumulate distribution of the minimum s-t cut capacity on random graphs. The graph ensemble treated in this paper consists of undirected graphs with arbitrary specified degree distribution. The main contribution of our work is a lower bound for the accumulate distribution of the minimum s-t cut capacity. The feature of our approach is to utilize the correspondence between the cut space of an undirected graph and a binary LDGM (low-density generator-matrix) code. From some computer experiments, it is observed that the lower bound derived here reflects the actual statistical behavior of the minimum s-t cut capacity of random graphs with specified degrees.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.12 pp.2317-2324

Publication Date: 2014/12/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E97.A.2317

Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)

Category: Coding Theory

Authors

Yuki FUJII
Nagoya Institute of Technology
Tadashi WADAYAMA
Nagoya Institute of Technology

Keyword

minimum cut, random graphs, LDGM code

Cite this

Copy

Yuki FUJII, Tadashi WADAYAMA, "Probabilistic Analysis on Minimum s-t Cut Capacity of Random Graphs with Specified Degree Distribution" in IEICE TRANSACTIONS on Fundamentals, vol. E97-A, no. 12, pp. 2317-2324, December 2014, doi: 10.1587/transfun.E97.A.2317.
Abstract: The capacity (i.e., maximum flow) of a unicast network is known to be equal to the minimum s-t cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or unknown, it is not so trivial to predict statistical properties on the maximum flow of the network. In this paper, we present a probabilistic analysis for evaluating the accumulate distribution of the minimum s-t cut capacity on random graphs. The graph ensemble treated in this paper consists of undirected graphs with arbitrary specified degree distribution. The main contribution of our work is a lower bound for the accumulate distribution of the minimum s-t cut capacity. The feature of our approach is to utilize the correspondence between the cut space of an undirected graph and a binary LDGM (low-density generator-matrix) code. From some computer experiments, it is observed that the lower bound derived here reflects the actual statistical behavior of the minimum s-t cut capacity of random graphs with specified degrees.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.2317/_p

Copy

@ARTICLE{e97-a_12_2317,
author={Yuki FUJII, Tadashi WADAYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Probabilistic Analysis on Minimum s-t Cut Capacity of Random Graphs with Specified Degree Distribution},
year={2014},
volume={E97-A},
number={12},
pages={2317-2324},
abstract={The capacity (i.e., maximum flow) of a unicast network is known to be equal to the minimum s-t cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or unknown, it is not so trivial to predict statistical properties on the maximum flow of the network. In this paper, we present a probabilistic analysis for evaluating the accumulate distribution of the minimum s-t cut capacity on random graphs. The graph ensemble treated in this paper consists of undirected graphs with arbitrary specified degree distribution. The main contribution of our work is a lower bound for the accumulate distribution of the minimum s-t cut capacity. The feature of our approach is to utilize the correspondence between the cut space of an undirected graph and a binary LDGM (low-density generator-matrix) code. From some computer experiments, it is observed that the lower bound derived here reflects the actual statistical behavior of the minimum s-t cut capacity of random graphs with specified degrees.},
keywords={},
doi={10.1587/transfun.E97.A.2317},
ISSN={1745-1337},
month={December},}

Copy

TY - JOUR
TI - Probabilistic Analysis on Minimum s-t Cut Capacity of Random Graphs with Specified Degree Distribution
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2317
EP - 2324
AU - Yuki FUJII
AU - Tadashi WADAYAMA
PY - 2014
DO - 10.1587/transfun.E97.A.2317
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2014
AB - The capacity (i.e., maximum flow) of a unicast network is known to be equal to the minimum s-t cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or unknown, it is not so trivial to predict statistical properties on the maximum flow of the network. In this paper, we present a probabilistic analysis for evaluating the accumulate distribution of the minimum s-t cut capacity on random graphs. The graph ensemble treated in this paper consists of undirected graphs with arbitrary specified degree distribution. The main contribution of our work is a lower bound for the accumulate distribution of the minimum s-t cut capacity. The feature of our approach is to utilize the correspondence between the cut space of an undirected graph and a binary LDGM (low-density generator-matrix) code. From some computer experiments, it is observed that the lower bound derived here reflects the actual statistical behavior of the minimum s-t cut capacity of random graphs with specified degrees.
ER -