标题： 图上的分布式推理拓扑 显示英文标题

标题： Topology for Distributed Inference on Graphs

摘要： 让$N$的本地决策者在传感器网络中与邻居通信以达成决策\emph{共识}。通信是局部的，仅在相邻传感器之间通过无噪声或有噪声的链路进行。我们研究了优化迭代决策共识算法收敛速率的网络拓扑设计。我们将拓扑设计问题重新表述为谱图设计问题，即最大化图拉普拉斯矩阵~$L$的两个特征值的特征比~$\gamma$，该矩阵自然与网络的互连模式相关联。这种重新表述避免了昂贵的蒙特卡洛模拟，并导致了一类非二分Ramanujan图，我们找到了~$\gamma$的下界。对于Ramanujan拓扑和无噪声链路，本地错误概率比结构化图、随机图或具有小世界特性的图更快地收敛到整体全局错误概率。在有噪声链路的情况下，我们确定了在做出决策之前最优的迭代次数。最后，我们引入了一类新的随机图，它们易于构建，可以设计任意数量的传感器，并且其谱特性和收敛特性使它们在实践中等同于Ramanujan拓扑。 显示英文摘要

摘要： Let $N$ local decision makers in a sensor network communicate with their neighbors to reach a decision \emph{consensus}. Communication is local, among neighboring sensors only, through noiseless or noisy links. We study the design of the network topology that optimizes the rate of convergence of the iterative decision consensus algorithm. We reformulate the topology design problem as a spectral graph design problem, namely, maximizing the eigenratio~$\gamma$ of two eigenvalues of the graph Laplacian~$L$, a matrix that is naturally associated with the interconnectivity pattern of the network. This reformulation avoids costly Monte Carlo simulations and leads to the class of non-bipartite Ramanujan graphs for which we find a lower bound on~$\gamma$. For Ramanujan topologies and noiseless links, the local probability of error converges much faster to the overall global probability of error than for structured graphs, random graphs, or graphs exhibiting small-world characteristics. With noisy links, we determine the optimal number of iterations before calling a decision. Finally, we introduce a new class of random graphs that are easy to construct, can be designed with arbitrary number of sensors, and whose spectral and convergence properties make them practically equivalent to Ramanujan topologies.