Journal article
On Multi-Source Networks: Enumeration, Rate Region Computation, and Hierarchy
IEEE transactions on information theory, v 63(11), pp 7283-7303
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.
Metrics
Details
- Title
- On Multi-Source Networks: Enumeration, Rate Region Computation, and Hierarchy
- Creators
- Congduan Congduan Li - Dept. of Electr. & Comput. Eng., Drexel Univ., Philadelphia, PA, USASteven Weber - Dept. of Electr. & Comput. Eng., Drexel Univ., Philadelphia, PA, USAJohn MacLaren Walsh - Dept. of Electr. & Comput. Eng., Drexel Univ., Philadelphia, PA, USA
- Publication Details
- IEEE transactions on information theory, v 63(11), pp 7283-7303
- Publisher
- IEEE
- Grant note
- RGC 11207615 / Research Grants Council of Hong Kong CCF–1016588; 1421828 / National Science Foundation Awards (10.13039/100000001) ITS/180/16 / Hong Kong Innovation and Technology Fund Project 20170221180035973; JCYJ20170307090810981 / Science, Technology and Innovation Commission of Shenzhen Municipality
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Web of Science ID
- WOS:000413318900027
- Scopus ID
- 2-s2.0-85028551729
- Other Identifier
- 991014877881004721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Information Systems
- Computer Science, Theory & Methods
- Engineering, Electrical & Electronic
- Mathematics, Applied