TY - JOUR
T1 - On multi-source networks
T2 - Enumeration, rate region computation, and hierarchy
AU - Li, Congduan
AU - Weber, Steven
AU - Walsh, John Maclaren
PY - 2017/11
Y1 - 2017/11
N2 - 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.
AB - 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.
KW - Enumeration
KW - Hierarchy
KW - Multi-source networks
KW - Rate region
UR - http://www.scopus.com/inward/record.url?scp=85028551729&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85028551729&origin=recordpage
U2 - 10.1109/TIT.2017.2745620
DO - 10.1109/TIT.2017.2745620
M3 - 21_Publication in refereed journal
VL - 63
SP - 7283
EP - 7303
JO - IRE Transactions on Information Theory
JF - IRE Transactions on Information Theory
SN - 0018-9448
IS - 11
M1 - 8017497
ER -