图像的代数连通性的边缘差分隐私 （CS Cryptography and Security）

在建模多主体系统中，图像是其中主导的形式。图像的代数连通性特别重要，因为它给出了共识算法的合流速度，而共识算法正是众多多智能体控制和优化技术的基础。但是，代数连通值的共享可能会无意间泄露有关图像拓扑算法中的敏感信息，例如在社交网络中的连接。因此，我们在这项工作中提出了一种基于图论形式的差分隐私（称为边缘差分隐私）下发布图像的代数连通性的方法。边缘差分隐私掩盖了图像边缘集之间的差异，进而掩盖了其中不存在或存在敏感连接的情况。我们为有界的拉普拉斯噪声提供了保密性，与传统的无界噪声相比，它可以提高准确性。有分析显示私有代数连通值可以给出对共识收敛速度的准确估算，以及图像直径及其节点之间的平均距离的准确界限。在模拟的结果中也反映了在这些情况下私有代数连通性的实用性。

原文题目：Edge Differential Privacy for Algebraic Connectivity of Graphs

原文：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.