Local Tomography of Large Networks under the Low-Observability Regime

Abstract

This article studies the problem of reconstructing the topology of a network of interacting agents via observations of the state-evolution of the agents. We focus on the large-scale network setting with the additional constraint of $partial$ observations, where only a small fraction of the agents can be feasibly observed. The goal is to infer the underlying subnetwork of interactions and we refer to this problem as $local$ $tomography$. In order to study the large-scale setting, we adopt a proper stochastic formulation where the unobserved part of the network is modeled as an Erdös-Rényi random graph, while the observable subnetwork is left arbitrary. The main result of this work is establishing that, under this setting, local tomography is actually possible with high probability, provided that certain conditions on the network model are met (such as stability and symmetry of the network combination matrix). Remarkably, such conclusion is established under the $low$-$observability$ $regime$, where the cardinality of the observable subnetwork is fixed, while the size of the overall network scales to infinity.

To appear in IEEE Transactions on Information Theory

References in corpus (11)

• Gossip Algorithms for Distributed Signal Processing
• Latent variable graphical model selection via convex optimization
• Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and Tradeoffs
• Noise bridges dynamical correlation and topology in coupled oscillator networks
• Signal Processing on Graphs: Causal Modeling of Unstructured Data
• Model of Brain Activation Predicts the Neural Collective Influence Map of the Brain
• Reconstructing Links in Directed Networks from Noisy Dynamics
• Large Deviations Performance of Consensus+Innovations Distributed Detection with Non-Gaussian Observations
• Diffusion-Based Adaptive Distributed Detection: Steady-State Performance in the Slow Adaptation Regime
• Learning loopy graphical models with latent variables: Efficient methods and guarantees
• Network Inference from Consensus Dynamics

Cited by in corpus (1)

• An Unbiased Symmetric Matrix Estimator for Topology Inference under Partial Observability