Edge Differential Privacy for Algebraic Connectivity of Graphs
Edge Differential Privacy for Algebraic Connectivity of Graphs
复制标题
DOI：
10.1109/cdc45484.2021.9683306
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Bo Chen;C. Hawkins;Kasra Yazdani;M. Hale
中科院分区：
文献类型：
--
作者：
Bo Chen;C. Hawkins;Kasra Yazdani;M. Hale
图是建模多智能体系统的主要形式主义。图的代数连通性是特别重要的，因为它提供了共识算法的收敛速度，这些算法是许多多智能体控制和优化技术的基础。然而，共享代数连通性的值可能会无意中泄露关于图的拓扑结构的敏感信息，例如社交网络中的连接。因此，在这项工作中，我们提出了一种方法来释放图的代数连通性下的图论形式的差分隐私，称为边缘差分隐私。边缘差分隐私混淆了图的边缘集之间的差异，从而隐藏了其中敏感连接的存在或不存在。我们提供的隐私与有界拉普拉斯噪声，这提高了精度相对于传统的无界噪声。私人代数连通性值的分析表明，提供准确的估计的共识收敛速度，以及准确的边界上的直径图和其节点之间的平均距离。仿真结果证实了私人代数连接在这些情况下的效用。
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.