Inferring Topology of Network Systems by Few Excitations: Probability Analysis and Fusion

Topology inference for network systems is prominent in many fields. Numerous methods have been proposed to improve the inference accuracy using sufficient observations, but few of them consider the situation where only a limited number of observations are available. This paper aims to infer the topology by injecting few excitations into the system and collecting several steps of noisy observations. The problem is challenging because the noise cannot be depressed using several observations, and is also mixed with the influence of injected excitation that will decay over time. Resorting to the hypothesis testing, we first develop a probabilistic method to infer the exact <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$h$</tex-math></inline-formula>-hop neighbors of an excited node and provide probability guarantees. The connection possibility of arbitrary two nodes is characterized as an explicitly calculable probability mass function (PMF), guiding the excitation design to meet desired inference accuracy. Then, based on Dempster-Shafer evidence theory, a fusion inference algorithm is designed to incorporate the multiple PMFs associated with multiple excitations, and provably improves the accuracy. Finally, how to combine the method with regression-based framework is discussed. Numerical simulations verify the effectiveness of the proposed method.