Graphs are the dominant formalism for modeling multi-agent systems. The algebraic connectivity of a graph is particularly important because it provides the convergence rates of consensus algorithms that underlie many multi-agent control and optimization techniques. However, sharing the value of algebraic connectivity can inadvertently reveal sensitive information about the topology of a graph, such as connections in social networks. Therefore, in this work we present a method to release a graph's algebraic connectivity under a graph-theoretic form of differential privacy, called edge differential privacy. Edge differential privacy obfuscates differences among graphs' edge sets and thus conceals the absence or presence of sensitive connections therein. We provide privacy with bounded Laplace noise, which improves accuracy relative to conventional unbounded noise. The private algebraic connectivity values are analytically shown to provide accurate estimates of consensus convergence rates, as well as accurate bounds on the diameter of a graph and the mean distance between its nodes. Simulation results confirm the utility of private algebraic connectivity in these contexts.
翻译:图形的代数连通性特别重要,因为它提供了许多多剂控制和优化技术所依据的共识算法的趋同率。然而,共享代数连通性的价值可能会无意中揭示出关于图的地形学的敏感信息,例如社交网络的连接。因此,在这项工作中,我们提出了一个方法,在差异隐私的图形理论形式下,即所谓的边缘差异隐私,释放图的代数连通性。强差隐私分解图边缘各组的差异,从而掩盖其中不存在或存在的敏感连接。我们提供了封闭式拉比噪音的隐私,这提高了与传统无限制噪音的准确性。私人代数连通性值通过分析显示,提供了共识趋同率的准确估计,以及图形直径及其节点之间的平均距离的准确界限。模拟结果证实了私人代数连通性在这些背景下的实用性。