Topology for Distributed Inference on Graphs

Let N decision-makers collaborate to reach a decision. We consider iterative distributed inference with local intersensor communication, which, under simplifying assumptions, is equivalent to distributed average consensus. We show that, under appropriate conditions, the topology given by the nonbipartite Ramanujan graphs optimizes the convergence rate of this distributed algorithm.

• Publication year

  2006

• Venue

  IEEE Transactions on Signal Processing

• Publication date

  2006-06-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TSP.2008.923536arXiv cs/0606052
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Models of random regular graphs

  2010cited by this paper
• Navigation in a small world

  2008cited by this paper
• Topology of Sensor Networks in Distributed Detection

  2006influential reference
• Ramanujan Topologies for Decision Making in Sensor Networks

  2006cited by this paper
• Influence of cultivation temperature on the ligninolytic activity of selected fungal strains

  2006cited by this paper
• Distributed Detection in Sensor Networks: Connectivity Graph and Small World Networks

  2005influential reference
• Network synchronization, diffusion, and the paradox of heterogeneity.

  2005cited by this paper
• Ultrafast consensus in small-world networks

  2005cited by this paper
• Consensus problems in networks of agents with switching topology and time-delays

  2004cited by this paper
• An Optimal Algorithm for Checking Regularity

  2003cited by this paper
• Fast linear iterations for distributed averaging

  2003cited by this paper
• Decentralized detection in sensor networks

  2003cited by this paper
• Coordination of groups of mobile autonomous agents using nearest neighbor rules

  2002cited by this paper
• Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors

  2000cited by this paper
• The small-world phenomenon: an algorithmic perspective

  2000cited by this paper
• The good, bad and ugly: distributed detection of a known signal in dependent Gaussian noise

  2000cited by this paper
• Surveys in Combinatorics, 1999: Models of Random Regular Graphs

  1999cited by this paper
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• Distributed detection with multiple sensors I. Advanced topics

  1997cited by this paper
• Distributed Detection and Data Fusion

  1996cited by this paper
• Matrices and Graphs: Theory and Applications to Economics Proceedings of the Conferences

  1996cited by this paper
• Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power q

  1994cited by this paper
• Decentralized Detection'

  1993cited by this paper
• A Short Proof of Jacobi's Formula for the Number of Representations of an Integer as a Sum of Four Squares

  1992cited by this paper
• Decentralized detection by a large number of sensors

  1988cited by this paper
• Eigenvalues and expanders

  1986cited by this paper
• Network synchronization

  1985cited by this paper
• The evolution of random graphs

  1984cited by this paper
• Problems in decentralized decision making and computation

  1984cited by this paper
• On the evolution of random graphs

  1984cited by this paper
• Generating Random Regular Graphs

  1984cited by this paper
• Detection with Distributed Sensors

  1980cited by this paper
• A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs

  1980cited by this paper
• The asymptotic number of non-negative integer matrices with given row and column sums

  1974cited by this paper
• Algebraic connectivity of graphs

  1973cited by this paper
• Detection, Estimation, and Modulation Theory, Part I

  1968cited by this paper
• Ramanujan Graphs

  1965cited by this paper
• Journal of Combinatorial Theory, Series A

  year unknowncited by this paper
• Probabilistic Decoding of Low-Density Cayley Codes

  year unknowncited by this paper

• Optimal Graph Stretching for Distributed Averaging

  2025cites this paper
• Approximate Stability Radius Analysis and Design in Linear Systems

  2024cites this paper
• Performance Analysis of Gossip Algorithms for Large Scale Wireless Sensor Networks

  2024cites this paper
• Decentralised possibilistic inference with applications to target tracking

  2022cites this paper
• Can Competition Outperform Collaboration? The Role of Malicious Agents

  2022cites this paper
• Matcha: A Matching-Based Link Scheduling Strategy to Speed up Distributed Optimization

  2022cites this paper
• A graph-theory approach to optimisation of an acoustic absorber targeting a specific noise spectrum that approaches the causal optimum minimum depth

  2021cites this paper
• Deflection-based Attack Detection for Network Systems

  2021cites this paper
• Dynamic Median Consensus Over Random Networks

  2021cites this paper
• To interact or not? The convergence properties of interacting stochastic mirror descent

  2020cites this paper
• Improved performance properties of the CISPRT algorithm for distributed sequential detection

  2020cites this paper
• The evolving topology of the Lightning Network: Centralization, efficiency, robustness, synchronization, and anonymity

  2020cites this paper
• Optimal Topology Search for Fast Model Averaging in Decentralized Parallel SGD

  2020cites this paper
• Fault-Resilient Distributed Detection and Estimation Over a SW-WSN Using LCMV Beamforming

  2020cites this paper
• Design and performance analysis of a fully distributed source detection algorithm for WSNs

  2019cites this paper
• Gossip algorithm with nonuniform clock distribution: Optimization over classical and quantum networks

  2019cites this paper
• Drones without a master : Resource efficiency in consensus-reaching topologies

  2019cites this paper
• Scalability and Fragility in Bounded-Degree Consensus Networks

  2019cites this paper
• Quantized Event-triggered Sampled-data Average Consensus with Guaranteed Rate of Convergence

  2019cites this paper
• Inference and Optimization over Networks: Communication Efficiency and Optimality

  2018cites this paper
• On the optimality of sparse long-range links in circulant consensus networks

  2017cites this paper
• Dist-Hedge: A partial information setting based distributed non-stochastic sequence prediction algorithm

  2017cites this paper
• Byzantine-Resilient locally optimum detection using collaborative autonomous networks

  2017cites this paper
• Distributed Learning With Time Correlated Information

  2017cites this paper
• Distributed cooperative target detection and localization in decentralized wireless sensor networks

  2017cites this paper
• Adaptive Nonassisted Distributed Detection in Sensor Networks

  2017cites this paper
• Quantized Consensus by the Alternating Direction Method of Multipliers: Algorithms and Applications

  2017cites this paper
• Byzantine Resilient Locally Optimum Radioactive Source Detection Using Collaborative Sensor Networks

  2017cites this paper
• Accelerated consensus via Min-Sum Splitting

  2017cites this paper
• Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization

  2017cites this paper
• Distributed average consensus with bounded quantization

  2016cites this paper
• Distributed Two-Step Quantized Fusion Rules Via Consensus Algorithm for Distributed Detection in Wireless Sensor Networks

  2016cites this paper
• Distributed detection over connected networks via one-bit quantizer

  2016cites this paper
• CONSENSUS IN MULTI-AGENT SYSTEMS

  2016cites this paper
• Distributed Detection in Ad Hoc Networks Through Quantized Consensus

  2016cites this paper
• Distributed Linear Filtering and Prediction of Time-varying Random Fields

  2016cites this paper
• Distributed Average Consensus with Bounded Quantizer and Unbounded Input

  2016cites this paper
• Queue-based broadcast gossip algorithm for consensus

  2016cites this paper
• Distributed sequence prediction: A consensus+innovations approach

  2016cites this paper
• Stochastic distributed consensus with quantized data and input noise

  2016cites this paper
• Leader-Follower Consensus in Mobile Sensor Networks

  2015cites this paper
• Ensuring High Performance of Consensus-Based Estimation by Lifetime Maximization in WSNs

  2015cites this paper
• Optimizing the Gossip Algorithm with Non-Uniform Clock Distribution over Classical & Quantum Networks

  2015cites this paper
• Distributed Consensus-Based Weight Design for Cooperative Spectrum Sensing

  2015cites this paper
• Data Falsification Attacks on Consensus-Based Detection Systems

  2015cites this paper
• Energy Efficient Consensus Over Complex Networks

  2015cites this paper
• Supplementary Material to “Distributed Consensus-based Weight Design for Cooperative Spectrum Sensing”

  2015cites this paper
• On Optimality of Sparse Long-Range Links in Circulant Consensus Networks

  2015cites this paper
• Distributed detection in practical wireless sensor networks via a two-step consensus algorithm

  2015cites this paper
• Distributed State Estimation and Energy Management in Smart Grids: A Consensus${+}$ Innovations Approach

  2014cites this paper
• Distributed Sequential Detection for Gaussian Shift-in-Mean Hypothesis Testing

  2014cites this paper
• Distributed sequential detection for Gaussian binary hypothesis testing: Heterogeneous networks

  2014cites this paper
• Convergence Analysis for Regular Wireless Consensus Networks

  2014cites this paper
• Consensus + innovations distributed inference over networks: cooperation and sensing in networked systems

  2013cites this paper
• Global Behavior in Large Scale Systems

  2013cites this paper
• The Wiring Economy Principle for Designing Inference Networks

  2013influential citation
• Scalable Sensor Network Field Reconstruction with Robust Basis Pursuit

  2013cites this paper
• Distributed Inference using Bounded Transmissions

  2013cites this paper
• Distributed Kalman filtering and Network Tracking Capacity

  2013cites this paper
• A Gossip Method for Optimal Consensus on a Binary State From Binary Actions

  2013cites this paper
• Secure Distributed Control Methodologies with Built-in Defense in Distributed Networked Control Systems.

  2013cites this paper
• Improve Network's Robustness Against Cascade with Rewiring

  2013cites this paper
• Robust adaptive machine learning algorithms for distributed signal processing

  2013cites this paper
• Distributed Kalman filtering

  2013cites this paper
• Enhancing the Resilience of Networked Agents through Risk Sharing

  2013cites this paper
• Bayesian Discovery of Threat Networks

  2013cites this paper
• Distributed estimation over complex networks

  2012cites this paper
• Distributed detection and isolation of topology attacks in power networks

  2012cites this paper
• Distributed Cooperative Spectrum Sensing Using Weighted Average Consensus

  2012cites this paper
• Distributed Consensus and Mitigating Risk Propagation in Evolutionary Optimized Networks

  2012cites this paper
• Topology design for distributed formation control towards optimal convergence rate

  2012cites this paper
• Cooperative strategies for near-optimal computation in wireless networks

  2012cites this paper
• Toward resource-optimal averaging consensus over the wireless medium

  2012cites this paper
• Dynamical behavior, cost and Magic Number in average consensus

  2012cites this paper
• Threshold phenomenon for average consensus

  2012cites this paper
• Optimal Topology Control and Power Allocation for Minimum Energy Consumption in Consensus Networks

  2012cites this paper
• Distributed Consensus With Limited Communication Data Rate

  2011cites this paper
• Large Deviations Performance of Consensus+Innovations Distributed Detection With Non-Gaussian Observations

  2011cites this paper
• Distributed Detection Over Noisy Networks: Large Deviations Analysis

  2011cites this paper
• Coordination of discrete‐time multi‐agent systems via relative output feedback

  2011cites this paper
• Large deviations analysis of consensus+innovations detection in random networks

  2011cites this paper
• Applying Formal Methods to Distributed Algorithms Using Local-Global Relations

  2011cites this paper
• Distributed Detection via Gaussian Running Consensus: Large Deviations Asymptotic Analysis

  2011cites this paper
• Distributed detection in noisy sensor networks

  2011cites this paper
• Weight Optimization for Consensus Algorithms With

  2010cites this paper
• Distributed detection over time varying networks: Large deviations analysis

  2010cites this paper
• Distributed Detection over Random Networks: Large Deviations Performance Analysis

  2010cites this paper
• Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and Tradeoffs

  2010cites this paper
• Distributed Detection over Random Networks: Large Deviations Analysis

  2010cites this paper
• Unreliable and resource-constrained decoding

  2010influential citation
• Evolutionary Optimized Networks for Consensus and Synchronization

  2010cites this paper
• Distributed inference networks with costly wires

  2010influential citation
• Information diffusion in complex networks via gossiping

  2010cites this paper
• Distributed Algorithms in Sensor Networks

  2010cites this paper
• Distributed Inference over Multiple-Access Channels with Wireless Sensor Networks

  2010cites this paper
• Communication Complexity and Energy Efficient Consensus Algorithm

  2010cites this paper
• Gossip Algorithms for Distributed Signal Processing

  2010cites this paper
• Evolutionary Optimized Consensus and Synchronization Networks

  2009cites this paper
• Structural Properties of the Caenorhabditis elegans Neuronal Network

  2009cites this paper
• Higher Dimensional Consensus: Learning in Large-Scale Networks

  2009cites this paper