主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第12期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
刘向宇,李佳佳,安云哲,周大海,夏秀峰.一种保持结点可达性的高效社会网络图匿名算法.软件学报,2016,27(8):1904-1921
一种保持结点可达性的高效社会网络图匿名算法
Efficient Algorithm on Anonymizing Social Networks with Reachability Preservation
投稿时间:2015-12-16  修订日期:2016-04-14
DOI:10.13328/j.cnki.jos.005092
中文关键词:  社会网络  隐私  匿名  可达性
英文关键词:social network  privacy  anonymization  reachability
基金项目:国家自然科学基金(61502316,61502317);沈阳航空航天大学校博士启动金(15YB36)
作者单位E-mail
刘向宇 沈阳航空航天大学 计算机学院, 辽宁 沈阳 110136 liuxy@sau.edu.cn 
李佳佳 沈阳航空航天大学 计算机学院, 辽宁 沈阳 110136  
安云哲 沈阳航空航天大学 计算机学院, 辽宁 沈阳 110136  
周大海 沈阳航空航天大学 计算机学院, 辽宁 沈阳 110136  
夏秀峰 沈阳航空航天大学 计算机学院, 辽宁 沈阳 110136  
摘要点击次数: 1847
全文下载次数: 1395
中文摘要:
      为了保护社会网络隐私信息,提出了多种社会网络图匿名化技术.图匿名化目的在于通过图修改操作来防止隐私泄露,同时保证匿名图在社会网络分析和图查询方面的数据可用性.可达性查询是一种基本图查询操作,可达性查询精度是衡量图数据可用性的一项重要指标.然而,当前研究忽略了图匿名对结点可达性的影响,导致较大的可达性信息损失.为了保持匿名图中结点的可达性,提出了可达性保持图匿名化(reachability preserving anonymization,简称RPA)算法,其基本思想是将结点进行分组并采取贪心策略进行匿名,从而减少匿名过程中的可达性信息损失.为了保证RPA算法的实用性,针对其执行效率进行优化,首先提出采用可达区间来高效地评估边添加操作所导致的匿名损失;其次,通过采用候选邻居索引,进一步加速RPA算法对每个结点的匿名过程.基于真实社会网络数据的实验结果表明了RPA算法的高执行效率,同时验证了生成匿名图在可达性查询方面的高精度.
英文摘要:
      As a proven effective solution to privacy preservation, graph anonymization has been studied extensively. The goal of graph anonymization is to avoid disclosure of privacy in social networks through graph modifications while at the same time preserving data utility of the anonymized graph for social network analysis and graph queries. Reachability is an important graph data utility as reachable queries are not only common on graph databases but also serving as fundamental operations for many other graph queries. However, the reachability of each vertex in the anonymized graph is severely distorted after the anonymization due to neglecting that the reachability is highly sensitive to edge modifications. This work solves the problem by designing a reachability preserving anonymization (RPA) algorithm. The main idea of RPA is to organize vertices into groups and greedily anonymizes each vertex with low impact on reachability. A number of techniques are designed to make RPA efficient. Firstly, reachable interval is proposed to efficiently measure the anonymization cost incurred by an edge addition. Secondly, an index structure, CN-index is adopted to accelerate anonymizing each vertex. Extensive experiments on real datasets demonstrate that RPA performs with high efficiency and the generated anonymized social networks preserve high data utility on reachable queries.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利