一种保持结点可达性的高效社会网络图匿名算法

来源：软件学报杂志2016年第8期北京时间：

作者：刘向宇,李佳佳,安云哲,周大海,夏秀峰

单位：刘向宇，沈阳航空航天大学 计算机学院, 辽宁 沈阳 11013611,李佳佳，沈阳航空航天大学 计算机学院, 辽宁 沈阳 11013602,安云哲，沈阳航空航天大学 计算机学院, 辽宁 沈阳 11013603,周大海，沈阳航空航天大学 计算机学院, 辽宁 沈阳 11013604,夏秀峰，沈阳航空航天大学 计算机学院, 辽宁 沈阳 11013605

摘要：为了保护社会网络隐私信息，提出了多种社会网络图匿名化技术.图匿名化目的在于通过图修改操作来防止隐私泄露，同时保证匿名图在社会网络分析和图查询方面的数据可用性.可达性查询是一种基本图查询操作，可达性查询精度是衡量图数据可用性的一项重要指标.然而，当前研究忽略了图匿名对结点可达性的影响，导致较大的可达性信息损失.为了保持匿名图中结点的可达性，提出了可达性保持图匿名化（reachability preserving anonymization，简称RPA）算法，其基本思想是将结点进行分组并采取贪心策略进行匿名，从而减少匿名过程中的可达性信息损失.为了保证RPA算法的实用性，针对其执行效率进行优化，首先提出采用可达区间来高效地评估边添加操作所导致的匿名损失；其次，通过采用候选邻居索引，进一步加速RPA算法对每个结点的匿名过程.基于真实社会网络数据的实验结果表明了RPA算法的高执行效率，同时验证了生成匿名图在可达性查询方面的高精度.

关键词：社会网络;隐私;匿名;可达性

基金资助：国家自然科学基金（61502316，61502317）；沈阳航空航天大学校博士启动金（15YB36）