基于改进轮廓信息模型的异构去匿名化算法
2022-04-20张小云
张小云
(武警甘肃总队，甘肃, 兰州 730046)
0 引言
社交网络[1-2]已成为人们生活不可或缺的一部分。随着社交网络的普及，人们享受着各种社交网络的丰富功能和服务，包括分享状态更新、发布照片、与他人交流和交友。由于不同社交网络的功能不同，用户往往会出于不同的目的登录多个社交网络，如微信、微博、QQ等。聚合不同社交网络的用户档案可以揭示用户的相关信息。然而跨网络信息是一把双刃剑：一方面，一旦识别或映射了用户在不同社交网络中的多个账户，就可以收集这些账户的配置文件、偏好和活动，从而有利于个性化、目标定位和推荐[3]；另一方面，可利用跨网络聚合收集目标用户的各个方面的信息，这将导致严重的隐私泄露问题[4]。因此，社交网络正面临着去匿名化攻击的威胁。
社交网络去匿名化是近年来的一个研究热点。刘家霖等[5]基于社交网络的拓扑结构，提出了一种高效高精度的无种子去匿名化算法RoleMatch识别个体身份。胡开先等[6]提出了一种基于社交关系的多数投票的身份识别方法，对社交关系中的用户身份特征进行统计，推测当前用户的地址信息、实体信息和用户兴趣。胡光武等[7]将社交网络的去匿名问题转化为辅助网络与匿名网络之间的节点匹配问题，并提出了一种基于随机森林分类器的社交网络去匿名方案。王照永等[8]利用社交网络图的结构特征与节点属性的特征之间的相似性差异实现节点间的映射，并提出一种基于用户社交网络图的结构和用户节点的特征来披露用户敏感信息的去匿名方法。上述方法大多数基于同一组用户的不同社交网络应该显示相似的网络拓扑结构的假设。这种方法的观察结果导致用户倾向于在不同的社交网络中与他们感兴趣或熟悉的相似用户建立联系。然而，在异构的社交网络中，由于不同社交网络的用户并不总是重叠的，不同社交网络使用模式的多样性将进一步导致不同社交网络的网络结构不一致。
为了进一步研究异构的社交网络聚合导致的隐私泄露，本文设计一种异构去匿名化算法。该方法联合利用公开的网络结构信息和用户信息，可以显著提高检测精度。
1 相关概念
1.1 图论
社交网络结构通常表示为一个图[9]，其中，每个用户是图中的一个节点，一对用户之间的连接表示为边。设G=(V,E)表示一个社交网络图，其中，V是一组用户，E⊂V×V是用户之间的一组有向/无向链接。e(v1,v2)表示v1和v2是朋友关系或跟随关系，其中：e∈E；v1,v2∈V。邻域和社区作为社交网络图中的重要结构，形式化定义如下。
定义1 用户vi的邻域集R是一组用户Ri=[vj]j=1,…,∀vj:∃e(vj,vi)，他们与vi有直接的朋友关系或跟随关系。进一步定义了函数α表示vi的邻域集Ri，即α(vi)=Ri。
定义2 社交网络图中的社区C是G=(V,E)中顶点的不相交划分。
形式上，本文将图中的社区表示为C={C1,C2,…,Ck}，其中Ci≠Φ且Ci∩Ci=Φ(i≠j，i≥1和j≤k)。∀Ci∈C，有VCi⊂V和ECi⊂VCi×VCi。本文假定社区由Infomap算法定义，该算法使用网络上随机游动的概率流，并通过压缩概率流的描述将网络分解为模块。
1.2 轮廓信息模型
作为旨在吸引眼球、提升自我展示、促进和维持社会资本的平台，社交网络必须允许公众获得部分用户资料信息。根据平台定义和/或用户定义的隐私设置，社交网络上公开的个人资料信息量各不相同。为了利用异构社交网络中的个人资料信息，本文首先给出一个统一的定义。
定义3 设Xi=[xik]k=1,…,d表示与用户vi∈V相关联的一组属性(例如用户名(昵称)、位置、自我描述等)，其中，d是属性类型的数目，xik记录用户vi的第k个属性的内容。如果用户vi的第j属性在社交网络上不可用(例如，用户选择不在微信上显示其位置信息)，则xij=null。
需注意，一个用户可能有几个向量来模拟他/她拥有账户的社交网络中的不同配置文件。两个向量之间的公共属性将用于计算轮廓相似度。
由于异构社交网络平台包含不同类型的概要信息，并且其中一些包含语义或句法意义，因此从2个异构社交网络映射2个用户账户类似于一个本体匹配问题。通常，本体匹配确定一对本体O1和O2的相似度。每个本体由一组离散的属性组成，这些属性通常以表、类、属性的形式表示，并确定输出关系。本文假定轮廓匹配定义如下。
定义4pA={x1,x2,…,xA}和pU={x1,x2,…,xU}为2个轮廓。如果2个属性xi∈pA和xj∈pU，有type(xi)=type(xj)，则2个属性之间的相似度定义为
sima=matchScore(xi,xj)
(1)
这里的相似度取决于所考虑的属性，可以是年龄或性别值的相似度、昵称名称的字符串相似度、描述或文本相似度、位置或家乡的语义相似度等。然后通过式(2)计算轮廓的相似度，
(2)
其中，wr为赋予属性的权重，t为2个轮廓之间相同类型的属性对的数目。
1.3 攻击模型
假设2个异构的社会网络图为GA和GU，GA表示匿名网络图，GU表示为辅助网络图。注意，这里的图不一定是社交网络的整个图，反匿名攻击可以对攻击者收集的部分图(即子图)进行。也就是说，攻击者能够通过发布的数据集或爬网站点获得子图G=(V,E)和对应于vi∈V的轮廓属性Xi。攻击者的目标是通过将GA中的用户映射到GU中的用户来了解不同网络中用户的更多信息。为了实现这一目标，攻击者需要从2个不同的社交网络中大规模、高置信度地识别属于同一个人的账户。因此，攻击模型可形式化定义为如下问题。
考虑2个不同的社交网络图GA=(VA,EA)和GU=(VU,EU)，Vi∈VA和Vj∈VU的属性集合定义为Xi和Xj。通过迭代计算，用户映射vi↔vj(vi∈VA，vj∈VU)表示属于同一个人，则有
(3)
其中，S是计算Xi和Xj之间相似度的函数(式(2))。Cand.A和Cand.B分别是GA和GU中由社区和邻域结构生成的潜在正确映射的2个候选集。
2 异构去匿名模型
图1为异构去匿名模型结构。该结构有3个主要步骤：①社区检测，根据社交网络图结构检测网络中的社区；②社区对齐，根据轮廓自动识别种子，并对齐包含相同种子对的社区；③在社区节点映射，在每对对齐的社区中计算具有高相似度得分的节点，该得分由轮廓相似度计算，并传播到其邻域节点。算法1为整个过程执行过程。
图1 异构去匿名模型结构
算法1 异构去匿名模型执行过程输入:GA
2.1 社区检测
第一步的目标是将社交网络图GA和GU划分为两组社区CA={c1,c2,…,cm}和CB={c1,c2,…,cn}。在Infomap算法[10]的基础上设计社区检测算法，该算法具有较低的时间复杂度，可以将不相交、不重叠的社区CA和CU分别划分为2个图。简言之，Infomap找到了随机游走者的最短多级描述，因此给出了网络的最佳分层聚类、每个层次上的最佳层数和模块划分。因此，使用Infomap算法的另一个优点是它可以在不同的层次上生成不同尺度的CA和CU，这样就可以选择相似尺度的社区进行对齐。社区检测和划分的算法在算法1中用Infomap(·)函数表示，且其时间复杂度为O(|E|)。
2.2 社区对齐
考虑到公共可用的概要信息，社区可以更容易地对齐。选择用户名(或昵称)来识别种子。主要原因如下：首先，用户名(或昵称)必须在每个社交网络的网站上都可用，因此攻击者有足够的机会获取或爬网它们；其次，具有相同用户名(或昵称)的2个账户有较大概率属于同一用户。
设计应用于社交网络的社区对齐算法，该算法可分为两步执行，并根据社区中相同用户名的个数来对齐CA和CU。
步骤1 找到具有相同用户名μ={…,(ui,uj)k,…}的所有用户对，其中ui∈VA和uj∈VU。使用贪婪搜索会导致O(|VA||VU|)的高度复杂性。为降低复杂度，采用哈希表实现这一过程，这样时间复杂度就可以降低到O(|VA|+|VU|)。此过程在算法1中表示为SelectSeeds(·)函数；
步骤2 将每对社区(Ci,Cj)的初始置信度csi,j(表明2个社区是否应对齐)设置为0，其中Ci∈CA，1≤i≤m，Cj∈CU，1≤j≤n。对于每对(up,uq)∈μ，csi,j逐次累计加1，且有up∈Ci和uq∈Cj。接着，检查社区对的所有置信度cs，如果csi,j超过阈值θcs，则对齐Ci和Cj。该过程的时间复杂度为O(|μ|) 综上，社区对齐算法的总体复杂度为O(|VA|+|VU|)。 算法2描述了社区内节点映射算法。在每对对齐的社区内，依次执行传播和映射算法。 算法2 InCommunityMapping(·)算法执行过程输入:社区对CommPairs,种子μ,阈值θ;输出:用户映射μ′ For (Ca,Cu)j∈CommPairs do μj=Propagation(Ca,Cu)endreturn μ′=∪j=1,…,len(CommPairs)μjDef Propagation(R1,R2): μj∈μ While exists 该算法以Gc1=(Vc1,Ec1)，Gc2=(Vc2,Ec2)2个社区图和社区中的种子集μc1,c2作为输入。算法执行时在μc1,c2的相邻种子集中迭代地寻找新的映射，并基于图结构扩展映射过程。在每次迭代中，该算法计算2个相邻集Ru=α(u)和Rv=α(v)内的相似度得分，且这2个相邻集由2个已映射的用户u和v生成。进一步，∀ru∈Ru，计算与Rv中用户的相似度得分，并找出得分最高的rv。算法中采用MatchScore(·)函数计算相似度，如果得分超过预先定义的阈值θ，则ru和rv表示成功的映射。如果一个已经映射的节点被映射到另一个具有更高相似度分数的节点，则先前的映射将被具有更高分数的新映射替换。如果没有发现新的映射，则该过程将停止，并收集2个社区传播过程中未访问的节点进行比较以找到剩余的映射。 传播过程的时间复杂度为O(min{|Vc1|,|Vc2|}dc1dc2)，其中dc1和dc2分别是Vc1和Vc2中节点度的界限。 以2个异构在线社交网络的数据集(Flickr和Last.fm)验证本文所提方法。数据集包括节点信息、边缘信息和社交网络用户子集的概要信息。根据社交网络数据集中的“朋友”或“跟随”关系构建无向社交网络图。统计数据信息如表1所示。仿真环境使用Python语言，程序运行在2.4 GHz CPU，内存为32 G的服务器上。此外，选取准确率及召回率作为性能指标验证算法性能。 表1 社交网络数据集信息统计 图2和图3为不同阈值θ下本文方法与传统轮廓匹配方法分别在数据集Flickr和Last.fm准确率和召回率对比结果。可以看出，本文方法结果明显优于传统轮廓匹配方法。由前述可知，阈值θ是一个相似性准则，本文算法中接受一对节点作为映射，即如果2个节点之间的相似性得分超过θ，则这2个节点表示为潜在映射。因此，θ越高，接受的节点越相似，因此返回的潜在映射就越少。所以θ实际上反映了精确性和召回之间的权衡。实际情况下，攻击者可以根据自己的要求来选择θ。当阈值设置为0.9时，本文方法匹配准确度可达90%以上，召回率可达40%。仿真结果进一步验证了该算法可以实现大规模精确解匿名。 图2 Flickr数据集仿真结果 图3 Last.fm数据集仿真结果 图4为所提出模型在Flickr数据集中与基于节点匹配[11]、RoleMatch算法[12]的性能曲线,其中阈值设置为0.9，可以看出，所提模型在40次迭代时可获得最佳性能，而其他模型在60次以上迭代时可获得最佳性能，且模型准确率有所提升。由此可见，所提模型收敛速度更快，且模型性能更优。 图4 不同算法性能对比结果 本文对异构社交网络中去匿名化过程过程进行了研究与分析，并提出了一种异构去匿名化算法提高模型检测精度。 本文在进行仿真及实验验证时假定用户信息都为准确的，未考虑部分用户可能会填写“假信息”或仅有部分信息情况。未来可对信息获取条件受限及数据存在坏值等情况进行研究，引入大数据、数据挖掘、人工智能等技术提高用户相似性匹配度等，进一步提升模型适用性范围。此外，社区匹配的置信度阈值在实际状况下可以自由选择，未来可引入机器学习模型对阈值进行调参，选取最优阈值。2.3 社区内节点映射
3 仿真与分析
3.1 阈值选取测试
3.2 算法性能测试
4 总结
