Abstract: Cloud platform is becoming a mainstream tool for storing and processing large-scale social network data. Aiming at large-scale social network subgraph matching privacy protection problem, this paper proposes a privacy preserving algorithm of distributed K-automorphism social network. The algorithm can protect structural privacy of the social network that has been uploaded to cloud platform. The algorithm adds noise edge by passing marked information between vertices, making original graph be anonymous as a K-automorphism social network graph with k symmetric subgraphs. This paper also proposes a distributed subgraph matching method for upload graph. According to the selectivity of nodes in query graph, this paper decomposes the query graph and gets the query decomposition subgraph; distributed and parallel subgraph matching is performed within each computing node to get the matching result of query decomposed subgraph. After the results are joint, the subgraph matching result of query graph is got; in the client, the results of the subgraph matching are recovered and filtered according to the symmetry of the K-automorphism social network graph and the K-automorphism function to get correct matching result. The experimental results show that: distributed K-automorphism social network privacy protection algorithm and distributed subgraph matching method are highly efficient in dealing with large-scale social network graph and these methods can effectively solve the problem of privacy leakage.

Key words: distributed, social network, privacy preserving, subgraph matching

摘要： 云平台作为存储和处理分析大规模社会网络数据的工具逐渐变为主流，针对大规模社会网络子图匹配隐私保护问题，提出分布式K-自同构社会网络隐私保护算法，保护上传至云平台的社会网络图的结构隐私。通过节点间传递标记信息的方式添加噪声边，使原始图匿名为具有k个对称子图的K-自同构社会网络图。提出分布式的子图匹配方法对上传图进行子图匹配，根据搜索图中节点的选择性对搜索图进行分解得到搜索分解子图；在每个计算节点内进行分布并行的子图匹配得到搜索分解子图匹配结果，将结果连接后得到关于搜索图的匹配结果；在客户端中根据K-自同构社会网络图的对称性和K-自同构函数对得到的子图匹配结果进行恢复和过滤得到正确匹配结果。实验结果表明：分布式K-自同构社会网络隐私保护算法和分布式子图匹配方法在处理大规模社会网络图时具有很高的效率，并且有效解决了隐私泄露问题。

关键词: 分布式, 社会网络, 隐私保护, 子图匹配