基于局部高阶子图的差分隐私保护社区发现算法

侯小军，李泽华，边 锦

（1.西安理工大学 信息化管理处，陕西 西安 710048；2.陕西师范大学 计算机科学学院，陕西 西安 710010；3.陕西师范大学 计算机科学学院，陕西 西安 710010）

1.绪论

近年来，随着互联网技术应用的迅猛发展，在线社交网络服务已经成为人们交流沟通、分享传递信息的重要平台，通过网络维系着用户的社会关系，逐渐形成了潜在的社区结构，其中根据个人的行为将个人分组为社区，通常，同一社区内的个体更有可能分享直接的社交链接，共同的朋友和相似的个人资料等。但是社交关系常常处于不断变化的状态，其动态范围从分分秒秒的变化逐渐到多年来所呈现的模式，故而衍生出动态社交网络。

本文针对在动态的社区划分过程中存在的局部子图隐私信息泄露问题，结合社区发现算法、随机游走算法以及差分隐私提出了一种可以保证子图隐私信息安全性的动态社区发现算法，实现了高效的非重叠社区划分操作。

2.基础理论与相关工作

2.1 基础理论

定义1（差分隐私—Differential Privacy[1]）假定随机算法M，PM表示M的取值范围，对于任意两个邻近数据集D与D"，在PM下的任意一个子集SM中，如果任意输出结果M满足如下不等式：

定义2（ω-事件隐私[2]）ω-事件隐私是一种基于差分隐私的机制，为ω时间戳的任何窗口内发生的任何事件提供可证明的隐私保证。针对时间戳为i的两个邻近数据集Di,，无限序列的流前缀在时间戳为t时定义为

定义3（局部高阶子图（Motif）[3]）社交网络丰富的高阶组织结构通过高阶链接模式的聚类从而表现出来，最普通的局部高阶子图为小网络子图，称为网络基序（主题），被认为是复杂网络的构建块，如图1所示。……