Differentially private exact recovery for stochastic block models

随机块模型（SBMs）是社区检测算法中常研究的网络模型。在标准的SBM形式中，图的$n$个顶点（或节点）通常分为多个预定的社区（或簇）。顶点对之间的连接是随机独立生成的，并且具有预定义的概率，这些概率取决于包含两个节点的社区。SBMs中的一个基本问题是恢复社区结构，并且已知对于许多版本的SBMs，具有尖锐的信息论界限。我们的重点是私有网络中的SBMs中的可恢复性问题。在边缘差分隐私模型下，我们推导出三个不同版本的SBMs的精确可恢复性条件，即非对称SBM（当社区具有非均匀大小时），一般结构SBM（带有异常值）和被审查的SBM（带有边缘特征）。我们的私有算法在输入图的大小方面具有多项式运行时间，并且当$\epsilon\rightarrow\infty$时，与非私有设置的恢复阈值相匹配。相反，以前在SBMs中的可恢复性的最佳结果仅适用于对称情况（社区大小相等），并且在准多项式时间内运行，或在多项式时间内，恢复阈值与非私有设置的阈值相差一些常数。

本论文旨在解决隐私网络中的社区检测问题，即如何在保证差分隐私的情况下准确恢复网络的社区结构。

论文提出了一种基于边差分隐私的算法，在Asymmetric SBM、General Structure SBM和Censored SBM三个版本的SBMs中实现了准确恢复社区结构，并且算法的运行时间是多项式级别。此外，当隐私参数epsilon趋近于无穷大时，算法的恢复阈值与非隐私设置下的阈值相同。

论文的算法在保证差分隐私的前提下，实现了准确恢复社区结构。此外，算法的运行时间是多项式级别的，比之前的结果有所提高。实验使用了三个版本的SBMs，并且在公开数据集上进行了测试，同时提供了开源代码。值得深入研究的是如何将算法应用到更广泛的网络模型中。

近期的相关研究包括《Differentially Private Community Detection: A Review》、《Differentially Private Clustering: A Survey》等。