一、研究背景
在线社交网络（Online social network，OSN）的数据可以用来做很多的事情，比如推荐新的朋友，针对性的广告，还有社交关系的分析。
但若直接共享OSN的原始信息，就很有可能会泄露用户的隐私和敏感信息，所以在共享前需要先对原始信息进行匿名化处理。
二、文章要解决的主要问题
差分隐私（Differential Privacy）正广泛应用在匿名化中，利用差分隐私的方法对真实数据加噪声后，敌手将无法区分出真实数据和带噪声数据。
由于不能直接对图结构添加噪声，通常需要将图抽象为某一个模型，并转化为能数值表示的数据。
已有的dK模型和HRG模型，分别是从特定的角度去描述原来的图，度数分布信息无法描述聚集系数信息，聚集系数信息也无法描述度数分布信息。
那么，能否找出一种实用指标全面地描述原来的图，并且找到一种匿名化机制使得这种实用指标能保持下来？
三、文章提出的主要技术方法
本文认为，持续同调（Persistent Homology）作为一种新颖的方法，可以在不同距离分辨率和不同维度下跟踪全图拓扑特征，可以将持续同调与差分隐私相结合，来保持图的实用指标。
本文设计了一种PHDP的匿名化方案，既保持持续同调，又满足差分隐私的要求。PHDP高层次的构想是，需要保持的结构只占了网络的一小部分，那么剩下的那一大部分就可以用来满足差分隐私。
PHDP分为三个步骤，
- 跟踪和分割持久结构
对于持久结构的跟踪，选择了邻接矩阵作为图抽象模型，有三个原因。第一点，邻接矩阵模型的灵敏度最低，所以需要注入的噪声也越少；第二点，邻接矩阵很容易转化为距离矩阵，距离矩阵是提取barcode的输入；第三点，邻接矩阵在抽象化一个图的时候不会丢失信息。
为了后续的步骤，将邻接矩阵分为四种子矩阵，M0是全零的矩阵，M1代表H1和H2，M2是没有孔的其他结构，M3是M1和M2之间的连接。
- 注入差分隐私噪声
本文嵌入了马尔可夫链蒙特卡洛过程MCMC以获得原始概率分布，这个原始概率分布是指，当随机翻转邻接矩阵中的若干个数时，有x个是0变1，表示加边，有y个是1变0，表示删边，蒙特卡洛就是用来模拟<x,y>在自然情况下对于翻转次数(x+y)的概率分布。
然后采用指数机制注入噪声，它会扰乱<x,y>的概率分布使其满足差分隐私的条件。
- 图的再建
完成噪声注入后，每个子矩阵里边的添加量和删除量都是已知的，但并不是直接按照这些值去做，而是要尽可能保持barcode不变，所以M0和M1消耗很少的噪声，M2和M3要消耗更多的噪声。
对于M0矩阵，不能消耗噪声。
对于M1矩阵（保存H1和H2），要保证调整边的时候不破坏原有的多边形。
对于M2和M3矩阵，它们本来是没有孔的，所以调整边的时候不能多出来孔。
四、实验及结论
本文使用的数据集是facebook和ka-HepPh，作为对比的方法是dK-2和Erdős–Rényi Graph（E-R图）。
- barcode的保持情况：即使是ε取1、也就是差分隐私的要求很严格的情况，PHDP也跟原图的输出差不多，而另外两个模型在H2这一栏是明显多了很多的。
- 度数和聚集系数：度数信息也能保持得跟原图差不多，包括跟本身就是维护度数信息的dK-2模型比也没有差很多，聚集系数也比另外两个模型好一些。
- 影响力最大化算法：从曲线图和均方根误差都可以看出，PHDP确实是这三者维持图信息最好最全面的。
结论：本文设计了一种新的匿名化方案PHDP保护社交网络的隐私，PH表示保持了持续同调，DP表示达到了差分隐私的标准。
五、分析及启示
本文使用了持续同调的方法提取图中孔结构的信息，这是一个保护结构化信息的全新角度。
但本文只是单纯地将两个方法结合起来，并没有解释为什么这样会使得图的信息得到极大的保留。我认为这是一个很值得研究的问题，可能与社交网络本身的特性有关，也有可能是因为孔结构既保持了弱关系也保持了强关系。
