Information Centrality and Ordering of Nodes for Accuracy in Noisy Decision-Making Networks

• Published in: IEEE transactions on automatic control 2016-04, Vol.61 (4), p.1040-1045
• Main Authors: Poulakakis, Ioannis, Young, George F., Scardovi, Luca, Leonard, Naomi Ehrich
• Format: Article
• Language: English
• Subjects: Constants; Decision making; Eigenvalues and eigenfunctions; Graph theory; Graphical representations; Graphs; Indexes; Laplace equations; Networks; Noise measurement; Order disorder; Resistance; Stochastic processes; Variance
• ISSN: 0018-9286; 1558-2523
• DOI: 10.1109/TAC.2015.2454373

This technical note considers a network of stochastic evidence accumulators, each represented by a drift-diffusion model accruing evidence towards a decision in continuous time by observing a noisy signal and by exchanging information with other units according to a fixed communication graph. These network dynamics model distributed sequential hypothesis testing as well as collective decision making. We prove the relationship between the location of each unit in the graph and its certainty as measured by the inverse of the variance of its state. Under mild connectivity assumptions, we show that only in balanced directed graphs do the node variances remain within a bounded constant from the minimum possible variance. We then prove that, for these digraphs, node ranking based on certainty is governed by information centrality, which depends on the notion of effective resistance suitably generalized to directed graphs. Our results, which describe the certainty of each unit as a function of the structural properties of the graph, can guide the selection of leaders in problems that involve the observation of noisy external signals by a cooperative multi-agent network.