Growing Well-Connected Networks for Entropy Rate Maximization

We study the problem of enhancing the maximum entropy rate of Markov chains by strategically adding edges from a candidate set to a given network. We first formulate an optimization problem to identify the optimal edges for addition, which is inherently hard since the edge selection is combinatorial. We then treat the edge addition as a perturbation to the network and derive a perturbation bound on the relative change of a low dimensional vector that is directly related to the maximum entropy rate when a small number of edges are being added. This analysis based on perturbation theory allows us to establish a linear approximation to the change of the maximum entropy rate, which further leads to efficient heuristic algorithms. Building on the efficient solution methods for vector equations in the existing literature, our algorithms only require additional simple vector operations and comparisons to obtain a near-optimal solution for the growing networks problem. Although we derive the heuristics from the perturbation theory, we further show that it can also be interpreted as moving along a direction that leads to the most improvement in the objective function. Extensive simulations validate the effectiveness of our algorithms.