On multi-source networks : Enumeration, rate region computation, and hierarchy

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

10 Scopus Citations
View graph of relations

Author(s)

  • Congduan Li
  • Steven Weber
  • John Maclaren Walsh

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number8017497
Pages (from-to)7283-7303
Journal / PublicationIEEE Transactions on Information Theory
Volume63
Issue number11
Online published29 Aug 2017
Publication statusPublished - Nov 2017

Abstract

Recent algorithmic developments have enabled computers to automatically determine and prove the capacity regions of small hypergraph networks under network coding. A structural theory relating network coding problems of different sizes is developed to make the best use of this newfound computational capability. A formal notion of network minimality is developed, which removes components of a network coding problem that are inessential to its core complexity. Equivalence between different network coding problems under relabeling is formalized via group actions, an algorithm which can directly list single representatives from each equivalence class of minimal networks up to a prescribed network size is presented. This algorithm, together with rate region software, is leveraged to create a database containing the rate regions for all minimal network coding problems with five or fewer sources and edges, a collection of 744119 equivalence classes representing more than 9 million networks. In order to best learn from this database, and to leverage it to infer rate regions and their characteristics of networks at scale, a hierarchy between different network coding problems is created with a new theory of combinations and embedding operators.

Research Area(s)

  • Enumeration, Hierarchy, Multi-source networks, Rate region

Citation Format(s)

On multi-source networks : Enumeration, rate region computation, and hierarchy. / Li, Congduan; Weber, Steven; Walsh, John Maclaren.

In: IEEE Transactions on Information Theory, Vol. 63, No. 11, 8017497, 11.2017, p. 7283-7303.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review