  We propose algorithms to approximate directed information graphs. Directed
information graphs are probabilistic graphical models that depict causal
dependencies between stochastic processes in a network. The proposed algorithms
identify optimal and near-optimal approximations in terms of Kullback-Leibler
divergence. The user-chosen sparsity trades off the quality of the
approximation against visual conciseness and computational tractability. One
class of approximations contains graphs with specified in-degrees. Another
class additionally requires that the graph is connected. For both classes, we
propose algorithms to identify the optimal approximations and also near-optimal
approximations, using a novel relaxation of submodularity. We also propose
algorithms to identify the r-best approximations among these classes, enabling
robust decision making.
