随着计算机领域的软硬件技术不断发展, 社交网络逐渐地成为了线上产物.脸谱、推特、腾讯等公司都维护着庞大的社交网络图, 并且这些图还在不断扩张.在这些社交网络图中, 用户被表示为带有标签(例如姓名、性别、兴趣、地址等)的结点, 而用户之间的交互活动可以被抽象为点之间的边(有向边或者无向边, 具体根据交互活动的性质而定), 通过这样的方式, 社交网络就被表示为了带有必要的用户关系信息的图.

由于社交网络自身的真实性、规模性以及边的分布特点, 吸引了很多的学术研究者和广告商的研究兴趣.然而, 在公司、组织不断开放更多的信息过程中, 用户的隐私很可能被迫揭露出来, 导致用户身份泄漏.而随着社交网络图中结点的真实身份被揭露, 会造成许多后果, 例如接收到无穷无尽的垃圾广告信息, 甚至因此错信他人而被诈骗.因此, 发布的社交网络数据需要经过一定的匿名化处理, 其中最简单的方法就是打乱图中点的标号.Backstrom等人^[1]提出了一种方法, 利用少量手动创建的用户, 建立一种特殊的模式, 然后在发布的图中寻找该模式, 就可以在发布的图中找到目标用户的对应身份.Wang等人^[2]提出了一种防止指纹攻击的匿名化方法, 既能有效地阻碍从已知的公众人物入手的隐私攻击, 又能较好地保持图的结构性质.

为了保护用户隐私, 找到有效的匿名化方法, 需要对匿名化方法的质量(破解的难易程度)进行评估, 而这样的评估依赖于对去匿名化方法的探索.去匿名化, 顾名思义就是匿名化的反过程, 通过一些拓扑结构信息、标签信息对匿名化之后的图进行处理, 找到各个点的原始身份信息.例如, 在图 1中, 左边的网络是通过爬虫获得的, 带有用户的公开信息(姓名); 而右边的图是发布的, 不带有用户的身份信息(姓名), 但是有一些其他的信息(地址).去匿名化的过程可以理解为:匹配这两张图中的点, 从而知道每一个人实际的地址.

近年来, 针对去匿名化问题, 研究者们相继提出了多种方法, 根据需要提供的输入和利用的信息, 主要可以将它们归为两类方法.

●  第1类方法是扩散性质的, 需要一些已知身份信息的匹配点对, 作为种子对, 从它们出发不断扩展到其他的结点.由于已经有了扩散的中心, 在初始中心正确的情况下, 比较容易得到一些高质量的匹配对.但是这类方法的缺陷在于:往往对种子对的可靠性非常依赖, 而该可靠性在实际操作中往往并不能保证, 因此造成了相当的匹配错误率;

●  第2类方法不需要种子对, 将各种结点对放在一个相对平等的初始地位上, 然后通过对图结构的分析匹配并获得身份结果.这类方法主要利用的是结点的结构特征信息(例如度数、子图、结点相似度、描述性信息等), 这些特征信息如果利用得好, 可以得到高质量的匹配对.而由于信息多而杂, 表示方法多样, 不方便进行统一度量, 度量之后也难以很好地加以利用, 这类方法主要的困难在于对特征的提取以及利用, 这也是笔者在设计算法的时候主要考虑的内容.

本文提出了一种不需要种子的去匿名化方法RoleMatch, 它属于上述第2类方法, 不需要初始的正确种子对, 只基于图的结构信息.具体来说, 只是利用图的拓扑结构信息, 将每个可能点对的匹配程度用一个数值进行抽象, 从而完成了从复杂多维空间到简单一维空间的有效映射, 便于进行比较判断, 解决了图结构信息多而杂的问题.在此基础上, 该方法对此映射进行有针对性的匹配应用, 获得高质量的匹配结果.

此外, 现有的研究中讨论的去匿名化算法都是针对全局、基于两个大小和结构都相近的图进行的.在另一种情况下, 攻击者关注的是一部分用户的个人信息, 这种情形可以称为局部去匿名化.例如从真实网络中爬取一个子图, 与经过匿名化的完整网络进行匹配.相对于全局的去匿名化, 局部去匿名化中可能与一个结点匹配的候选结点数增加到了多个, 因此具有更高的难度.并且, 针对局部去匿名化的研究相对更少.本文介绍的算法对局部去匿名化也具有较好的效果.

在利用常见的匿名化方法(例如, 朴素匿名化方法、交换匿名化方法、稀疏化匿名化方法等)处理的图上, 本文提出的方法取得了很好的匹配结果.该方法主要可以分为两个阶段:(1)结点相似度计算阶段; (2)结点匹配阶段.在第1个阶段, 笔者根据两张图中结点的结构信息, 采用RoleSim++计算结点对的相似度.在第2个阶段, 匹配两张图中的点, 从而获取点的身份信息.本文的主要贡献是:

●  提出一种基于图结构信息的结点相似度计算方法RoleSim++, 它自带归一化并对大度数和小度数的点都适用(第2.1节);

●  提出一种基于结点相似度的结点匹配算法, 同时考虑了结点的相似程度和匹配过程中的反馈(第2.2节);

●  在传统去匿名化实验方法的基础上, 增加了更贴合实际应用情景的局部去匿名化, 并取得较好的效果(第3.2.3节);

●  利用这些提出的方法, 在真实的社交网络数据集上评估了几种不同的匿名化算法的隐私泄漏风险(第3节).

本文第1节论述现存的相关研究.第2节提出去匿名化算法RoleMatch, 具体包括结点RoleSim++相似度计算和结点匹配.第3节在Live Journal数据集上, 通过模拟实验验证算法的有效性和高效性.最后, 阐述研究结论.

1 相关工作 1.1 匿名化算法

根据对社交网络匿名化的一项研究^[3], 匿名化算法可以分为3类:(1) K-匿名算法; (2)边随机匿名化算法; 和(3)基于聚类的泛化匿名化算法.

K-匿名方法^{[4, 5]}通过边的加减来修改图结构, 使得图中的每一个点至少与K-1个其他的点在一定的结构特征上不可区分, 例如拥有相同的度数, 或拥有相同的邻居结构.该方法在匿名化结果上有较好的表现, 但是一方面, 最优化的K-匿名方法实现相对复杂; 另一方面, 对图结构的改变程度比较大, 可能对图结构的研究有一定的影响.边随机方法通过随机添加边、删除边、交换边来修改图结构^[6], 它在一定概率上保证了隐私安全.基于聚类的泛化方法^[7]首先将结点聚类, 然后把每一个子图匿名为一个不带有个体结点具体信息的超点.这样的方法在防止身份识别方面有较好的效果, 但是损失了很多个体信息, 也损失了规模信息, 从而对社交网络分析可能有一定的妨害.

1.2 去匿名化算法

去匿名化算法主要分为两类:一类是需要初始种子对进行扩散的方法; 一类是不需要种子对, 仅利用图特征信息进行提取判断的算法.各个去匿名化算法之间差别多样, 这也是图结构信息表示的多样性带来的特点.

Backstorm等人^[1]提出了一种连续的攻击方式, 以此来获知特定的两个点之间有没有边存在.缺陷在于, 尽管该算法对仅仅交换结点编号的朴素匿名化算法效果较好, 但对那些会修改图结构的匿名化算法, 该攻击方式无能为力.

Narayanan等人^[8]呈现了一种分析隐私的框架, 并提出了一种去匿名化算法, 只基于网络拓扑结构, 并对噪音和大多数防御有较好的健壮性.它需要一些已知的种子匹配对, 然后逐渐扩散到全图.然而, 根据作者论文中的描述, 种子对的质量对去匿名化是否成功至关重要.Narayanan^[9]还提出了一种基于模拟退火的边匹配算法, 替代去匿名化算法中种子对的效果.而本文考虑的算法不需要基于高质量的匹配种子对.

Yartseva等人^[10]根据图的渗流理论(graph percolation)提出了基于种子的图匹配方法.Kazemi等人^[11]在Yartseva等人的基础上又放宽了对种子的要求, 降低了所需种子的数量.Korula等人^[12]将图的渗流理论应用到了幂律分布的图上, 对真实的社交网络匹配有更好的效果.

Fu等人^[13]提出了不需要种子对的社交网络去匿名化算法, 该算法首先用公式计算每对结点的相似度, 然后根据结点对的相似度由高到低贪心匹配.本文采用与其类似的基本思路, 通过计算相似度以匹配结点, 提出了更合理的计算公式, 达到了更好的匹配精度.

1.3 结点相似度计算方法

去匿名化算法中, 结点相似度度量的质量至关重要, 因为它是后续匹配情况的最重要依据, 表征了结点具有相同身份的可能性.结点相似度的度量, 常常是结点本身信息和子图信息的综合考虑, 不同的考虑权重, 不同的综合方法, 导致了不同的度量方法.

Henderson等人^[14]提出了一个相似度度量, 递归地将局部特征和邻居特征结合起来产生区域特征, 然后用这些区域特征去匿名化.这样的区域特征可以有效缩小可能的对应点范围, 但是并无法证明这样可以找到最相似的点(点的真实身份).

著名的Simrank方法^[15]提供了一张图内结点相似度的度量方法, 这在去匿名化问题中无法直接应用. Blondel等人^[16]在此基础上提出了一个多图的结点相似度度量, 将两个结点邻居的相似度求和得到相似度. HaoFu等人^[13]提出了两张图的结点相似度度量, 迭代计算, 对两个点匹配它们的邻居最大化匹配的相似度和.这样的方法对Simrank的简单移植是一种有效的改进, 对度数大的结点能产生不错的度量结果.但是由于缺乏归一化, 尺度不统一, 该方法对小度数的结点计算得到的相似度, 往往太小以至于失去意义.Jing等人^[17]提出了一种一张图内带归一化的结点相似度度量方案RoleSim, 它对点的结构信息有比较好的刻画, 但是定义和计算方法限制在了单图上.本文提出的度量方法可以用于去匿名化匹配, 并不带有上述问题.

还有一些研究者希望用机器学习的方法计算结点相似度.Pozzi等人^[18]提出了深度学习算法, 通过截取随机游走路径, 将该路径视作句子来学习结点的潜在向量表示.Tang等人^[19]提出了大规模信息网络嵌入方法, 用低维向量表示大规模图中的结点.

2 基于社交网络图结构的去匿名化算法RoleMatch

基于社交网络图结构的去匿名化算法RoleMatch与现有算法相比匹配结果效果更好, 计算方法速度更快.

2.1 结点相似度

去匿名化算法的第1个阶段是提供一个结点相似度度量, 衡量每一个可能的结点对的相似程度.在这一部分, 我们设计了一种新的结点相似度度量, 它与现有方法相比有更好的度量效果(精确度); 并且有极为高效的计算方法.

2.1.1 两图结点RoleSim++相似度

文献[5]提出了一种对两图结点相似度的度量方法, 基于Simrank^[7]一样的直觉, 认为邻居相似的点对本身也相似.分别用N₁(u), N₂(v)表示u, v两个来自不同图的点的邻居, 该方法对N₁(u)和N₂(v)中相似的点匹配, 最大化匹配点对的相似度和.结点相似度S(u, v)的值通过如下方程组定义:

$ S(u, v) = \mathop {\max }\limits_{M是集合{N_1}(u)元素和{N_2}(v)元素的匹配}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\sum\limits_{(x, y) \in M} {S(x, y)} . $

但是这个相似度计算缺少了归一化, 效果严重依赖结点度数大小, 导致不同的结点对, 它们的S(u, v)尺度相差很大, 整个相似度矩阵也就无法达到衡量相似度的作用.

尽管如此, 结点相似度仍然是去匿名化中非常重要的衡量指标, 通过对相似度定义的改进, 本文设计了结点相似度算法RoleSim++.

定义.给定两张图G₁=(V₁, E₁), G₂=(V₂, E₂), 给定两个结点u∈V₁和v∈V₂, 用$ N_1^ + (u), N_1^ - (u)$和$ N_2^ + (v), N_2^ - (v)$分别表示它们的邻居(“+”表示出边连接的邻居, “”表示入边连接的邻居), 用$|N_1^ + (u)|, |N_1^ - (u)|, |N_2^ + (v)|, |N_2^ - (v)| $分别

表示对应的度数.定义两点的出度较大值、入度较大值为

$ \begin{array}{l} {\mathit{\Delta} ^ + }(u, v) = \max \{ |N_1^ + (u)|, |N_2^ + (v)|\}, \\ {\mathit{\Delta} ^ - }(u, v) = \max \{ |N_1^ - (u)|, |N_2^ - (v)|\}, \end{array} $

以及匹配权和(即邻居点对相似度的最大匹配):

$ \begin{array}{l} {\mathit{\Gamma} ^ + }(u, v) = \mathop {\max }\limits_{{M^ + }(u, v)} \sum\limits_{(x, y) \in {M^ + }(u, v)} {Sim(x, y)}, \\ {\mathit{\Gamma} ^ - }(u, v) = \mathop {\max }\limits_{{M^ - }(u, v)} \sum\limits_{(x, y) \in {M^ - }(u, v)} {Sim(x, y)}, \end{array} $

其中, M⁺(u, v)是对$N_1^ + (u) $和$N_2^ + (v) $的一个匹配, 类似定义M^-(u, v).对Γ⁺(u, v)和Γ^-(u, v)的计算可以视作一个最优化的子过程.在此基础上, 定义结点RoleSim++相似度为$ Sim(u, v) = (1 - \beta )\frac{{{\mathit{\Gamma} ^ + }(u, v) + {\mathit{\Gamma} ^ - }(u, v)}}{{{\mathit{\Delta} ^ + }(u, v) + {\mathit{\Delta} ^ - }(u, v)}} + \beta $.其中, 参数β是一个衰减因子, 有界0 < β < 1.

为了将更多的结构信息考虑进去, Sim(u, v)分别计算两个方向的边(入边和出边), 并且用它们的和作为相似度值.这样的相似度度量, 符合相似的点有相似的邻居这一基本直觉, 并且自带归一化, 对度数无论大小的点都有较好的度量.

在该度量中, 可以看到一些与去匿名化相关的事实:(1)如果两张图形态是完全一样的, 那么一个点肯定与另一张图中的对应点最相似(Sim值为1);(2)该算法在计算的时候, 不会忽略度数小的点, 并且有一个比较合适的尺度.

在该定义的基础上, 可以证明迭代计算的单调性, 并在证明了单调性后, 结合Sim^k(u, v)≥β, 立即得到收敛性.

接下来证明该相似度度量在迭代计算中的相关收敛性质.

引理1(单调性).用Sim^k(u, v)和Sim^k+1(u, v)表示点对(u, v)在第k轮之后的相似度值, 那么对任意的k和(u, v), 有Sim^k(u, v)≥Sim^k+1(u, v).

证明:按照迭代轮数归纳.注意到Sim⁰(u, v)=1, 那么:

$ Si{m^1}(u, v) = (1 - \beta )\frac{{\min \{ |N_1^ + (u)|, |N_2^ + (v)|\} + \min \{ |N_1^ - (u)|, |N_2^ - (v)|\} }}{{\max \{ |N_1^ + (u)|, |N_2^ + (v)|\} + \max \{ |N_1^ - (u)|, |N_2^ - (v)|\} }} + \beta . $

因此, Sim¹(u, v)≤1.

在第k+1轮, (u, v)的邻居对的相似度值不会比第k轮有所增加, 那它们之间的匹配权和也不会增加.因此对任意(u, v)、任意k, 有Sim^k(u, v)≥Sim^k+1(u, v).

在单调性的基础上, 结合Sim^k(u, v)≥β, 容易证明收敛性.

命题1(收敛性). 上文定义的相似度, 对任意(u, v)收敛, 即 $\mathop {\lim }\limits_{k \to \infty } Si{m^k}(u,v) = Sim(u,v).$

下面的命题表明了β对迭代收敛速度的影响.Sim^k(u, v)与Sim(u, v)之间的差距以指数的速度减小.

命题2.对任意点对(u, v), 用ε^k(u, v)表示Sim^k(u, v)-Sim(u, v), 那么有ε^k(u, v)≤(1-β)^k+1.

证明:从引理1可知Sim^k(u, v)-Sim(u, v)≥0, 接下来, 按照迭代轮数归纳证明命题.

由定义得知Sim(u, v)≥β, 因此Sim⁰(u, v)-Sim(u, v)≤(1-β)⁰⁺¹=1-β.

在第k轮迭代之后, 有:

$ \begin{array}{l} {\varepsilon ^k}(u, v) = Si{m^k}(u, v) - Sim(u, v)\\ {\rm{ }} = (1 - \beta )(\mathit{\Gamma} _k^ + (u, v) + \mathit{\Gamma} _k^ - (u, v) - \mathit{\Gamma} _{k + 1}^ + (u, v) + \mathit{\Gamma} _{k + 1}^ - (u, v))/({\mathit{\Delta} ^ + }(u, v) + {\mathit{\Delta} ^ - }(u, v))\\ {\rm{ }} \le (1 - \beta )(\min \{ |N_1^ + (u)|, |N_2^ + (v)|\} + \min \{ |N_1^ - (u)|, |N_2^ - (v)|\} ){(1 - \beta )^k}/({\mathit{\Delta} ^ + }(u, v) + {\mathit{\Delta} ^ - }(u, v))\\ {\rm{ }} \le (1 - \beta ){(1 - \beta )^k}\\ {\rm{ }} = (1 - \beta ){(1 - \beta )^{k + 1}}. \end{array} $

因此有ε^k(u, v)≤(1-β)^k+1.

注意到:如果令β=0.15, 迭代轮数为5, 根据命题2, 相似度的理论值和迭代值相差不超过0.85⁵=0.44, 这仍然不是一个非常小的值.但是在实际计算中, 增加迭代轮数对结果的精度几乎没有影响, 笔者会在后面的实验部分继续讨论这个问题.

2.1.2 结点相似度计算

基于上面讨论的性质, 采用迭代的方式计算Sim矩阵, 伪代码见算法1.在每一轮(第3行~第9行), 枚举所有的结点对(第4行), 根据之前的定义计算它们的相似度(第5行、第6行), 在每一轮之后更新矩阵值(第8行).迭代若干轮以后得到结果.

算法1.迭代更新相似度矩阵.

$ \begin{array}{l} {\rm{Input}}:{G_1} = ({V_1}, {E_1}), {G_2} = ({V_1}, {E_1});\\ {\rm{Output}}:Sim.\\ 1\mathit{\boldsymbol{ }}Sim \leftarrow MatrixAllOne;\\ 2\mathit{\boldsymbol{ }}{\bf{for}}\;\mathit{ }\underline {i = 1 \to nRounds}{\rm{ }}\;{\bf{do}}\\ 3\;\;\;\;{\rm{ }}{\bf{for}}\;\mathit{ }\underline {\langle u, v\rangle \in {V_1} \times {V_2}} \mathit{ }\;{\bf{do}}\\ 4\mathit{\boldsymbol{ }}\;\;\;\;\;\;\;\mathit{\boldsymbol{ }}r \leftarrow \frac{{\gamma (N_1^ + (u), N_2^ + (v)) + \gamma (N_1^ - (u), N_2^ - (v))}}{{{\mathit{\Delta} ^ + }(u, v) + {\mathit{\Delta} ^ - }(u, v)}};\\ 5\mathit{\boldsymbol{ }}\;\;\;\;\;\;\;\;Sim'(u, v) \leftarrow (1 - \beta ) \cdot r + \beta ;\\ 6\mathit{\boldsymbol{ }}\;\;\;\;\mathit{\boldsymbol{ }}{\bf{end}}\\ 7\mathit{\boldsymbol{ }}\;\;\;\;\mathit{\boldsymbol{ }}Sim \leftarrow Sim';\\ 8\mathit{\boldsymbol{ }}{\bf{end}}\\ 9\mathit{\boldsymbol{ }}{\bf{return}}\;\;\mathit{ }Sim \end{array} $

伪代码中的函数γ(N_u, N_v)是选择实现算法描述中匹配子过程的方式(也就是Γ⁺和Γ^-的实现).在这个子过程中, 首先用N_u和N_v中的点建立二分图, 边权为上一轮计算中的相似度.然后, Γ函数用一个最大匹配作为这个子过程的结果.与之对应的, 实际计算中采用的方法是:依边权降序排列这些边, 然后依次贪心选择, 优先选择权值大的边.本文的选择是对原最优化问题的一种高效近似, 降低了计算复杂度.

以图 1为例, 考虑其中的点u₁, 取β=0.15, 在第1轮迭代中, 就有:

$ Sim({u_1}, {v_1}) = (1 - \beta )\frac{{0 + 2}}{{0 + 3}} + \beta = 0.72, Sim({u_1}, {v_1}) = (1 - \beta )\frac{{0 + 1}}{{2 + 3}} + \beta = 0.32. $

类似得到Sim(u₁, v₃)=0.32, Sim(u₁, v₄)=0.1, Sim(u₁, v₅)=0.43.显而易见:尽管第1轮迭代只使用了相邻结点的信息, 点u₁与v₁的相似度显著高于与其他点的相似度.经过5轮迭代之后, 点对之间的相似度情况见表 1.

在实际计算中, 迭代在几轮之内就能收敛.实际上, 在实验中, 5轮以内的结果就已经足够令人满意了.

2.1.3 加速相似度计算

前面介绍了本文提出的结点相似度度量方法以及一个能在几轮内有效收敛的迭代计算方法.然而, 考虑到每轮的计算复杂度都有至少Ω(|V₁||V₂|d²), 其中, d是平均度数.这样的复杂度仍然是一个不小的负担, 尤其是当面对大规模图网络的时候.更重要的是, 大多数计算并不必要因为很多结点对本身就不相似.因此, 笔者充分利用计算的中间结果, 在每一轮只计算有可能匹配的结点对, 针对该度量设计了一种快速计算的方法α-Rolesim++”.

引入一个参数α, 介于0和1之间, 来帮助控制计算量, 伪代码见算法2.当对一个结点u∈V₁计算相似度的时候(第4行~第14行), 找到上一轮相似度最高的对应点$top = {\max _{v \in {V_2}}}Sim(u, v)$ 1(第5行), 然后设置阈值θ=α·top.V₂的点中, 上一轮相似度不低于θ的被视作有可能与u匹配的点, 这一轮继续计算(第8行、第9行); 上一轮相似度低于q的被视作不可能与u匹配的点, 这一轮被忽略不计算(第11行).

算法2.迭代快速更新相似度矩阵.

$ \begin{array}{l} {\rm{Input}}:{G_1} = ({V_1}, {E_1}), {G_2} = ({V_1}, {E_1});\\ {\rm{Output}}:Sim.\\ \mathit{\boldsymbol{ }}1\mathit{\boldsymbol{ }}Sim \leftarrow InitSim({G_1}, {G_2});\\ \mathit{\boldsymbol{ }}2\mathit{\boldsymbol{ }}{\bf{for}}\;\mathit{ }\underline {i = 1 \to nRounds} \;{\bf{ do}}\\ \mathit{\boldsymbol{ }}3\mathit{\boldsymbol{ }}{\rm{ }}\;\;{\bf{for}}\;\mathit{ }\underline {u \in {V_1}} {\rm{ }}\;{\bf{do}}\\ \mathit{\boldsymbol{ }}4\mathit{\boldsymbol{ }}\;\;\;\;\mathit{\boldsymbol{ }}top \leftarrow \max \{ Sim(u, v)|v \in {V_2}\} ;\\ \mathit{\boldsymbol{ }}5\mathit{\boldsymbol{ }}\;\;\;\;{\bf{for}}\;\mathit{ }\underline {v \in {V_2}} \mathit{ }\;{\bf{do}}\\ \mathit{\boldsymbol{ }}6\mathit{\boldsymbol{ }}\;\;\;\;\;\;\mathit{\boldsymbol{ }}{\bf{if}}\;\mathit{ }\underline {Sim(u, v) \ge \alpha \cdot top} \mathit{ }\;{\bf{then}}\\ \mathit{\boldsymbol{ }}7\mathit{\boldsymbol{ }}\;\;\;\;\;\;\;\;\;\;\;\mathit{\boldsymbol{ }}r \leftarrow \frac{{\gamma (N_1^ + (u), N_2^ + (v)) + \gamma (N_1^ - (u), N_2^ - (v))}}{{{\mathit{\Delta} ^ + }(u, v) + {\mathit{\Delta} ^ - }(u, v)}};\\ \mathit{\boldsymbol{ }}8\mathit{\boldsymbol{ }}\;\;\;\;\;\;\;\;\;\;\;\;Sim'(u, v) \leftarrow (1 - \beta ) \cdot r + \beta ;\\ \mathit{\boldsymbol{ }}9\mathit{\boldsymbol{ }}\;\;\;\;\;\;\;\mathit{\boldsymbol{ }}{\bf{else}}\\ 10\mathit{\boldsymbol{ }}\;\;\;\;\;\;\;\;\;\;\;Sim'(u, v) \leftarrow Sim(u, v);\\ 11\;\;\;\;\;\;\;\mathit{\boldsymbol{ }}{\bf{end}}\\ 12\mathit{\boldsymbol{ }}\;\;\;\;\;\;\mathit{\boldsymbol{ }}{\bf{end}}\\ 13\;\;\;{\bf{end}}\\ 14\mathit{\boldsymbol{ }}\;\;Sim \leftarrow Sim';\\ 15\mathit{\boldsymbol{ }}{\bf{end}}\\ 16\mathit{\boldsymbol{ }}{\bf{return}}\mathit{ }\;\;Sim \end{array} $

参数α具体值的决定方式和敏感度分析, 将在实验部分详细展开.

用这样的计算方法, 原先的全置一的初始化方式不再合适, 需要模拟RoleSim++第1轮的结果, 而这一结果可以在O(|V₁||V₂|)时间复杂度内计算, 因为已知在这样的情况下:

$ \begin{array}{l} \gamma (N_1^ + (u), N_2^ + (v)) = \min \{ |N_1^ + (u)|, |N_2^ + (v)|\}, \\ \gamma (N_1^ - (u), N_2^ - (v)) = \min \{ |N_1^ - (u)|, |N_2^ - (v)|\} . \end{array} $

到目前为止, 用该快速计算的方法以及一个合适的参数α, 可以对基本的迭代计算有一个非常显著的速度改进.

2.2 结点匹配

本节讨论不同的跨图结点匹配算法, 并评估每一个算法的复杂度.准确性的实验评估将在后面给出.

2.2.1 不使用结构信息的匹配

直觉上, 基于结点相似度的去匿名化, 考虑二分图的带权最大匹配.使用KM算法, 最大匹配可以在时间复杂度O(n³)内被计算.

然而, 最大匹配过程求解复杂度高, 难以在大规模图中被采用.Fu等人^[13]采用了一种贪心的方法, 提供了一种对全局最优匹配的近似, 在一定的精确度牺牲的情况下, 能在O(n²logn)时间复杂度内计算.

2.2.2 使用邻居信息的匹配

在第2.2.1节中提到的两种算法都只考虑了相似度的大小, 而图的结构信息被忽略了.通常, 高相似度的结点对在去匿名化过程中更重要, 通过图结构的传递, 能够给它周围的其他结点的匹配提供相当的反馈信息.基于这一点, 先匹配最高相似度的结点对, 然后在后续的匹配中给它们的邻居一个更高的优先级作为反馈, 辅助修正整个匹配过程.笔者设计了两种算法——DfsMatch和NeighborMatch, 二者的时间复杂度都是O(n²).

DfsMatch按照深度优先的顺序匹配结点:首先, 具有最高相似度的一对结点被匹配; 然后, 每当一对结点被匹配, 它们的所有邻居都被加入到一个等待匹配的队列里, 根据相似度的降序排列.对朴素匿名化方法, DfsMatch表现接近完美, 但是对网络噪音的容忍度很差, 因为一旦有一对错误匹配, 所有的邻居对都会被影响, 然后匹配错误.

对NeighborMatch来说, 邻居的优先级按照一个相对少一点的量递增, 从而避免深度优先序那样的限制及其严重后果.具体见算法3, 其过程可以描述如下.

(1)   首先, 预处理相似矩阵Sim, 另一个矩阵rank_score被初始化为原来的相似矩阵的拷贝, 并影响下一步中的结点匹配.对每一个匿名图中的结点u, 在另一张图找与它有最高相似度的点, 记为top(u);

(2)   每一次根据top()挑选出具有最高相似度的点对(u, v)并匹配.既然v被匹配了, 用当前未被匹配的点中相似度最高的更新top(w)=v的点w的top值; 另一方面, 在矩阵rank_score将二者邻居对的值都增加原来相似度值的大小, 并更新相应的top值.

重复上述过程(2), 直到所有结点被匹配.

算法3.结点匹配.

$ \begin{array}{l} {\rm{Input}}:{G_1} = ({V_1}, {E_1}), {G_2} = ({V_2}, {E_2}), score[n][n];\\ {\rm{Output}}:node\_match[n].\\ \mathit{\boldsymbol{ }}1\mathit{\boldsymbol{ }}rank\_sim[n][n] \leftarrow score[n][n];\\ \mathit{\boldsymbol{ }}2\mathit{\boldsymbol{ }}{\bf{for}}\;\;\underline {i = 1 \to n} \;\;{\bf{do}}\\ \mathit{\boldsymbol{ }}3\mathit{\boldsymbol{ }}\;\;\;\mathit{\boldsymbol{ }}top[i] \leftarrow top\;\;{\rm{ }}rank\;\;{\rm{ }}id\\ \mathit{\boldsymbol{ }}4\mathit{\boldsymbol{ }}{\bf{end}}\\ \mathit{\boldsymbol{ }}5\mathit{\boldsymbol{ }}{\bf{for}}\;\;\underline {i = 1 \to n} \;\;{\bf{do}}\\ \mathit{\boldsymbol{ }}6\mathit{\boldsymbol{ }}\;\;\;u \leftarrow FindMax(top);\\ \mathit{\boldsymbol{ }}7\mathit{\boldsymbol{ }}\;\;\;v \leftarrow top[u];\\ \mathit{\boldsymbol{ }}8\mathit{\boldsymbol{ }}\;\;\;node\_match[u] \leftarrow v;\\ \mathit{\boldsymbol{ }}9\mathit{\boldsymbol{ }}\;\;\;\mathit{\boldsymbol{ }}{\bf{for}}\;\;\underline {\forall neighbor\;\;{\rm{ }}pair(x, y){\rm{ }}of{\rm{ }}(u, v)} \;\;{\bf{do}}\\ 10\mathit{\boldsymbol{ }}\;\;\;\;\;\;rank\_score[x][y] \leftarrow rank\_score[x][y] + score[u][v];\\ 11\mathit{\boldsymbol{ }}\;\;\;\;{\bf{end}}\\ 12\mathit{\boldsymbol{ }}\;\;\;\;update{\rm{ }}\;\;top[n]\\ 13\mathit{\boldsymbol{ }}{\bf{end}}\\ 14\mathit{\boldsymbol{ }}{\bf{return}}\;\;node\_match \end{array} $

仍以图 1的情况为例, 在表 1的相似度结果基础上, 第1次可选择点u₁和v₁匹配; 同时, 点对(u₂, v₂), (u₂, v₃), (u₃, v₂), (u₃, v₃), (u₄, v₂), (u₄, v₃)的rank_score将分别被加上0.38.经过4次匹配之后, 能够将图中的点对都正确配对.

3 实验分析

本节通过实验评估了相似度度量和结点匹配算法的性能表现, 将两者和Fu等人^[13]方法的对应部分比较, 在比较中主要关注以下3个方面:(1)结点相似度度量作为中间结果的准确度; (2)去匿名化算法整体的准确度; (3)相似度计算的时间开销以及效率和准确度之间的权衡.

3.1 实验基本设置

本节讨论在实验中使用的公开社交网络数据集, 以及如何从中提取子图作为去匿名化的输入.

3.1.1 数据集

本文选择LiveJournal数据集(LiveJournal数据集发布在http://snap.stanford.edu/data/)和Enron数据集(Enron数据集发布在https://www.cs.cmu.edu/~./enron/).

LiveJournal的图包含4 847 571个结点和68 993 771条有向边, 其中, 每一个结点表示一个Live Journal用户, 每条边表示网站上两个用户之间的朋友关系(有向).由于该图对现有去匿名化算法而言规模过大, 本文随机在其中选取大小为10 000个点的子图用以分析, 并记为G₀=(V₀, E₀).

从G₀中抽取生成一对图G₁=(V₁, E₁)和G₂=(V₂, E₂), 并保证交叠率l, 以此模拟爬虫爬取的社交网络和组织公开发布的匿名化以后的图, 其中交叠率λ定义为$\frac{{{V_1} \cap {V_2}}}{{{V_1} \cup {V_2}}}$.这可以通过宽度优先搜索算法保证.首先, 使用宽度优先搜索爬取一张交叠图G₀=(V₀, E₀), 并且使得|V₀|=λ|V₀|; 然后, 随机将剩余的点一半归入G₁, 一半归入G₂.在这样生成的两张图上, 对G₂应用选择的匿名化算法后, 与G₁一起作为去匿名化的输入.

Enron数据集是一个email关系图, 包含36 692个结点(表示邮件地址)和367 662条有向边(表示邮件通信关系).对该数据集, 全图匿名化后与原图做去匿名化实验.

3.1.2 匿名化算法

在这里列举在实验中用到的所有匿名化算法.

●  朴素匿名化(Naive):该算法简单地打乱结点的标志(编号), 保持结构不变;

●  稀疏化(Sparsify):稀疏化方法随机移除p|E|条边, 其中, 参数p控制匿名化程度;

●  扰动(Perturb):扰动方法先与稀疏化一样随机移除边, 然后增加不存在的边, 直到总的边数和匿名化之前一样.该方法可以看做是对社交网络演化的一种模拟, 或者是无目的性的匿名化;

●  交换(switch):交换方法随机选择两条边(u₁, u₂), (v₁, v₂), 并且不存在边(u₁, v₂), (u₂, v₁).然后交换两条边, 也就是说:边(u₁, u₂), (v₁, v₂)被删除, 而边(u₁, v₂), (u₂, v₁)被添加.这样的过程重复p|E|/2次.

为了保证数据的有效性, 在实验中设置p=0.1.

3.1.3 去匿名化算法

在实验中比较了以下3种去匿名化算法.

●  基准算法(Baseline):Fu等人^[13]提出的去匿名化算法.该算法先通过度数相关的公式计算点对相似度, 然后根据相似度贪心匹配结点对;

●   RoleMatch(Rolesim++):用算法1计算相似度, 再用算法3进行结点匹配.该算法在迭代中, 每轮计算所有点对的相似度, 然后使用相似度加邻居信息匹配结点;

●   RoleMatch(α-Rolesim++):在RoleSim++的基础上用算法2加快相似度计算, 再用算法3进行结点匹配.该算法在相似度迭代中忽略不相似点对, 然后使用相似度加邻居信息匹配结点.

3.1.4 评估准则

为了对3种算法有一个清晰的评估, 在评估去匿名化算法的整体效果时, 提出3个重要的指标.

●  精确度分数:为了评估一个算法, 最直观的方式就是通过正确匹配的比例.这里定义正确匹配的比例为W=W'/|V₁∩V₂|, 其中, W'是正确匹配的对数.由于在同一组去匿名化实验中|V₁∩V₂|是一个常数, 因此, 本文在实验结果中以正确匹配的对数W'来代表每个算法的精确度分数;

●  中间结果分数:由于评估的算法都会生成相似度矩阵来代表结点对的相似度, 就用最相似对恰好是正确匹配的数量来评估相似度模型.也就是说, 令S'为G₁中这样的点的数量, 它对应的正确匹配点恰好是相似度最高的点, 那么定义相似度比例为S=S'/|V₁∩V₂|.与精确度分数相同, 本文在实验结果中以S'来代表中间结果分数;

●  执行时间:如果一个算法时间复杂度非常高, 那么该算法就不可能被应用于大规模的图, 应用性不好.本文用T来表示实验中算法的执行时间.

3.1.5 实验环境

在实验中使用了一台配置为AMD Opteron Processor 4180(6核, 12线程, 2.6GHz), 48GB内存的机器.由于迭代计算的阶段可以直接并行, 实验中使用了8个线程.所有的算法都用C++实现.

3.2 评估

本文在不同的交叠率和匿名化算法下进行了一系列实验, 并评估了3种去匿名化算法的性能(基于之前提出的评估准则).在实验中, 交叠率分别被设置为50%和100%.在每一种情况下, 为3种算法随机生成10对图, 并用平均结果来分析.

3.2.1 参数选择

●  衰减因子:根据RoleSim^[8]的结果, 选取β=0.15.

●  迭代轮数:3种算法在实现时均采用了迭代计算, 迭代计算结点相似度时, 迭代轮数会影响精度, 迭代轮数越多时精度越高, 但是花费的时间也更多.因此需要通过实验确定迭代轮数与精度间的平衡.实验结果如图 2所示, 在LiveJournal数据集上使用稀疏化匿名化算法以及RoleSim++去匿名化.实验的结果表明, 正确的匹配数在5轮以后就基本保持不变.因此, 本文将后续实验中的迭代轮数统一设置为5轮;

●  加速算法中的参数α:从算法3中可以直观地看出:当α越小时, 每轮迭代的点数越多, 精度越高, 然而时间开销也越大(当α=0时与RloeSim++等价).我们需要选定一个a值, 在精度得到保持的情况下, 时间开销尽量小.调整α从0.95~0.50, 步长0.05, 在10对从LiveJournal数据集中随机提取的图上跑RoleSim++算法和α-Rolesim++算法, 结果如图 3所示.当α增大时, 时间开销几乎是线性减少的; 而在α≤0.85时, 精度能得到较好的保持.因此在后续实验中, 选定α=0.85.

3.2.2 对匹配精度的比较

本节实验对比了3种去匿名化算法的精度.在实验中, 对各种匿名化算法生成的目标图, 用3种算法进行去匿名化, 统计正确匹配顶点的数量.在LiveJournal数据集上, 分别按交叠率50%和100%实验; 在Enron数据集上, 设定交叠率为100%, 实验的匹配结果如图 4所示.

在这两个数据集上的3小组实验, 结果是一致的.对经过朴素匿名化的目标图, 基准算法(Baseline)在交叠率50%和100%的图上, 效果几乎和本文提出的算法相当.这是因为匿名化算法不改变交叠部分的图结构, 给去匿名化降低了难度.当不同的去匿名化算法被应用的时候, 本文提出的RoleMatch算法精度远远高于基准算法.后者的表现在不同的匿名化方法上差异很大, 在交换匿名化上表现最差, 当交叠率为50%时, 只去匿名化了40%的交叠点.RoleMatch(Rolesim++)算法和RoleMatch(α-Rolesim++)算法在每一种匿名化算法下都保持了较好的健壮性, 在LiveJournal数据集的实验中, 大约能正确匹配80%以上的交叠点; 在Enron数据集的结果中, 也能正确匹配一半以上.

3.2.3 局部去匿名化

本节实验对比了3种算法在非匿名图和匿名图大小不同时的去匿名化的效果.实验中, 我们从LiveJournal图中爬取一定大小的非匿名图, 并应用匿名化算法于实验图中得到匿名图.这样, 非匿名图即为匿名图的局部子图.两张图的交叠率从15%~35%进行匹配实验, 多次匹配并求取平均值.实验结果如图 5所示.

在图 5中可以看到:随着交叠率的增加, 3种算法的匹配精度均出现增长.当交叠率低于0.15时, 3种算法的去匿名化精度均低于50%.这是因为当交叠率低于15%时, 匿名图中其他点过多对去匿名化造成影响较大.当交叠率高于0.20后, Rolesim算法和Rolesim++算法都取得了80%以上的去匿名化精度, 而Baseline算法的去匿名化精度始终低于40%.

3.2.4 对中间结果的考察

为评估相似度算法的合理性, 本节实验对比了3种算法的中间结果精度.在实验中, 选择第1阶段迭代计算之后得到的相似度矩阵, 对每个匿名化后的顶点, 统计与其相似度最高的顶点恰好是正确匹配的数量.进而又统计了对每个匿名化后的顶点, 正确匹配的相似度位于前1%~10%的比例.比较得到的结果如图 6和图 7所示.

Rolesim++算法和α-Rolesim++算法在不同的匿名化算法下比基准算法有更好的表现, 尤其是当交叠率不高的时候.另外, 当交叠率逐渐降低时, Rolesim++算法和α-Rolesim++算法之间的差别逐渐明显.与图 4相对照, 更好的相似度度量可以带来更高的去匿名化精度.基准算法在交换匿名化上有最差的精度表现, 它的相似度分数也在该匿名化上表现最差(低于1%).

在这个最相似点对的基础上, 可以通过优先匹配相似度高的点对获得更高的精确度, 因为它们往往有更大的概率是正确的匹配.这也是为什么很多最相似度不排在第1的点对, 在结点匹配阶段之后能够被正确匹配, 而最后的去匿名化结果比中间结果要好.

3.2.5 执行时间

本节实验比较Rolesim++算法和α-Rolesim++算法的时间性能.Baseline算法的时间复杂度和实验中的实际耗时与Rolesim++算法并没有显著区别, 因此不再与之比较.对于每种去匿名化算法, 分别使图中点的数量|V|与边的平均密度d增加.

图 8展示了算法执行时间的变化.Rolesim++算法的执行时间随着点数与边的密度的增加而显著增加, 而α-Rolesim++算法总是比它更快, 而且耗时的增加相对缓慢.由此体现了α-Rolesim++算法的高效性.

4 结论

本文提出了一种不需要已知种子的去匿名化算法RoleMatch, 分为结点相似度计算阶段和结点匹配阶段.其中, 结点相似度阶段计算的精确而具有容错性的相似度, 刻画了不同的图中结点有同一身份的可能性; 动态的结点匹配阶段同时考虑了结点的相似度对匹配的影响, 以及之前匹配结果的反馈.这一算法仅需要社交网络图的拓扑结构信息, 产生非常好的去匿名化结果, 并有一个快速计算的版本, 能够高效去匿名化.在LiveJournal真实数据集上进行的实验, 实验方式在传统对称去匿名化的基础上还进行了更贴合应用情景的局部去匿名化实验, 各项实验的结果进一步表明了去匿名化的准确性和高效性.接下来, 我们将进一步考虑算法的分布式实现, 并考虑在富信息图上利用更多的信息进行去匿名化.