0 概述

随着社会网络的发展以及各种社交App的快速普及, 网络用户人数不断增加。目前, Facebook用户总数约为21.7亿, 微信用户总数约为9.8亿, 截至2018年3月31日, 支付宝为约8.7亿位活跃用户提供服务。用户在使用社会网络的过程中产生了大量社会网络数据, 对于实际社会网络有向图, 一些具有相同爱好或者相似属性的用户还会形成各种特定的群体, 即社会网络的社区结构。因此, 对大规模社会网络有向图发布时的社区结构进行分析具有重要意义。文献[1]指出由于社会网络具有结构特征, 简单的删除标识属性不能防止攻击者通过其他背景知识识别出目标用户。因此, 研究人员针对不同的隐私信息提出了不同的隐私保护模型, 如图修改模型^[2-4]、聚类泛化模型^[5-6]、数据扰动模型^[7]和差分隐私模型^[8]等。但是, 目前大部分隐私保护技术仅针对社会网络无向图来保护个人隐私信息, 忽略了对社会网络有向图社区结构的保护。

为满足K-出入度匿名并有效保护大规模社会网络有向图的社区结构, 本文基于GraphX图数据处理平台, 建立基于层次社区结构的大规模社会网络K-出入度匿名模型, 并提出一种K-出入度匿名(KIODA)算法。

1 相关工作

目前, 社会网络隐私保护信息主要包括节点隐私、边隐私和图性质隐私3种^[9]。针对不同的社会网络隐私保护信息, 文献[7]提出一种新的匿名方法, 即拆分匿名化, 通过拆分匿名处理的社交网络可以抵御直接攻击。文献[10]提出无向图的k-度匿名概念, 其要求图中任何节点都至少有k-1个节点与其度数相同, 使用贪心策略增加边来实现匿名, 从而抵御节点度属性攻击。文献[11]提出一种UMGA算法, 其采用贪心算法和穷举法生成匿名度序列, 通过随机边选择和邻居中心性边选择方法修改无向图从而实现k-度匿名。文献[12]提出一种改进的K-度匿名算法, 该算法保留了个人隐私信息以及社交网络结构属性。文献[13]提出一种图形结构感知的分层k-匿名技术, 其根据幂律分布的特征划分节点, 在隐私保护过程中分析图形的结构特征, 根据图形结构特征调整边缘。文献[14]提出一种保持网络结构稳定性的k-度匿名隐私保护模型SimilarGraph, 该模型运用动态规划方法对社会网络按照节点度序列进行最优簇划分, 通过移动边操作方式重构网络图以实现图的k-度匿名化。文献[15]针对有向图提出了可达性保持图匿名化方法, 通过图修改来防止隐私泄露, 同时保证匿名图在社会网络分析和图查询方面的数据可用性。文献[16]提出一种保护链接关系的分布式匿名方法PLRD-(k, m), 其将互为N-hop邻居的节点分为一组并进行k-度匿名和m-标签匿名, 保证攻击者无法通过度和标签识别出目标并保护链接关系不被泄露。现有的隐私保护方法虽然减少了图修改的信息损失, 但改变了原始图的网络连通性, 在匿名过程中没有考虑社会网络图的社区结构, 从而影响了社区结构的性质分析并降低了所发布数据的使用价值。

在进行大规模社会网络隐私保护的同时保护社会网络图的社区结构成为国内外学者关注的热点。文献[17]在保持总体图谱不变的前提下, 通过节点之间相似度的比较来随机增删k条边。文献[18]利用基于图分割理论的社区划分算法计算拉普拉斯矩阵, 设置谱约束条件, 从而计算增删边的约束。文献[19]提出一种局部扰动的k-匿名技术, 在节点分组时使属于相同社区的节点分到一个组内, 根据节点相似性重构社会网络无向图。文献[20]利用粗糙集的上近似概念划分社区并进行匿名, 匿名前后保持图的社区结构性质。文献[21]提出一种新的边缘修改技术, 对图表进行匿名化时较好地保留了图形社区结构, 匿名后社会网络K核数保持不变, 即保持社区结构不变。

目前, 多数社会网络隐私保护方法存在处理大规模社会网络有向图时数据效率低、忽略了对社会网络有向图社区结构进行保护的问题, 因此, 本文提出一种基于层次社区结构的KIODA算法, 以提高数据处理效率并保证数据发布时社区结构分析结果的可用性。

2 预备知识与问题定义

将社会网络表示为有向图G=(V, E), 其中, V(G)和E(G)分别表示图G的节点集合和边集合。边 < u, v>表示从节点u指向v的一条边, 边<u,v>称为u的出边、v的入边, 节点u的入边数目是u的入度数, 记作d_in(u), 节点u的出边数目是u的出度数, 记作d_out(u), 节点u的出入度用(d_in(u), d_out(u))表示。

2.1 基于层次社区结构的社区划分

定义1(有向图层次社区树H_G)  给定一个社会网络有向图G, 用层次随机图HRG来表示有向图G的社区结构, 记作有向图层次社区树H_G。H_G的叶子节点表示有向图G中的节点, H_G中的每个内部节点r代表叶子节点的连接概率P_r, T_r是H_G的一个内部节点r的子树, 左子树T_r^L中的叶子节点与右子树T_r^R中的叶子节点在有向图G中的连接概率用P_r表示, 其反映左子树与右子树叶子节点的联系强度, P_r越大, 节点联系越紧密。P_r的计算公式为:

$ {P_r} = \frac{{\left| {{E_r}} \right|}}{{\left| {T_r^R} \right| \cdot \left| {T_r^L} \right| \cdot 2}} $

(1)

社会网络有向图G的HRG不是唯一的, 因此, 选择最优的HRG, 进而根据有向图层次社区树H_G得到社会网络有向图的社区结构。对于不同的HRG, 可以采用似然函数L来评价其对社会网络有向图G的合适程度。

定义2(似然函数L)  似然函数L是社会网络有向图G产生H_G的后验函数, 选取L值最大的HRG树作为有向图G的H_G。L的计算公式为:

$ L\left( {{H_G}} \right) = {\prod\limits_{r \in {H_G}} {\left[ {P_r^{{P_r}}{{\left( {1 - {P_r}} \right)}^{1 - {P_r}}}} \right]} ^{\left| {T_r^R} \right| \cdot \left| {T_r^L} \right| \cdot 2}} $

(2)

图 1(a)所示为社会网络有向图G₀, 图 1(b)~图 1(d)为社会网络有向图G₀的3个可能HRG。

对有向图G₀列出3个可能的HRG, 计算似然函数L的值。经计算, 图 1(b)的L=4.639e^-7, 图 1(c)的L=6.465e^-5, 图 1(d)的L=4.255e^-6, 其中, 图 1(c)的L值最大, 因此, 选择H_G0²作为有向图G₀的H_G0, 社区划分结果如图 2所示。

2.2 大规模社会网络K-出入度匿名模型

在社会网络无向图中, 攻击者可以通过度攻击识别出目标节点, 但是对于社会网络有向图, 节点具有出度数和入度数。因此, 本文构建一种出入度攻击模型。

定义3(出入度攻击)  假设攻击者知道目标节点的入(出)度数, 或者同时知道入度数和出度数, 攻击者通过这些背景知识能够识别出唯一目标节点, 这种攻击被称为出入度攻击。

如图 3所示, 假设攻击者知道目标节点的出度数为2, 可以识别出Alice、Kayla和Bob。如果攻击者还知道目标节点的入度数为1, 则能识别出唯一目标节点Alice, 导致Alice节点的隐私信息泄露。

传统的K-度匿名技术仅针对社会网络无向图, 忽略了边的方向性, 但是实际的社会网络图中的边存在方向, 因此, 本文针对社会网络有向图抵御出入度攻击, 构造K-出入度序列进行K-出入度匿名。

定义4(K-出入度匿名)  给定社会网络有向图G=(V, E)和正整数K, 对于有向图中任意节点v∈V(G), 均存在m(m≥K-1)个其他节点与节点v的入度数和出度数相等, 即d_in(v)=d_in(v_i), d_out(v)=d_out(v_i)(1≤i≤m), 则称有向图G为K-出入度匿名图。

定义5(基于层次社区结构的大规模社会网络K-出入度匿名模型)  给定社会网络有向图G=(V, E)和正整数K。根据如下3个步骤得到的匿名社会网络有向图G^*=(V^*, E^*), 即符合基于层次社区结构的大规模社会网络K-出入度匿名模型:

1) 基于层次社区结构划分社区, 确定原始社会网络有向图G中节点所属的社区。

2) 对社会网络有向图G中节点的出入度序列进行排序、分组并匿名, 得到K-出入度匿名序列。

3) 根据K-出入度匿名序列分布并行构造匿名图, 基于GraphX传递节点间信息并迭代进行虚拟节点对合并与删除, 提高数据发布时社区结构分析结果的可用性。

如图 4所示, 有向图G^*为社会网络有向图G的3-出入度匿名图, 其中, K=3, 节点1~节点7属于社区1, 节点8~节点11属于社区2, 节点12~节点14属于社区3。对于任意节点v, 均存在至少2个节点与其具有相同的入度数和出度数, 即攻击者不能以大于1/3的概率唯一识别出目标节点, 从而满足了K-出入度匿名并保证了数据发布时社区结构分析结果的高可用性。

3 K-出入度匿名算法

基于层次社区结构的大规模社会网络K-出入度匿名算法KIODA结合了为大规模数据处理而设计的计算引擎Spark, 算法在分布式并行环境下执行, 对大规模社会网络数据实现并行高效的隐私保护。

3.1 基于层次社区结构的社区划分算法

基于层次社区结构的社区划分算法首先得到社会网络有向图的HRG, 然后借助马尔科夫蒙特卡洛抽样方法^[22]收敛筛选出较优的层次随机图H_G, 进而得到社会网络图的社区结构。HRG生成算法描述如下:

算法1  Construst_HRG(G, ε₁)算法

输入  原始图G, 差分隐私参数ε₁

输出  H_G

1.根据Markov chain随机生成原始图G的一个HRG, 作为T₀;

2.t←1;

3.while Markov chain is not converged do

4.Randomly select an internal node n in T_t-1

5.Generate HRG T′ by randomly transforming

adjacent subtrees of node n

//通过随机交换节点n的相邻HRG生成T′

6.if the probability of transformation satisfies

$ \min \left( {\frac{{\exp \left( {\frac{{{\varepsilon _1}}}{{2\Delta {\rm{u}}}}{{\log }_{\rm{a}}}{\rm{L}}\left( {{\rm{T'}}} \right)} \right)}}{{\exp \left( {\frac{{{\varepsilon _1}}}{{2\Delta {\rm{u}}}}{{\log }_{\rm{a}}}{\rm{L}}\left( {{{\rm{T}}_{{\rm{t - 1}}}}} \right)} \right)}}, 1} \right)\;\;\;{\rm{then}} $

7.T_t=T′;

8.else

9.T_t=T_t-1;

10.end if

11.t=t+1;

12.end while

13.return H_G=T_t;

算法1随机选择一个HRG来初始化马尔科夫链, 第3行~第12行多次迭代直到马尔科夫链收敛。设马尔科夫链的当前状态为T_t-1, 随机选择一个内部节点n, 替换n的相邻HRG产生下一个状态T′。由于选择具有随机性, T′不唯一, 通过计算似然函数L的值筛选较优的T′。第6行~第10行通过比较交换前后L的误差值, 借助马尔科夫蒙特卡洛抽样方法, 设置状态交换接受率为$\min \left( {\frac{{\exp \left( {\frac{{{\varepsilon _1}}}{{2\Delta u}}{{\log }_a}L\left( {T'} \right)} \right)}}{{\exp \left( {\frac{{{\varepsilon _1}}}{{2\Delta u}}{{\log }_a}L\left( {{T_{t - 1}}} \right)} \right)}}, 1} \right)$。迭代结束, 马尔科夫链收敛, 得到较优的H_G。图 3所示的有向图G生成的较优H_G如图 5(a)所示, 社区划分结果如图 5(b)所示。

3.2 K-出入度序列分组匿名算法

针对社会网络有向图, 本文提出Sequence Partition(G, k)算法, 同一组中目标出入度的入(出)度数为该分组中所有入(出)度数的最大值, 即goal(in_deg, out_deg)=(max{分组中所有元素的in_deg}, max{分组中所有元素的out_deg})。K-出入度序列分组匿名算法描述如下:

算法2  Sequence Partition(G, k)算法

输入  原始有向图G, 匿名参数k

输出  K-出入度匿名序列d^~

1.MF_Seq=[];

2.for each node < in_deg, out_deg> do

3.Insert in MF_Seq;

4.end for

5.Sort(MF_Seq) by < in_deg, out_deg>;

6.last_partition_index=0;

7.for v_i∈MF_Seq do

8.for l=last to i-1 do

9.goal_1(in_deg, out_deg)=max(in_deg[i], out_deg[i]);

10.end for

11.for m=i to i+k do

12.goal_2(in_deg, out_deg)=max(in_deg[m+1], out_deg[m+1]);

13.goal_3(in_deg, out_deg)=max(in_deg[m], out_deg[l]);

14.end for

15.SPC1=goal_1-MF_Seq[i], SPC2=0;

16.for j=i+1 to i+k do

17.SPC1=SPC1+goal_3-deg[j-1];

18.SPC2=SPC2+goal_2-deg[j];

19.end for

20.if SPC2 < SPC1 then

21.last_partition_index=i;

22.i=i+k;

23.else

24.i++;

25.end if

26.end for

算法2第2行~第14行根据节点出入度进行排序, 求出目标出入度。第16行~第25行判断SPC1、SPC2值的大小并进行分组。其中, SPC1表示将当前元素合并到上一组中的匿名化成本, SPC2表示将当前元素和后面k-1个元素形成新组的成本。如果SPC2 < SPC1, 该元素将和后面k-1个元素形成一个新组, 反之则合并到上一组。原始图G的分组匿名过程如图 6所示。

图 6(a)表示初始出入度序列d。假设k=3, 前3个元素先被放入一个组中, 如图 6(b)所示。判断第4个元素的分组情况, 如图 6(c)所示, 此时goal_1=(3, 3), goal_2=(2, 3), goal_3=(2, 3), SPC1=cost₁+cost₂=3, SPC2=cost₃=1。SPC1>SPC2, 因此, 第4个元素和后面2个元素形成新组, 再判断第7个元素的分组情况。最终分组结果如图 6(d)所示, 得到的K-出入度匿名序列d^~如图 6(e)所示。

3.3 选择虚拟节点对合并删除算法

根据K-出入度匿名序列分布并行构造匿名图, 添加虚拟节点得到图 7所示的匿名社会网络有向图G′。为了减少信息损失, 本文基于GraphX图数据处理平台, 通过节点间的信息传递实现虚拟节点对的合并删除, 提高所发布数据的可用性。

信息传递的数据结构用五元组(dstid, srcid, hops, community, tags)表示, 称五元组为n-跳邻居列表(n-Hops Neighborhood Table, HNT), 其中, dstid表示目的节点ID, srcid表示源节点ID, hops表示跳数, community表示源节点所属社区, tags表示节点标志位(初始时tags=0), tags=1表示源节点和目的节点均为虚拟节点。

初始化匿名图G′的结果如图 8所示(仅列出部分虚拟节点初始HNTE(n-Hops Neigh-borhood Table Entry))。在初始时, 节点的dstid和srcid都是节点的ID, hops=0, tags=0, 如节点f₂的HNTE={f₂, f₂, 0, 1, 0}。

定义6(有向图层次社区熵)  用有向图层次社区熵(DGHCE)量化添加边操作对社区层次结构的影响, 记作DGHCE(G, H_G), 其计算公式为:

$ \begin{array}{l} {\rm{DGHCE}}\left( {G, {H_G}} \right) = \\ - \sum\limits_{t = 1}^{\left| V \right| - 1} {\frac{{\left| {T_r^R} \right| \cdot \left| {T_r^L} \right| \cdot 2{P_r}}}{{\left| E \right|}}} 1{\rm{b}}\frac{{\left| {T_r^R} \right| \cdot \left| {T_r^L} \right| \cdot 2{P_r}}}{{\left| E \right|}} \end{array} $

(3)

定义7(有向图层次社区熵变化值)  用DGHCE的变化值UL衡量虚拟节点对合并删除后添加的边操作造成的信息损失, 其计算公式为:

$ {\rm{UL}}\left( {G, G'} \right) = \left| {{\rm{DGHCE}}\left( {G, {H_G}} \right) - {\rm{DGHCE}}\left( {G, {{H'}_G}} \right)} \right| $

(4)

定义8(虚拟节点对合并删除条件VNMDC)  设存在边 < u, f_w>和边 < f_x, v>, 虚拟节点对(f_w, f_x)能够进行合并删除, 当且仅当∀(f_w, f_x)∈VirtualSet满足以下3个条件:

1) f_w, f_x∉VirtualRDD。

2) < u, v>∉EdgeRDD。

3) u≠v。

定理1  对于虚拟节点对(f_w, f_x), VNMDC条件是(f_w, f_x)能够合并删除的充分条件。

证明  如图 9(a)所示, 合并删除虚拟节点对(f_w, f_x), 需删除边 < u, f_w>、< f_x, v>并添加边 < u, v>, 但是有向图G中已经存在边 < u, v>, 故(f_w, f_x)不能合并删除。同理, 如图 9(b)所示, 虚拟节点f_w、f_x均与节点u相连, 不能添加边 < u, v>, 故(f_w, f_x)不能合并删除。因此, 当且仅当虚拟节点对(f_w, f_x)满足VNMDC条件时, (f_w, f_x)能够合并删除, 如图 9(c)所示。

通过节点间的信息传递得到每次迭代的虚拟节点对集合VirtualSet, 判断∀(f_w, f_x)∈VirtualSet是否满足VNMDC条件, 将满足条件的虚拟节点对放入候选虚拟节点集合CandidateSet中。选择虚拟节点对合并删除算法Select Merge_Delete(CandidateSet)描述如下:

算法3  Select Merge_Delete(CandidateSet)算法

输入  候选合并删除节点集合CandidateSet

输出  虚拟节点对(f_w, f_x)

1.M = Number of same community in CandidateSet;

2.N = CandidateSet.size;

3.if (N >1) then

4.if (M >1 || M==0) then

5.(f_w, f_x)=the min(UL) from CandidateSet;

6.return (f_w, f_x);

7.end if

8.if (M=1) then

9.return (f_w, f_x);

10.end if

11.else

12.return (f_w, f_x)

若候选虚拟节点对集合CandidateSet中虚拟节点对个数大于1, 执行算法3第4行~第7行, 对于同一社区(或均为不同社区)的虚拟节点对计算DGHCE值, 选择UL值小的虚拟节点对进行合并删除。如果虚拟节点对个数为1, 执行算法3的第8行~第12行直接选择虚拟节点对(f_w, f_x)。

3.4 KIODA算法步骤

本文基于层次社区结构的大规模社会网络K-出入度匿名算法KIODA描述如下:

算法4  KIODA算法

输入  原始图G, 匿名参数k

输出  匿名图G^*

1.基于Construst HRG算法生成H_G;

2.基于Sequence Partition(G, k)算法生成K-出入度匿名序列d^~;

3.根据匿名序列添加虚拟节点, 得到匿名图G′;

4.初始化匿名图G′, CandidateSet=Ø, VirtualRDD=Ø;

5.for SuperStep=1 to 6 do

6.Dst.Message ← Src.Message; //源节点将更新的//HNTE信息发送到目的节点

7.for (Message from Dst.HNTE) do

8.if (Message.Tags==1) then

9.Dst.VirtualSet ← Message;

10.end if

11.end for

12.for (Message from Dst.VirtualSet) do

13.f_w=Message.srcid, f_x=Message.disid;

14.if (f_w, f_x) satify VNMDC then

15.CandidateSet ← (f_w, f_x);

16.end if

17.end for

18.if CandidateSet.size > 0 then

19.(f_w, f_x)=Select Merge_Delete(CandidateSet);

20.G′.EdgeRDD.Remove < u, f_w>;

21.G′.EdgeRDD.Remove < f_x, v>;

22.G′.EdgeRDD.Add < u, v>;

23.VirtualRDD.Add (f_w, f_x);

24.VoteToHalt (f_w, f_x);

25.end if

26.end for

27.return G^*

KIODA算法具体步骤如下:

1) 在Superstep=0时, 节点初始化得到初始边集合EdgeRDD。

2) 在Superstep=1时, 进行第1次迭代。节点收到自己的1跳邻居信息, 生成1-跳邻居列表。第1次迭代标志位均为0, VirtualSet=Ø, CandidateSet=Ø。

3) 在Superstep=2时, 进行第2次迭代, 2-跳邻居列表如表 1所示(仅列出部分虚拟节点), 查看是否存在tags=1。迭代得到VirtualSet={(f₂, f₁)}, 由于虚拟节点f₂、f₁均与节点1相连, 不满足VNMDC条件, 故不能进行合并删除, CandidateSet=Ø。

4) 在Superstep=3时, 进行第3次迭代, 3-跳邻居列表如表 2所示(仅列出tags=1的节点), 迭代得到VirtualSet={(f₁₀, f₁₁), (f₉, f₁), (f₆, f₅), (f₆, f₁₁)}。

虚拟节点对(f₁₀, f₁₁)不满足VNMDC条件, 不能合并删除, 故CandidateSet={(f₉, f₁), (f₆, f₅), (f₆, f₁₁)}。执行KIODA算法第20行~第24行合并删除虚拟节点对(f₉, f₁), 将边 < 3, 1>添加到EdgeRDD中, 删除边 < f₁, 1>、< 3, f₉>; 虚拟节点f₉、f₁添加到VirtualRDD中, 状态设为InActive, 停止迭代。虚拟节点对(f₆, f₅)、(f₆, f₁₁)执行算法3计算DGHCE的变化情况, 选择UL值小的虚拟节点对进行合并删除。若合并删除(f₆, f₅), 有向图层次社区树H_G的连接概率P₁由1/2变为1;若合并删除(f₆, f₁₁), P₂由1/2变为3/4, 如图 10所示。

经计算, 原始图的DGHCE=3.574 15, DGHCE_{f6, f5} =3.593 27, UL_{f6, f5}=0.019 12, DGHCE_{f6, f11}=3.563 07, UL_{f6, f11}=0.011 08, 因此, 选择合并删除虚拟节点对(f₆, f₁₁), 此时VirtualRDD={f₉, f₁, f₆, f₁₁}。第3次迭代停止, 结果如图 11所示。

KIODA算法在迭代6次后停止虚拟节点对合并删除, 得到如图 12所示的匿名社会网络有向图G^*。

4 实验结果与分析

本节将KIODA算法与快速K-度匿名(KDA)算法^[10]、VA(VertexAddition)算法^[23]进行性能分析与比较。

4.1 实验设置

本次实验采用斯坦福大学公开的2个真实社会网络有向图数据集Eu-Email和Epinions。Eu-Email网络是欧洲大型研究机构在2003年10月—2005年5月期间的电子邮件数据, 其中, 给定一组电子邮件消息, 每个节点对应一个电子邮件地址, 有向边 < i, j>表示节点i向j发送一条消息。Epinions网络是一个消费者的在线评论社交网络, 网站成员可以决定是否“互相信任”, 有向边 < u, v>表示用户u信任用户v。表 3所示为数据集相关统计数据。实验使用的处理工具是GraphX, 算法运行环境为15个计算节点, 1.8 GHz CPU, 16 GB RAM, Hadoop 2.7.2, Spark2.2.0, 采用Scala 2.11.12编程。

4.2 算法性能分析

图 13所示为随着隐私值k的变化, 算法的运行时间对比结果。从图 13可以看出, 随着k值的增加, 各算法的运行时间也随之增加, 其中, KDA算法运行时间最短, KIODA算法运行时间最长。这是因为KIODA算法首先要基于层次社区结构对原始图进行社区划分, 然后再对出入度序列分组匿名, 最后合并删除虚拟节点对, 随着k值的增加, 需要添加更多的虚拟节点, 同时为了减少信息损失, 要对更多的虚拟节点对进行合并删除操作。因此, KIODA算法的执行时间略大于KDA算法和VA算法, 但是总体而言, KIODA算法的运行时间在可接受范围内。

4.3 信息损失分析

为了比较算法在匿名过程中的信息损失, 测试算法匿名后平均出/入度数的变化情况。图 14所示为随着k值的增加, 3种算法在不同数据集中的平均出/入度数对比结果。从图 14可以看出, 随着k值的增加, VA算法在匿名后节点的平均度数变化较大, 而KDA算法和KIODA算法匿名后节点的平均度数更接近于原始平均度数。这是因为VA算法通过添加节点来实现K-匿名, 匿名后造成节点的平均度数变化大, 对图结构的影响较大, 信息损失大; KDA算法和KIODA算法尽可能减少图的修改, 因此, 匿名后平均节点度数变化较小, 图信息损失较小。

聚集系数(Clustering Coefficient, CC)是用来描述一个图中顶点之间聚集程度的系数。匿名后平均聚集系数(Average Clustering Coefficient, ACC)变化越小, 匿名过程对社区变化的影响越小。为了衡量算法匿名过程中在图结构方面的信息损失, 测试匿名图ACC的变化率如下:

$ {\rm{Changeradio}} = \left| {{\rm{AC}}{{\rm{C}}^*} - {\rm{ACC}}} \right|/{\rm{ACC}} \times 100\% $

(5)

其中, ACC^*表示匿名后的平均聚类系数值。

图 15所示为3种算法匿名后ACC的变化率情况, 从图 15可以看出, KDA算法和VA算法在匿名后ACC的变化率均大于KIODA算法。这是因为KDA算法对图的修改最少, VA算法添加节点实现最佳K-匿名化。KDA算法和VA算法在匿名时仅考虑满足K-匿名, 而不考虑节点所属社区情况, 因此, ACC变化率较大, 匿名后社区结构可用性低。随着k值的增加, KIODA算法的ACC变化率很小, 因此, KIODA算法更好地保证了有向图的图结构性质, 减少了社区结构的信息损失。

4.4 数据可用性分析

μ_i(0=μ₁≤μ₂≤…≤μ_m≤m)是拉普拉斯矩阵L的特征值, L的第二小特征值(μ₂)是其重要的一个特征值, 用来表示社区的分离方式。图 16所示为随着k值的增加, 3种算法在不同数据集中的μ₂值与原始图的相似性比较结果。

从图 16可以看出, KIODA算法的μ₂值与原始图更相似。这是因为KIODA算法在合并删除虚拟节点对时考虑了原始图的社区结构, 而KDA算法和VA算法在匿名时忽略了对社区结构的保护, 给社区结构造成了很大的损失。

在匿名过程中, 为了衡量算法在社区结构方面的可用性, 引入精度指标(Precision index)^[24]衡量节点所属社区变化情况。若节点在原始图所属社区与匿名后的社区相同, 则ρ_{ltv(v)=lpv(v)}值为1;若节点在原始图所属社区与匿名后的社区不同, 则ρ_{ltv(v)=lpv(v)}的值为0。精度指标的范围在[0, 1]之间, 若精度指标的值为0, 则原始图与匿名图的社区划分完全不同; 若精度指标的值为1, 则原始图与匿名图的社区划分相同。精度指标计算公式如下:

$ {\rm{Precision}}\;{\rm{index}} = \frac{1}{n}\sum\limits_{v \in G} {{\rho _{{l_{tv}}(v) = {l_{pv}}\left( v \right)}}} $

(6)

图 17所示为3种算法匿名后节点所属社区的变化情况。从图 17可以看出, KDA算法和VA算法在匿名过程中没有考虑节点的社区情况, 因此匿名后节点所属社区变化率很大。KIODA算法在合并删除虚拟节点对时尽可能保证了节点所属社区不变, 因此匿名后社区的精度指标更接近于1, 其更好地保持了匿名图在社区划分方面的数据可用性。

5 结束语

针对大规模社会网络有向图的隐私保护问题, 本文构建一种新的出入度攻击模型并提出基于层次社区结构的大规模社会网络K-出入度匿名算法。该算法基于层次社区结构划分社区, 根据贪心算法分组并匿名出入度序列, 对虚拟节点对进行合并删除以减少信息损失, 在合并删除虚拟节点对的过程中保持原始图中节点所属社区不变。基于真实社会网络数据集的实验结果表明, 在分布式并行环境下执行该算法, 能够对大规模社会网络数据进行并行高效的隐私保护, 与传统K-度匿名算法相比, 其提高了大规模社会网络有向图数据的处理效率, 更好地保证了数据发布时社区结构分析结果的可用性, 在节点平均出/入度数变化、平均聚类系数、拉普拉斯矩阵第二小特征值(μ₂)以及社区结构保护等方面都取得了很好的效果。本文算法在保证社区结构分析结果可用性的基础上保护了节点的隐私信息, 但是, 目前该算法仅针对具有相同隐私保护等级的用户, 下一步将针对不同隐私保护等级的用户, 研究个性化的K-出入度匿名方法。