Network Inference from Consensus Dynamics with Unknown Parameters

Abstract

We explore the problem of inferring the graph Laplacian of a weighted, undirected network from snapshots of a single or multiple discrete-time consensus dynamics, subject to parameter uncertainty, taking place on the network. Specifically, we consider three problems in which we assume different levels of knowledge about the diffusion rates, observation times, and the input signal power of the dynamics. To solve these underdetermined problems, we propose a set of algorithms that leverage the spectral properties of the observed data and tools from convex optimization. Furthermore, we provide theoretical performance guarantees associated with these algorithms. We complement our theoretical work with numerical experiments, that demonstrate how our proposed methods outperform current state-of-the-art algorithms and showcase their effectiveness in recovering both synthetic and real-world networks.

References in corpus (11)

• Statistical mechanics of complex networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs
• Learning graphs from data: A signal representation perspective
• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• Stationary signal processing on graphs
• Stationary Graph Processes and Spectral Estimation
• Revealing networks from dynamics: an introduction
• Signal Processing on Graphs: Causal Modeling of Unstructured Data
• High-dimensional covariance estimation based on Gaussian graphical models
• Network Inference from Consensus Dynamics

Cited by in corpus (8)

• Joint Inference of Multiple Graphs from Matrix Polynomials
• Exact Blind Community Detection from Signals on Multiple Graphs
• Blind Inference of Eigenvector Centrality Rankings
• Joint Network Topology Inference in the Presence of Hidden Nodes
• Topology Inference for Network Systems with Unknown Inputs
• Impact of Community Structure on Consensus Machine Learning
• Blind Demixing of Diffused Graph Signals
• On the Impact of Random Actions on Opinion Dynamics