1 引言

随着互联网的快速发展, 在线社交网络在全世界普及, 社交网络的运营商收集了大量用户数据, 如果通过简单的匿名化处理将用户数据提供给第三方(研究人员、市场营销等)使用, 就会出现隐私泄漏的风险^{[1, 2]}. 因此, 社交网络的隐私安全越来越受到人们的关注, 运营商需要在发布数据之前, 对用户数据进行匿名化处理, 确保用户隐私不会泄漏^[3]; 同时尽可能地保留社交网络的结构特性, 从而保证数据的实用性^{[4, 5]}.

基于图结构变换的匿名方法^[6], 能够有效地解决社交网络中用户的隐私保护问题. Backstrom等人^[7]指出使用无意义的唯一标识符替换用户的身份作匿名化处理, 并不能防止用户隐私泄漏. Hay等人^[8]发现利用节点周围的结构信息仍然能够在匿名图中重新识别该节点, 这种结构信息与节点及其邻居节点的度有关. Liu等人^[9]基于k匿名性, 提出了k度匿名化模型, 这种匿名保护能够有效抵御以节点度数为背景知识的隐私攻击, 使得每个节点被重新识别的概率不大于 ${1 \mathord{\left/ {\vphantom {1 k}} \right. } k}$ .

针对k度匿名化问题, Liu等人^[9]基于动态规划思想生成匿名度序列, 根据该序列通过添加边的方式去构建图, 由于构图操作并不能保证一定成图, 所以需要构图测试, 这会增加算法运行时间; 而且构图操作的随机过程导致原图结构信息的损失. Lu等人^[10]提出了一种贪心匿名化算法, 在给原图添加边的同时进行度序列的匿名化, 直接在原图上进行加边能够避免度序列的构图测试, 但是同步匿名化需要添加较多的边来实现图匿名化.

Chester等人^{[11, 12]}提出了加点的匿名化策略, 基于动态规划思想生成匿名度序列, 通过新节点与原图节点连边满足节点匿名要求, 然而加点太多导致原图结构信息的损失. Ma等人^[13]结合加边且可加点的匿名化策略提出匿名化算法, 利用贪心法生成匿名度序列, 并基于社区结构进行加边, 这种匿名化方式能较好地保留图的某些结构特性, 但添加的边或节点数较多. 吴童^[14]结合加边且可加点的匿名化策略提出了改进算法, 利用Liu等人^[9]提出的动态规划匿名分组算法生成匿名度序列, 根据该序列贪心加边; 若加边不能完成匿名化, 则进行加点完成图匿名化. 由于未充分利用原图中的点进行加边, 导致添加的节点数较多. Rajabzadeh等人^[15]利用Ma等人^[13]提出的贪心分组算法和基于模块度的社区发现算法^[16]确定每个社区内节点的匿名化代价, 然后通过遗传算法决定每个社区内的节点之间如何连边, 从而实现图的度匿名化. 本文的主要贡献包括:

(1) 结合加边且可加点的策略, 改进了匿名化方式, 分两个阶段进行加边, 这种匿名方式能有效减少添加的边或节点.

(2) 在加边操作中, 考虑节点度、社区结构和节点距离等因素选择目标节点进行连边, 这种操作能够有效保留原图的某些结构特性.

(3) 在多个真实数据集上进行了大量实验, 实验结果验证了新算法的有效性.

2 预备知识

本文将社交网络建模为无向图 $ G(V{\text{, }}{\kern 1pt} E) $ , 其中, $V$ 是节点集, $E$ 是边集. 令节点个数 $n = \left| V \right|$ , $V = \{ {v_1}, {v_2}, \cdots, {v_n}\} $ , 则称图 $G$ 所有节点的点度序列 ${{\boldsymbol{d}}_G} = \{ {{\boldsymbol{d}}_G}({v_1}), {{\boldsymbol{d}}_G}({v_2}), \cdots , $ $ {{\boldsymbol{d}}_G}({v_n})\} $ 为图 $G$ 的度序列, 其中, ${{\boldsymbol{d}}_G}({v_i})$ 为图 $G$ 中节点 ${v_i}$ 的度数. 为了方便讨论, 不妨假设图 $G$ 的度序列为非递增序列, 由此, 图 $G$ 最小点度为 ${\delta _G} = {{\boldsymbol{d}}_G}({v_n})$ , 最大点度为 ${\Delta _G} = {{\boldsymbol{d}}_G}({v_1})$ .

给定无向图 $G$ 和正整数 $k\;({\delta _G} \leqslant k \leqslant {\Delta _G})$ , 当且仅当图中每个节点至少与 $k$ −1个其他节点具有相同的度, 则称图 $G$ 是 ${ k}$ 度匿名图, 其度序列称为 ${ k}$ 度匿名度序列.

设图 $G$ 不是k度匿名图, 通过在图 $G$ 中添加边得到新图 $G'$ , 使得 $G'$ 是k度匿名图, 称序列 ${{\boldsymbol{d}}_{G' }} = \{ {{\boldsymbol{d}}_{G\prime }}({v_1}), \cdots, $ $ {{\boldsymbol{d}}_{G' }}({v_n})\}$ 为图 $G'$ 的k度匿名度序列. 令 ${{\boldsymbol{d}}_{{\text{Cost}}}} = \{ {{\boldsymbol{d}}_{G' }}({v_1}) - $ $ {{\boldsymbol{d}}_G}(v{}_1), \cdots, {{\boldsymbol{d}}_{G' }}({v_n}) - {{\boldsymbol{d}}_G}({v_n})\}$ 为匿名代价序列. 为了方便操作, 不妨假设匿名代价序列为非递增序列, 其中, ${{\boldsymbol{d}}_{G' }}({v_i}) - {{\boldsymbol{d}}_G}({v_i})$ 表示节点 ${v_i}$ 的匿名化代价.

图匿名问题可描述如下: 给定无向图 $G$ 和正整数 $k\;({\delta _G} \leqslant k \leqslant {\Delta _G})$ , 构造图 $G$ 的k度匿名图 $G'$ 满足 $G \subseteq G'$ , 且使得 ${\textit{diff}}(M(G), M(G' ))$ 可能小. 其中, $M(G)$ 表示图 $G$ 的某个结构特性(平均路径长度等), 而 ${\textit{diff}}(M(G), M(G' ))$ 表示两个图在某个结构特性上的差异程度. 即要求图 $G$ 的k度匿名图 $G'$ 满足 ${\boldsymbol{mi}}{{\boldsymbol{n}}_{G \subseteq G' }}{\textit{diff}}(M(G), M(G' ))$ . 由于图的结构特性的多样性, 本文将图的3种典型的结构特性(平均路径长度、平均聚类系数、传递系数)作为匿名效果的度量指标, 使得匿名图与原图在这3种结构特性上的差异尽可能小.

3 算法模型

新算法包括如下子算法: 匿名分组算法、加边算法、加点算法、层次社区发现算法. 新算法思想是利用贪心匿名分组算法生成匿名度序列, 基于层次社区结构加边, 优先满足匿名代价大于平均匿名代价的节点的匿名要求; 然后再次利用贪心匿名分组算法得到匿名度序列, 通过同样的加边操作满足未匿名节点的匿名要求; 若加边不能完成匿名化, 则通过加点实现图匿名化.

3.1 匿名分组算法

本文采用Liu等人^[9]提出的贪心匿名分组算法, 首先形成一个包含前 $k$ 个最高度节点的组, 并把组内节点的度赋值为 ${{\boldsymbol{d}}_G}({v_1})$ , 然后考虑两个匿名代价 $ {C_{{\text{merge}}}} $ 和 $ {C_{{\text{new}}}} $ , 计算公式如下:

$ {C_{{\text{merge}}}} = ({{\boldsymbol{d}}_G}({v_1}) - {{\boldsymbol{d}}_G}({v_{k + \, 1}})) + Cost({{\boldsymbol{d}}_G}[{v_{k + \, 2}}, {v_{2k + \, 1}}]) $

(1)

$ {C_{{\text{new}}}} = Cost({{\boldsymbol{d}}_G}[{v_{k + \, 1}}, {v_{2k}}]) $

(2)

当 $ {C_{{\text{merge}}}} > {C_{{\text{new}}}} $ 时, 把第 $k + 1$ 个节点至第 $2k$ 个节点合并成一个新组, 组内所有节点度为 ${\boldsymbol{d}}({v_{k + 1}})$ ; 否则将第 $k + 1$ 个节点合并到前一个组中, 并将第 $k + 2$ 个节点视为合并或作为新组的起点, 算法在遍历所有节点后停止. 其中 $ Cost({{\boldsymbol{d}}_G}[{v_i}, {v_j}]) $ 表示第 $i$ 至 $j$ 个节点划分到同个匿名组的匿名代价, 计算公式如下:

$ Cost({{\boldsymbol{d}}_G}[{v_i}, {v_j}]) = \sum\nolimits_{l = i}^j {({{\boldsymbol{d}}_G}({v_i}) - {{\boldsymbol{d}}_G}({v_l}))} $

(3)

通过该算法得到匿名度序列, 每个组中至少有 $k$ 个度相同的节点, 满足k匿名性原则.

3.2 加边算法

加边算法包括两个阶段: 优先加边和普通加边. 优先加边阶段尽量满足匿名代价大于平均匿名代价的节点的匿名要求, 按照匿名代价降序遍历节点, 基于层次社区结构选择目标节点进行连边, 每次加边操作更新匿名代价序列. 在加边操作中, 从当前节点所在的社区开始遍历, 考虑两类节点: 1)节点度比当前节点度小; 2)节点度比当前节点度大且匿名代价大于0. 将符合条件的节点标识为目标节点, 并优先选择与当前节点距离近的目标节点进行连边. 若标记的目标节点数仍不能满足当前节点的匿名要求, 则向高级别社区遍历, 找到足够多的目标节点进行连边.

算法 1. 优先加边算法 $\;\scriptstyle ({\text{pre\_edges\_addition}})$

输入: 图 $\scriptstyle G$ , 匿名代价序列 $\scriptstyle {{\boldsymbol{d}}_{{\text{Cost}}}}$ , 层次社区L

输出: 图G'

1. initialize $\scriptstyle T = \emptyset $ //目标节点集合

2. FOR $\scriptstyle vertex\;v$ in $\scriptstyle \{ v|{{\boldsymbol{d}}_{{\text{Cost}}}}(v) > avg\_cost\, , v \in V\} $ DO

3.　 $\scriptstyle C \leftarrow {\text{find\_community}}(L, v)$

4.　FOR $\scriptstyle community\;c \in C$ DO

5.　　 $\scriptstyle {\rm{FOR}}\; node\;n \in V\;{\rm{DO}}$ //选择目标节点

6.　　　IF $\scriptstyle n \in c \wedge n \notin T\; \wedge \;n \ne v\; \wedge \;(n, v) \notin E$ THEN

7.　　　　IF $\scriptstyle {{\boldsymbol{d}}_G}(n) < {{\boldsymbol{d}}_G}(v)$ THEN

8.　　　　　 $\scriptstyle T \leftarrow T \cup \{ n\} $

9.　　　　ELSE IF $\scriptstyle {{\boldsymbol{d}}_G}(n) > {{\boldsymbol{d}}_G}(v) \wedge {{\boldsymbol{d}}_{{\text{Cost}}}}(n) > 0$ THEN

10.　　　　　 $\scriptstyle T \leftarrow T \cup \{ n\} $

11.　　　　END IF

12.　　　END IF

13.　　END FOR

14.　　IF $\scriptstyle |T|\; \geqslant {{\boldsymbol{d}}_{{\text{Cost}}}}(v)$ THEN

15.　　　BREAK//目标节点数满足当前节点匿名要求

16.　　END IF

17.　END FOR

18.　sort $\scriptstyle T$ according to the shortest $\scriptstyle {path}\; ({T_i}, v), i \in (0, \, \, |T|)$ in the ascending order//若节点不可达, 则距离为 $\scriptstyle \infty $

19.　WHILE $\scriptstyle {{\boldsymbol{d}}_{{\text{Cost}}}}(v) > 0\; \wedge \;|T| > 0$ DO//加边操作

20.　　 $\scriptstyle E \cup \{ ({T_i}, v)\} , i \in (0, \, \, |T|)$

21.　　 $\scriptstyle T \leftarrow T\backslash {T_i}$

22.　　 $\scriptstyle {{\boldsymbol{d}}_{{\text{Cost}}}}(v) \leftarrow {{\boldsymbol{d}}_{{\text{Cost}}}}(v) - 1$

23.　END WHILE

24. END FOR

25. RETURN $\scriptstyle G'$

再次通过贪心匿名分组得到匿名度序列, 普通加边阶段根据该序列尽量满足所有节点的匿名要求. 采用与优先加边阶段同样的加边操作, 仅考虑匿名代价大于0的节点, 并优先选择与当前节点距离近的目标节点进行连边.

算法 2. 普通加边算法 $\scriptstyle ({\text{edges}}\_{\text{addition}}) $

输入: 图 $\scriptstyle G'$ , 匿名代价序列 $\scriptstyle {{\boldsymbol{d}}_{{\text{Cost}}}}$ , 层次社区 $\scriptstyle L$

输出: 图G'', 匿名代价序列 $\scriptstyle\;{\boldsymbol{d}}_{{\text{Cost}}}^\prime$

1. initialize $\scriptstyle T = \emptyset $ //目标节点集合

2. FOR $\scriptstyle vertex\;v$ in $\scriptstyle \{ v|{{\boldsymbol{d}}_{{\text{Cost}}}}(v) > 0, v \in V\} $ DO

3.　 $\scriptstyle C \leftarrow {\text{find\_community}}(L, v)$

4.　FOR $\scriptstyle community\;c \in C$ DO

5.　　FOR $\scriptstyle node\;n $ in $\scriptstyle \{ n|\;{{\boldsymbol{d}}_{{\text{Cost}}}}(n) > 0, n \in V\} $ DO

6.　　　IF $\scriptstyle n \in c \wedge n \notin T\; \wedge \;n \ne v\; \wedge (n, v) \notin E $ THEN

7.　　　　 $\scriptstyle T \leftarrow T \cup \{ n\} $

8.　　　END IF

9.　　END FOR

10.　　 $\scriptstyle \cdots $ //省略部分参考算法1

11. END FOR

12. RETURN $\scriptstyle G'' , {\boldsymbol{d}}_{{\text{Cost}}}^\prime$

3.3 层次社区发现算法

在层次化社区树中, 社区级别越高则社区规模越大, 整个图为最高级别的社区, 如图1所示. 采用Louvain算法^[16]获得层次化社区结构, 这是一种基于模块度优化^[17]的启发式算法. 第1步, 每个节点都属于一个独立的社区, 通过社区之间的节点移动, 使得社区划分的模块度最大化; 第2步, 根据当前划分的每个社区聚合成单个节点, 节点之间的边权重为其代表的两个社区之间的边权重之和; 重复这两个步骤, 直到模块度大小不再变化. igraph软件包^[18]提供了该算法的实现函数community_multilevel. 当传入参数 $ return\_levels $ 为True, 返回包含每层社区结构的节点集合 $L = \{ \{ L_{_1}^2, \cdots, L_{{n_2}}^2\} , \cdots, \{ L_{_1}^l, \cdots, $ $ L_{{n_l}}^l\} \} $ ; 否则返回模块度最优的社区结构 $\{ L_{_1}^2, \cdots, L_{{n_2}}^2\} $ .

算法 3. 层次社区发现算法 $ \scriptstyle {\text{(find\_community)}} $

输入: 层次社区 $ \scriptstyle L $ , 当前节点 $\scriptstyle v$

输出: 包含 $\scriptstyle v$ 的层次社区 $\scriptstyle C$

1. initialize $\scriptstyle C = \emptyset $

2. FOR $ \scriptstyle hierarchy\_community\;hc \in L $ DO

3.　FOR $ \scriptstyle community\;c \in hc $ DO

4.　IF $\scriptstyle v \in c $ THEN

5.　　 $ \scriptstyle C \cup \{ c\} $

6.　　BREAK

7.　END IF

8.　END FOR

9. END FOR

10.　 $\scriptstyle C \cup \{ V\} $ //添加最高级别社区

11. RETURN $\scriptstyle C$

3.4 图匿名化算法

图匿名化算法整合如下算法: 匿名分组算法、层次社区发现算法、加边算法和加点算法, 原图经过加边和加点操作生成满足k度匿名化的图.

算法 4.图匿名化算法 $ \scriptstyle ({\text{graph}}\_{\text{anonymization}}) $

输入: 图 $\scriptstyle G(V, E) $ , 参数 $\scriptstyle k$

输出: 匿名图 $\scriptstyle G'''$

1. $\scriptstyle L \leftarrow G.{\text{community\_multilevel}}(return\_level \leftarrow T) $

2. $\scriptstyle {{\boldsymbol{d}}_{{\text{Cost}}}} \leftarrow {\text{anonymize\_partition}}(G, k)$

3. $\scriptstyle G' \leftarrow {\text{pre\_edges\_addition}}(G, {{\boldsymbol{d}}_{{\text{Cost}}}}, L)$

4. $\scriptstyle {{\boldsymbol{d}}_{{\text{Cost}}}} \leftarrow {\text{anonymize\_partition}}(G' , k)$

5. $\scriptstyle G'' , {\boldsymbol{d}}_{{\text{Cost}}}^\prime \leftarrow {\text{edges\_addition}}(G', {{\boldsymbol{d}}_{{\text{Cost}}}}, L)$

6.　IF $\scriptstyle \{ v|\;{{\boldsymbol{d'}}_{{\text{Cost}}}}(v) > 0, v \in V\} \ne \emptyset$ THEN//是否加点

7.　　 $\scriptstyle G''' \leftarrow {\text{nodes\_addition}}(G'' , {\boldsymbol{d}}_{{\text{Cost}}}^\prime , k)$

8.　END IF

9.　 $\scriptstyle G''' \leftarrow G''$

10. RETURN $\scriptstyle G'''$

对于一些特殊情况, 新算法仅通过加边无法满足节点匿名化要求. 所以, 通过Chester等人^{[11, 12]}提出的加点算法, 将原图中未匿名的节点依次与新节点相连来满足节点的匿名化要求; 同时, 新节点也需要进行匿名化处理, 并最终实现图的匿名化. 新节点个数 $m$ 满足如下关系, $mc$ 表示节点的最大匿名代价.

$ m = (1 + \max (mc, k)\boldsymbolod 2) + \max (mc, k) $

(4)

3.5 算法复杂性分析

Liu等人^[9]提出的贪心匿名分组算法的时间复杂度为 ${\rm{O}}(nk)$ . 由匿名分组算法确定的未匿名节点个数不会超过 $ (n - {n \mathord{\left/ {\vphantom {n k}} \right. } k}) $ , ${n \mathord{\left/ {\vphantom {n k}} \right. } k}$ 表示匿名分组数. 优先加边算法的时间复杂度为 ${\rm{O}}(lmn)$ , $l$ 表示层次化社区树的高度, $m$ 表示匿名代价大于平均匿名代价的节点个数; 当节点匿名代价很大时, 可能需要遍历全图寻找目标节点. 普通加边算法的时间复杂度为 ${\rm{O}}((n - {n \mathord{\left/ {\vphantom {n k}} \right. } k}) \times l \times mc)$ , 虽然此阶段需要匿名处理的节点数较多, 但是节点最大匿名代价 $mc$ 较小, $mc \ll n$ . Louvain算法^[16]的时间复杂度是线性阶的, 层次社区发现算法的时间复杂度也是线性阶的. 通过Floyed算法^[19]计算所有节点的路径长度, 将其输出作为算法输入, 该时间复杂度为 ${\rm{O}}({n^3})$ . 因此, 新算法的时间复杂度为 ${\rm{O}}({n^2})$ .

4 实验结果与分析

实验环境为Windows 10专业版, 运行环境采用PyCharm 2020 (Python语言), PC机主频3.6 GHz, 内存8 GB. 新算法命名为KDVEM21, 在5个真实数据集上进行实验, 同5个经典算法比较, 对比算法仅包含加边或加点的多项式时间复杂度算法: 包括Priority算法^[9]、FKDA算法^[10]、V_ADD算法^{[11, 12]}、KDVEM15算法^[13]和KDVEM18算法^[14], 分别从匿名效果和匿名代价两个方面评估算法的性能, 并对实验结果进行分析.

4.1 数据集描述

本文实验数据采用斯坦福大学提供的公开数据集(SNAP), 表1给出了数据集的详细介绍, 实验数据集都是无向的、简单的、无标记的.

4.2 评价方法

徐恪等人^[20]概述了典型的社交网络拓扑参数, Ji等人^[21]讨论了图数据匿名化的研究演变和匿名度量的有效性, Zhao等人^[22]指出组合多个度量指标作为隐私度量更具可比性, 赵蕙等人^[23]认为社交网络匿名化度量方法的多样和复杂, 匿名算法研究者难以找到合适的方法评估自己的创新研究. 因此, 实验采用典型的3个图的结构特性作为匿名效果的度量指标.

(1) 平均路径长度(average path length)

平均路径长度计算公式如下, ${\textit{SPL}}$ 是节点 $u$ 和 $v$ 之间的最短距离, $CP$ 表示所有可连接的节点对.

$ \overline P = \frac{{\displaystyle\sum\limits_{\left( {u, v} \right) \in CP} {{\textit{SPL}}(u, v)} }}{{|CP|}} $

(5)

(2) 传递系数(transitivity)

传递系数, 也称为全局聚类系数, 计算公式如下, $\Delta $ 表示闭合三联体数目, $ \wedge $ 表示三联体数目.

$ T = \frac{\Delta }{ \wedge } $

(6)

(3) 平均聚类系数(average clustering coeffiient)

在社交网络中, 聚类系数的体现是一个人的两个好友彼此也是好友的概率, 计算公式如下:

$ {C_i} = \frac{{2|{E_{xy}}|}}{{{d_i}({d_i} - 1)}}, {0 \leqslant {C_i} \leqslant 1} $

(7)

其中, ${E_{xy}}$ 表示节点 $i$ 的相邻节点 $x$ 和 $y$ 之间的边数, ${d_i}$ 表示节点 $i$ 的度, $n$ 为节点数. 平均聚类系数是所有节点的聚类系数的平均值, 计算公式如下:

$ \overline C = \frac{1}{n}\sum\limits_{i = 1}^n {{C_i}} , {0 \leqslant \overline C \leqslant 1} $

(8)

4.3 结果分析

实验参数 $k$ 的取值范围{5, 10, 15, 20, 25, 50}, 在复现Priority算法时, 构图操作中采用了随机选点的策略, 因而在每个参数上运算10次取平均值作为实验结果. V_ADD算法和KDVEM15算法由作者提供源代码. 将实验结果绘制成点线图, 其中, 横轴表示参数 $k$ , 纵轴表示度量指标的取值范围. 水平线表示原图的度量指标, 其余分别表示对比算法在对应参数下输出匿名图结构特性的度量指标. 图2–图6分别表示各个真实数据集在对应参数k生成匿名图的结构特性.

为了直观地对比算法性能, 采用平均变化量的百分比形式作为实验结果, 如表2所示, 数值越小说明匿名图与原图的结构特性差异越小. 计算公式如式(9), 其中, $m$ 表示图的结构特性的度量指标.

$ R = \frac{1}{{\left| k \right|}}\sum\limits_{i \in k} {{{\left| {\frac{{\vartriangle m}}{{{m_0}}}} \right|}_i}} \times 100 $

(9)

Rajabzadeh等人^[15]认为3个度量指标具有同等的重要性, 取3个度量指标的平均值作为算法的综合评价. 随着参数 $k$ 的增大, 需要添加的边就越多, 若将相近节点相连, 则路径长度会变小; 简单的加边使得原图的社区结构变得交错, 从而传递系数和平均聚类系数变化较大, 而基于原图社区结构加边, 一定程度保留了社区结构, 使得传递系数和平均聚类系数变化较小. KDVEM21算法基于层次化社区结构, 优先与距离近的目标节点连边, 使得平均路径长度的变化较小, 从表2可以看出, KDVEM21算法在平均路径长度的相对变化较小; 正是考虑社区结构的原因, 传递系数和平均聚类系数的变化较小, 在ca-GrQc、ca-HepTh、ca-HepPh和ca-AstroPh数据集上的综合评价最好. 但对于节点较多且最大度较大的数据集, 采用优先加边的操作时, 可能需要遍历高级别社区, 这一定程度上破坏了小规模社区的结构, 加剧了传递系数的变化.

Zhang等人^[24]通过对比添加边和节点来评估算法的匿名代价, 如表3、表4所示. KDVEM21算法采用两阶段加边操作, 充分利用原图的节点进行加边, 减少了添加的节点. 对比加边且可加点类算法, KDVEM21算法添加的边或节点更少.

5 总结与展望

社交网络匿名化是复杂网络领域中一个重要的研究方向. 解决社交网络匿名化问题需要平衡用户隐私保护和图数据实用性二者的关系. 本文利用经典算法的优势提出了改进算法, KDVEM21算法采用加边且可加点的匿名化策略, 分两个阶段进行加边, 并结合节点特性和社区结构对加边操作进行了优化. 在5个真实网络上测试KDVEM21算法的有效性, 实验结果表明, 对比5个经典算法, 大多数情况下, KDVEM21算法能更好地保留图的几种典型的结构特性(平均路径长度、平均聚类系数和传递系数), 并且对比加边且可加点类算法, 添加边或节点更少; 但新算法的时间复杂度并不具备优势. 未来工作: 对算法时间复杂度进行优化; 探索算法在其它图结构特性度量下的匿名效果; 减少图匿名化的代价.