侯小军，李泽华，边 锦

（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所示。

图1 局部高阶子图

定义4（主题电导—Motif Conductance[4]）对于一个网络主题实例M的主题电导定义如下：

网络主题M为任意小的连通子图。节点S集合的主题划分由cutM(S)表示，其中至少存在一个节点在S中，另一个节点在中，如图2中A图所示，节点S的主题划分体积由volM(S)表示主题实例节点在S中的数量，社区划分操作如图2中B图所示。

图2 主题电导及划分

定义5（时序图-时序主题[5]）时序边为有序节点对之间带有时间戳的有向边，时序图由多条时序边组成，时序图如图3中A图所示。A:一个有九条时序边的时序图，每条边都有一个时间戳（以秒为单位）。B:三个节点，三条边的δ-时序网络主题M。C:δ-时序主题M的实例，时间戳范围δ=10s，被消去的主题均不是M的实例，因为边定向关系方向不正确或者在δ时间戳范围内未发生。

图3 时序图

2.2 相关工作

基于局部高阶子图的图聚类划分，Hu[6]等人提出m-派系主题，并在大型异构信息网络中寻求最大的网络主题派系，探索多种复杂网络的内部结构特征。Li[7]等人引入三角网络主题划分加权完整图的节点，运用模拟退火算法解决划分过程中重叠聚类的节点。Zhang[8]等人基于局部高阶网络主题提出新的局部社区检测方法（LCD-motif），通过在局部光谱范围内寻找稀疏矢量来划分聚簇。以上基于局部高阶子图进行社区划分的研究大多应用均在静态社交网络上执行，但是，现实的网络系统多数情况下不是静态的，它们之间的链接对象随着时间动态变化[9]，如邮件系统等。依据对以上现有局部高阶子图研究的分析，目前动态社交网络进行社区划分主要存在两个问题：1）依据局部高阶子图的多样性，在基于时间动态变化的社交网络上如何保证获取准确的局部子图结构。2）动态社交网络实现社区划分的同时如何避免子图隐私信息的泄露以及如何保证社区划分的准确度；

针对第一个问题，基于时序网络主题定义在δ时间戳范围内定义时序边，提出运用快速算法统计在δ时序内生成网络主题的个数，提高了算法计数的时间效率。针对第二个问题，为δ时间戳范围内生成网络主题的邻接矩阵，运用ω-事件隐私机制为相邻时间戳邻接矩阵的变化量添加噪声进行干扰，避免后期进行随机游走时因噪声过大造成社区划分准确度低的问题，与此同时且有效保护了网络演化过程中局部子图的隐私信息。

本文主要的贡献如下：1）通过定义时序边统计在δ时间戳范围内生成的网络主题结构构建动态主题序列，运用快速算法统计真实社交网络上节点之间生成网络主题实例的个数。2）针对随时间戳动态变化的时序网络主题子图隐私泄露的问题，结合ω-事件差分隐私机制[10]对δ时间戳范围内相邻的网络主题邻接矩阵的变化量添加拉普拉斯噪声进行干扰，因为ω-事件差分隐私机制相比于其他隐私机制更好地控制了敏感度的大小；3）针对扰动后网络主题的邻接矩阵，提出了近似个性化页面排名算法，该排名算法对扰动后的邻接矩阵进行随机游走，其算法运行时间不受输入图形大小的影响，优于目前基于边的个性化页面方法。

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

3.1 算法简述

算法整体目标是运用有向无权图G=(V，E)，通过定义时序边序列，统计在δ时间戳内形成的网络主题，并统计主题在社交网络节点上形成的个数，由邻接矩阵Gw=(V，E，W)表示，权重W为节点之间生成网络主题实例的个数。随着时序网络中时序边的添加与删除生成的基于网络主题的邻接矩阵随时发生变化，针对网络在演化过程中局部子图隐私信息的泄露问题，对δ时间戳内相邻的网络主题邻接矩阵的变化量添加拉普拉斯噪声，对干扰后的邻接矩阵进行随机游走，对社交节点执行非重叠聚类划分，从而依据动态时序主题有效实现社交网络的局部高阶聚类挖掘。本算法运用时序网络中定义时序边的方法，为每一条定向边分配时间戳，构建动态主题序列；运用快速算法统计真实社交网络图在δ时间戳内生成的时序网络主题个数，运用邻接权重矩阵表示；对δ时间戳内相邻的邻接矩阵变化量运用ω-事件隐私保护机制分配隐私预算，进行干扰；针对干扰后的邻接矩阵，运用近似个性化页面排名算法进行随机游走，计算社交网络个体的特征向量，并对δ时间戳上社交个体的特征向量执行扫描操作，输出带有最小主题的电导，执行非重叠聚类划分操作。

3.2 算法详述

3.2.1 时序网络主题

时序网络主题作为时序网络中的基本单位，也是理解社交网络结构和功能的局部高阶子图，时序网络主题的节点之间包含许多带时间戳的链接，以时间戳变化为基础，定义时序边，生成动态时序网络主题。对于三角网络主题来说，由3个节点组成的子图结构，其中任意一对节点之间至少有一条有向边，在一个时序图上去统计生成的三角网络主题实例应当满足（1）运用快速静态图三角枚举算法[11]去查找由时序图[12]所诱导出静态图G中所有的三角网络实例；（2）对于每一个三角节点(u，v，w)，合并每对节点的所有时序边去获取含有时序边的列表。

对于三角网络主题，对给定中心节点的所有网络主题实例进行计数，只需遍历一次与中心节点相邻的边即可。如图3-4所示，三角主题的三类边形式如下，每一类都对应三个边上每个可能的方向。

图4 三类主题边

3.2.2ω-事件隐私机制的扰动

运用ω-事件隐私机制[10]以保护任意网络主题在任何连续时间戳上的隐私信息，事件隐私机制让主题实例M成为一种以流前缀St作为输入的机制，并且输出假设M可以分解为t个子机制使得 ，每一个Mi都能产生独立的随机性并实现εi-差分隐私。所以M满足ω-事件隐私时，ω-事件隐私可以在大小为ω的任何滑动窗口中设置总的隐私预算ε，并在时间戳中适当的分配隐私预算的一部分。

通过算法1对时序网络主题进行计数，将节点之间生成的网络主题个数运用邻接权重矩阵进行存储，矩阵中的权重表示两节点生成的网络主题M7的个数。选取特定时间戳上生成的基于网络主题的邻接矩阵，在时间戳为t时生成的主题邻接矩阵表示为记为At。t+1时刻的邻接矩阵为At+1，针对局部高阶子图从t时刻动态演变至t+1时刻网络主题邻接矩阵的变化量为At+1-At，即At+1=At+Δt，考虑到时间戳动态变化过程中基于网络主题的边隐私泄露情况，为邻接矩阵的变化量Δt添加拉普拉斯噪声进行干扰，公式如下：

εi表示为每一时间戳δ内生成的网络主题邻接矩阵分配的隐私预算。敏感度Δf为任意连续时间戳内生成网络主题个数变化量的最大值，也就是邻接矩阵中权重变化量的最大值。为邻接矩阵进行加噪干扰的伪代码如算法2所示：

3.2.3 基于扰动后网络主题的近似个性化页面排名算法

近似个性化页面排名算法基于网络主题权重图在给定种子节点的情况下，聚类划分出一个带有最小主题电导的集合。过程步骤如图5所示：

图5 局部高阶聚类划分

个性化页面排名的向量表示一个特定随机游走的平稳分布，随机游走的每一步中，都有参数随机游走者以概率1-α传送回特定种子节点u，以概率α执行随机游走的每一步。对其随机游走的平稳分布表示为其中，I是单位矩阵，P表示在图上进行随机游走的列随机转移矩阵，eu是种子节点u的指示向量，形式上定义P=AD-1，A是基于时序网络主题的邻接矩阵，D=diag(Ae)是节点的对角度矩阵，e是所有整数的向量。

Andersen等人[13]提出一种快速的近似个性化页面排名向量Pu通过向量其近似向量满足式4，ξ为损失参数。

将近似个性化页面排名算法应用于时序网络主题中，通过在时序网络邻接权重矩阵上进行随机游走计算近似个性化页面排名向量划分具有最小主题电导的聚簇，针对时序网络主题实例M，构建基于时序网络主题的邻接权重矩阵，对时序网络主题进行ω-事件隐私机制进行扰动后的邻接权重矩阵，作为近似化页面排名算法的输入；针对每一时间戳上的扰动邻接权重矩阵进行随机游走，计算基于邻接权重矩阵的近似化个性向量；执行扫描操作输出带有最小主题电导的集合。

其中随机游走后执行扫描操作的步骤即，通过随机游走计算向量的值，通过向量值降序对节点进行排列，计算该排序列表中每个前缀的电导，最终输出带有最小主题电导的前缀集合。

基于以上分析，对扰动后的基于时序网络主题的邻接矩阵进行近似个性化随机游走的算法步骤如算法3所示：

基于每一时间戳上扰动后的邻接权重矩阵，进行随机游走，计算节点的近似个性化向量，算法步骤如算法4所示：

3.3 隐私性分析

算法统计δ-时间戳范围内社交网络节点间生成网络主题的个数，将其作为ω-事件隐私机制的流输入，ω-事件隐私机制将加噪机制M分解为t个子机制M1，…，Mt使得针对相邻的邻接权重矩阵Di和Di+1，使得Mi(Di)=si，输出的每一个Mi都能产生独立的随机性并实现εi-差分隐私，因此对于任意算法满足差分隐私并行组合定理。所以隐私机制M满足ω-事件隐私当式5成立时。

ω-事件隐私可以在大小为ω的任何滑动窗口中计算总的隐私预算ε，并在特定时间戳范围内平均分配隐私预算。依据差分隐私并行组合定理2-6可以证明随时间戳动态变化生成的时序网络主题算法满足ω-事件ε-差分隐私。

4.实验结果与分析

4.1 实验环境

本文的实验硬件环境为：Intel(R) Core(TM) i5-6600U CPU@ 3.30GHz，8G内存，1T硬盘空间；软件环境为Windows10，64位操作系统，VirtualBox-6.0.6，Spyder3.6；数据集分别采用了有向无权的电子邮件网络[15]和来自Google+的社交网络[15]。由于这两个真实数据集节点和边的数据量较大，考虑运行时间以及运行效率的问题，因此只采用了数据集的部分数据进行实验。信息统计结果如表1所示：

表1 数据集信息统计表

4.2 实验结果分析

实验与Andersen[13]和Chung等人[14]在社交网络上实现局部聚类的算法进行实验对比，分别运用基于网络主题的电导，扩展的互信息化函数和F-度量三个评价指标来验证算法的有效性。扩展的互信息化函数（Extend Normalized Mutual Information ENMI）用于测量不同时间戳下社区划分的准确度，其值范围在[0，1]之间，计算划分的结果值越接近于1，划分的社区结果效果越准确。定义如下式6：

N为社交网络节点的个数，C"代表真实的社区结构，C"表示算法基于时序网络矩阵划分的社区结构，Ni表示在社区C"中第i个社区的节点个数，Nj表示在社区C"中第j个社区的节点个数，因此，Nij分别表示在社区C"中第i个社区和在社区C"中第j个社区共有的节点个数。

F-度量（F-measure Index）又称F-Score，用于评判不同时间戳下分配不同的隐私预算算法的聚类划分情况。定义如下式7：

其中，精确率为Pi，召回率为Ri，N表示聚类划分的社区个数，F-Score结合精确率和召回率综合评价整体社区划分情况。

实验针对2个数据集，分别选取不同数据节点个数，执行近似个性化随机游走计算的主题电导。email-Eu-core数据集选取的社交个体节点分别为20，40，60，80，100，120，140，随机游走后计算的主题电导如图3-8所示。因为ego-Gplus数据集数据量较大，则取2500，5000，7500，10000，12500，15000，17500，20000，随机游走后执行扫描操作计算的主题电导如图7所示。

图6 email-Eu-core数据集主题电导

图6，7表示的是特定数据集节点在不同时间戳下生成主题实例M进行随机游走计算主题电导的均值情况，分别选取δ时间戳取值范围为5，10，15，20，25，30（单位为秒）。对于email-Eu-core数据集，通过多次试验对比，在δ时间戳内生成网络主题实例频数最高的是M1，M2，M3，并且这三个网络主题实例分别在社交个体节点为80时，计算的主题电导最小，依据主题电导原理进行聚类划分效果最好，因此，选取社交个体节点为80时评估不同时间戳下社区划分的准确率。

同理，图7表示ego-Gplus数据集统计不同社交节点下生成的主题电导，ego-Gplus数据集在δ时间戳内生成的频数最高的网络主题实例为M7，M6，M3，M1，综合分析这四种网络主题实例在节点为10000时主题电导最小，聚类效果最好，所以选取节点数为10000进行社区划分的对比实验。

图8 email-Eu-core数据集

图8表示email-Eu-core数据集基于主题实例M2，M3进行聚类划分的对比实验。分别运用文献[13][14]中提出的随机游走算法与近似个性化页面排名算法进行对比，可知在时间戳为15，20时聚类划分的准确率最高。综合分析，在不同时间戳下，近似个性化页面排名算法较其他两种算法有较高的效用性。

图9 ego-Gplus数据集

图9表示ego-Gplus数据集基于主题实例M7，M6进行聚类划分的对比试验，由于主题实例M7是最具代表社交网络的局部高阶子图，从图4-4中可知运用实例M7进行社区聚类划分，准确率最高可达到0.9左右，相比较图4-4中M2，M3实例有明显优势。

图10表示email-Eu-core数据集基于网络主题实例M2分配隐私预算的情况，依据图10中a），b）得知，针对不同页面排名算法，对于同一网络主题实例，在相同时间戳下对邻居权重矩阵分配隐私预算进行干扰，分配的隐私预算越小，产生的误差越大，因此聚类划分的准确性越低。

图11表示ego-Gplus数据集基于网络主题实例M7分配隐私预算的情况，执行近似化个性页面排名算法之后，针对同一网络主题实例M7，在时间戳为15的情况下，隐私预算分配0.5的F-score值为0.57，当隐私预算分配0.75时F-score值为0.63，表明同一条件下，隐私预算越大，产生的噪声越小，对比实验的聚类准确度越高。

图10 email-Eu-core数据集网络主题实例为M2

图11 ego-Gplus数据集网络主题实例M7