Network Tomography: New Rigorous Approaches for Discrete and Continuous Problems

We consider several rigorously defined network tomography problems from applications ranging from communication networks, to social networks. The universal abstraction we develop involves the inference of various network structural and parametric properties form observations of certain “probing” processes from a subset of network nodes which we call the boundary nodes of the network. We show that these problems lead to mathematical problems of “deconvolution” over unconventional semirings, inversion of integrals over trees of the underlying graph, Radon transform over symmetric spaces, and completion of sparse matrices albeit in non-conventional semirings. We illustrate applications in several applied problems.Some of the problem formulations and solutions are inspired by generalizations of “electric impedance problems” in various non-nonconventional spaces. Some of the solutions have a variational interpretation.