张晓琳，袁昊晨，李卓麟，张换香，刘 娇

内蒙古科技大学 信息工程学院，内蒙古 包头 014000

1 引言

随着社会网络的快速发展，社会网络含有更加丰富的信息，例如Facebook、Twitter、微博等。社会网络中含有用户的隐私信息，在云平台内进行子图匹配[1-4]时保护隐私信息是非常重要的。K-自同构算法[5]是传统的社会网络隐私保护算法，这种方法在处理大规模社会网络图时，处理效率会大幅度下降[6]而且不能保证较高的数据可用性。传统的K-自同构算法在原始图中添加噪声边，使原始图中的每个节点都有至少有k-1 个对称节点。如图1 是社会网络原始图，在原始图的基础上添加3 条噪声边，同时根据表1对原始图的标签进行标签分组泛化[7]后使原始图转换成2-自同构图，如图2。

可以看出K-自同构算法能很好地抵御结构攻击。但这种方法因为添加了噪声边，导致了子图匹配结果的不准确以及在云平台中进行子图匹配大量的空间时间消耗。

为此提出一种解决方案，将原始社会网络图匿名成K-自同构匿名图并将K-自同构匿名图的一部分和K-自同构函数上传至云平台中；在云平台中进行子图匹配操作得到不完全子图匹配结果；将得到的结果以及K-自同构函数下载至客户端内进行恢复和过滤。本文主要研究内容如下：

（1）提出分布式K-自同构社会网络隐私保护算法DK-A（distributedK-automorphism）保护社会网络结构隐私，为了减少子图匹配时间空间成本，上传K-自同构图的一部分和K-自同构函数至云平台。

（2）提出分布并行的子图匹配方法，在云平台中对搜索分解子图QSGs（query subgraphs）进行子图匹配，将得到的结果以及K-自同构函数下载回客户端中进行子图匹配。……