一种基于无向图修改的社交网络隐私保护方法

摘要

本发明公开了一种基于无向图修改的社交网络隐私保护方法，包括：（1）构建社交网络的无向图；（2）挖掘最大频繁子图；（3）构建节点映射关系；（4）对子图进行迭代扩展并完善映射表；（6）根据映射表，在无向图中添加映射线和虚假节点形成匿名同构图。本发明通过对添加若干虚假节点使得每个节点都有与之对称的其它节点，避免用户身份的重新定位，有效的保护用户的个人隐私安全；另外本发明通过对社交网络图局部结构的精细修改，可以安全的对外发布社交网络图数据，适用于研究社交网络局部结构特征分析统计，促进了数据挖掘技术在社交网络领域的研究与应用。

主权项

一种基于无向图修改的社交网络隐私保护方法，包括如下步骤：(1)构建待发布社交网络的无向图H；无向图H中每个节点对应代表每个用户，任意两节点间的连线代表对应两个用户的好友关系；(2)删除无向图H中各节点的身份信息，得到无向图G；通过最大频繁子图挖掘算法从无向图G中挖掘出最大频繁子图集合，并从最大频繁子图集合中任取出k个子图组成待删除子图集合，k为大于1的自然数；(3)确定待删除子图集合中k个子图间节点的对应关系，进而构建节点映射表；(4)对待删除子图集合中各子图进行扩展：4.1.找出各子图中的边缘节点；对于任一子图中的任一节点，若与其相连的其他所有节点不完全在该子图内，则称该节点为该子图的边缘节点，与边缘节点相连且不在该子图内的其他节点为边缘节点的扩展节点；4.2.对于任一边缘节点，确定与其对应的其他k‑1个边缘节点；从这组相互对应的边缘节点中找出扩展节点最多的边缘节点，其扩展节点个数为m，将该边缘节点的所有扩展节点均纳入其所在子图内；4.3.对于这组相互对应的边缘节点中的其他任一边缘节点，将该边缘节点的所有扩展节点均纳入其所在子图内，并补充虚假节点与其相连，直至其扩展节点和虚假节点的个数总和达到m，同时将这些虚假节点纳入其所在子图内，所述的虚假节点的属性信息为从无向图G中任意节点上复制而来；4.4.根据步骤4.2和4.3，遍历待删除子图集合中各组相互对应的边缘节点；根据以下算式计算扩展后待删除子图集合的匿名代价值：C＝E+0.5(k+1)Σ其中：C为匿名代价值，E为扩展后待删除子图集合中新增加的连线条数，Σ为扩展后待删除子图集合中的跨线总数；对于子图中的任一节点，若该节点与子图外的节点有连线，则该连线为子图的跨线；(5)通过比较当前扩展后待删除子图集合的匿名代价值与上一次扩展后待删除子图集合的匿名代价值，对待删除子图集合进行迭代扩展，每迭代扩展一次则对节点映射表更新一次，直至迭代扩展收敛；将迭代扩展收敛后的待删除子图集合从无向图G中删除，得到无向图G’，并返回步骤(2)中再对无向图G’进行最大频繁子图挖掘，依此循环操作直至无向图G删空；(6)根据所述的节点映射表，通过在无向图G中添加映射线和虚假节点形成匿名同构图，并对该匿名同构图进行发布；在无向图G中添加映射线和虚假节点的方法如下：6.1.对于无向图G中的任一条连线，确定该连线对应的一对节点；6.2.根据映射排列顺序，从节点映射表中确定出与这对节点对应的k‑1对映射节点；6.3.从无向图G中找出这k‑1对映射节点，若有缺失，则在无向图G中添加虚假节点作为映射节点，然后通过映射线使每对映射节点连接；6.4.根据步骤6.1～6.3，遍历无向图G中的每一条连线。