We consider a delay-constrained streaming model for zero-error communications and show that under this model, network coding and index coding problems are code equivalent. That is, any streaming network coding instance can be efficiently mapped to a corresponding acyclic streaming index coding instance such that an index code for the latter can be efficiently transformed into a network code for the former. This reduction holds even for network coding instances that contain cycles, thereby proving the first known reduction from cyclic to finite acyclic network coding networks.

In this work, we study the Yeung network coding entropic function outer bound and prove an equivalence relationship between its tightness and the edge removal problem. In addition, we derive an implicit characterization of the 0-error capacity region using restricted sets of entropic vectors.

In recent work, Kamath et al. show that network code design for any k-unicast network reduces to network code design for a related 2-unicast network. The proof assumes that codes achieve their desired rates precisely (rather than approaching them asymptotically) and that error probability equals zero. We study two questions posed in but left unanswered by the Kamath et al. paper. The first asks whether the reduction for 0-error code design can be extended to show an equivalence in 0-error network capacity, which includes rates approached asymptotically. The second asks whether the reduction can be generalized to show an equivalence in Shannon capacity, which requires that error probability approach (but not necessarily hit) zero. While we do not solve these questions, we show that finding the k-unicast capacity reduces to finding the 2-unicast capacity under this reduction if and only if the so called “edge removal statement” is true for all networks. This equivalence holds under both 0-error and asymptotic notions of reliability.

An equivalence between multiple multicast and multiple unicast network codes is proven in a 2007 paper by Dougherty and Zeger. A related equivalence between multiple multicast and multiple unicast capacity for general (possibly noisy) memoryless networks is proven in a 2013 paper by the current authors. While the construction used in the proof from the earlier paper maps any linear code for one network to a linear code for the other network, the construction from the later paper does not necessarily preserve linearity. As a result, the 2013 result does not prove an equivalence between the capacity achievable by linear codes in memoryless multiple multicast and memoryless multiple unicast networks. The linear capacity equivalence for memoryless multiple multicast and multiple unicast networks is proven in this work.

In recent work by Effros, El Rouayheb, and Langberg, an equivalence of code feasibility between network and index coding is derived. The authors ask whether the capacity region of a network coding problem can be obtained by solving the capacity region of an index coding problem. We answer in the affirmative for the linear coding case. While the question is still open for the general case, we show that it is related to the edge removal problem, which has been studied recently.

Many real-world domains are relational in nature, consisting of a set of objects related to each other in complex ways. This paper focuses on predicting the existence and the type of links between entities in such domains. We apply the relational Markov network framework of Taskar et al. to define a joint probabilis- tic model over the entire link graph — entity attributes and links. The application of the RMN algorithm to this task requires the definition of probabilistic patterns over subgraph structures. We apply this method to two new relational datasets, one involving university webpages, and the other a social network. We show that the collective classification approach of RMNs, and the introduction of subgraph patterns over link labels, provide significant improvements in accuracy over flat classification, which attempts to predict each link in isolation.