面向数值型敏感属性的隐私保护方案

针对现有的个性化隐私匿名技术不能很好地解决数值型敏感属性容易遭受近邻泄漏的问题,提出了一种基于聚类技术的匿名模型——（ε_i,k）-匿名模型.该模型首先基于聚类技术将按升序排列的敏感属性值划分到几个值域区间内;然后,提出了针对数值型敏感属性抵抗近邻泄漏的（ε_i,k）-匿名原则;最后,提出了一种最大桶优先算法来实现（ε_i,k）-匿名原则.实验结果表明,与已有的面向数值型敏感属性抗近邻泄漏方案相比,该匿名方案信息损失降低,算法执行效率提高,可以有效地降低用户隐私泄露风险.     

改进k值自动获取VDBSCAN聚类算法

针对DBSCAN聚类算法不能对变密度分布数据集进行有效聚类,VDBSCAN算法借助k-dist图来自动获取各个密度层次的数据对象的邻域半径,解决了具有不同密度层次分布数据集的聚类问题. k-VDBSCAN算法通过对k值的自动获取,减小了VDBSCAN中参数k对最终聚类结果的影响. 针对k值的自动获取,在原有的k-VDBSCAN聚类算法基础上,依据数据集本身,利用数据对象间距离的特征,提出了一种k值改进自动获取聚类算法. 理论分析与实验结果表明,新的改进算法能够有效的自动获得参数k的值,并且在聚类结果、时间效率方面都有明显的提高.     

求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n²),对Laplacian矩阵特征分解的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n²).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.     

面向缺失数据的数据匿名方法

在数据发布过程中,为了防止隐私泄露,需要对数据的准标识符属性进行匿名化,以降低链接攻击风险,实现对数据所有者敏感属性的匿名保护.现有数据匿名方法都建立在数据无缺失的假设基础上,在数据存在缺失的情况下会直接丢弃相关的记录,造成了匿名化前后数据特性不一致.针对缺失数据匿名方法进行研究,基于k-匿名模型提出面向缺失数据的数据匿名方法KAIM(k-anonymity for incomplete mircrodata),在保留包含缺失记录的前提下,使在同一属性上缺失的记录尽量被分配到同一分组参与泛化.该方法将分组泛化前后的信息熵变化作为距离,基于改进的k-member 算法对数据进行聚类分组,最后通过基于泛化层次的局部泛化算法对组内数据进行泛化.实际数据集的大量实验结果表明,KAIM 造成信息缺损仅为现有算法的43.8%,可以最大程度地保障匿名化前后数据特性不变.     

图数据发布隐私保护的聚类匿名方法

社交网络中积累的海量信息构成一类图大数据,为防范隐私泄露,一般在发布此类数据时需要做匿名化处理.针对现有匿名方案难以防范同时以结构和属性信息为背景知识的攻击的不足,研究一种基于节点连接结构和属性值的属性图聚类匿名化方法,利用属性图表示社交网络数据,综合根据节点间的结构和属性相似度,将图中所有节点聚类成一些包含节点个数不小于k的超点,特别针对各超点进行匿名化处理.该方法中,超点的子图隐匿和属性概化可以分别防范一切基于结构和属性背景知识的识别攻击.另外,聚类过程平衡了节点间的连接紧密性和属性值相近性,有利于减小结构和属性的总体信息损失值,较好地维持数据的可用性.实验结果表明了该方法在实现算法功能和减少信息损失方面的有效性.     

基于图压缩的k可达查询处理

研究了基于图压缩的k可达查询处理,提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法,k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系,因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边,然后使用k-RPC获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明,对于稀疏的原始图,两种压缩算法的压缩比分别可以达到45%,对于稠密的原始图,两种压缩算法的压缩比分别可以达到75%和67%;与在原始图上直接进行查询处理相比,两种基于压缩图的查询处理算法效率更好,在稀疏图上的查询效率可以提高2.5倍.     

路网环境下兴趣点查询的隐私保护方法

近年来,随着无线通信技术的迅猛发展,推动了基于位置服务（Location-based services,LBS）的发展进程.而其中兴趣点（Point of Interest,POI）查询是基于位置服务最重要的应用之一.针对在路网环境下,用户查询过程中位置隐私泄露的问题,提出了一种新的位置k匿名隐私保护方法.首先,匿名服务器将兴趣点作为种子节点生成网络Voronoi图,将整个路网划分为相互独立且不重叠的网络Voronoi单元（Network Voronoi Cell,NVC）;其次,利用Hilbert曲线遍历路网空间,并按照Hilbert顺序,对路网上所有的兴趣点进行排序.当用户发起查询时,提出的匿名算法通过查找与用户所在NVC的查询频率相同且位置分散的k-1个NVC,并根据用户的相对位置在NVC内生成匿名位置,从而保证了生成的匿名集中位置之间的相互性,克服了传统k-匿名不能抵御推断攻击的缺陷.最后,理论分析和实验结果表明本文提出的隐私保护方案,能有效保护用户位置隐私.     

基于Voronoi-R*的隐私保护路网k近邻查询方法

针对已有的保护位置隐私路网k近邻查询依赖可信匿名服务器造成的安全隐患,以及服务器端全局路网索引利用效率低的缺陷,提出基于路网局部索引机制的保护位置隐私路网近邻查询方法.查询客户端通过与LBS服务器的一轮通信获取局部路网信息,生成查询位置所在路段满足l-路段多样性的匿名查询序列,并将匿名查询序列提交LBS服务器,从而避免保护位置隐私查询对可信第三方服务器的依赖.在LBS服务器端,提出基于路网基本单元划分的分段式近邻查询处理策略,对频繁查询请求路网基本单元,构建基于路网泰森多边形和R^*树的局部Vor-R^*索引结构,实现基于索引的快速查找.对非频繁请求路网基本单元,采用常规路网扩张查询处理.有效降低索引存储规模和基于全局索引进行无差异近邻查询的访问代价,在保证查询结果正确的同时,提高了LBS服务器端k近邻查询处理效率.理论分析和实验结果表明,所提方法在兼顾查询准确性的同时,有效地提高了查询处理效率.     

基于随机kNN图的批量边删除聚类算法

建立邻接图上的批量边删除聚类算法通用框架,提出基于高斯平滑模型的批量边删除判定准则,定义了适于聚类的邻接图的一般性质,提出并证明在kNN图基础上引入随机因子构造的随机kNN图,可以增强顶点之间的局部连通性,使聚类结果不再强烈依赖于某条边或某些边的保留或删除.RkNNClus算法简洁高效,依赖参数少,无需指定类簇数目,模拟和真实数据上的实验均有证明.     

面向表数据发布隐私保护的贪心聚类匿名方法

为了防范隐私泄露,表数据一般需要匿名处理后发布.现有匿名方案较少分类考察准标识属性概化,并缺少同时考虑信息损失量和时间效率的最优化.利用贪心法和聚类划分的思想,提出一种贪心聚类匿名方法：分类概化准标识属性,并分别度量其信息损失,有利于减小并合理评价信息损失.对元组间距离和元组与等价类距离,建立与最小合并概化信息损失值正相关的距离定义,聚类过程始终选取具有最小距离值的元组添加,从而保证信息损失总量趋于最小.按照k值控制逐一聚类,实现等价类均衡划分,减少了距离计算总量,节省了运行时间.实验结果表明,该方法在减少信息损失和运行时间方面是有效的.     

动态社会网络隐私保护方法研究*

针对动态社会网络数据多重发布中用户的隐私信息泄露问题,结合攻击者基于背景知识的结构化攻击,提出了一种动态社会网络隐私保护方法。该方法首先在每次发布时采用k-同构算法把原始图有效划分为k个同构子图,并最小化匿名成本;然后对节点ID泛化,阻止节点增加或删除时攻击者结合多重发布间的关联识别用户的隐私信息。通过数据集实验证实,提出的方法有较高的匿名质量和较低的信息损失,能有效保护动态社会网络中用户的隐私。     

社会网络中基于节点平均度的k-度匿名隐私保护方案

社会网络数据的发布可能导致用户隐私被泄露,例如用户的身份信息可能被恶意攻击者通过分析网络中节点的度数识别出来,针对这个问题提出一种基于节点平均度的k-度匿名隐私保护方案.方案首先利用基于平均度的贪心算法对社会网络节点进行划分,使得同一分组中节点的度都修改成平均度,从而生成k-度匿名序列;然后利用优先保留重要边的图结构修改方法对图进行修改,从而实现图的k-度匿名化.本方案在生成k-度匿名序列时引入平均度,提高了聚类的精度,降低了图结构修改的代价.同时,由于在图结构修改时考虑了衡量边重要性的指标—邻域中心性,重要的边被优先保留,保持了稳定的网络结构.实验结果表明,本方案不仅能有效地提高网络抵抗度攻击的能力,还能极大降低信息损失量,在保护用户隐私的同时提高了发布数据的可用性.     

Publishing anonymous survey rating data

We study the challenges of protecting privacy of individuals in the large public survey rating data in this paper. Recent study shows that personal information in supposedly anonymous movie rating records are de-identified. The survey rating data usually contains both ratings of sensitive and non-sensitive issues. The ratings of sensitive issues involve personal privacy. Even though the survey participants do not reveal any of their ratings, their survey records are potentially identifiable by using information from other public sources. None of the existing anonymisation principles (e.g., k-anonymity, l-diversity, etc.) can effectively prevent such breaches in large survey rating data sets. We tackle the problem by defining a principle called (k,e){(k,\epsilon)}-anonymity model to protect privacy. Intuitively, the principle requires that, for each transaction t in the given survey rating data T, at least (k − 1) other transactions in T must have ratings similar to t, where the similarity is controlled by e{\epsilon} . The (k,e){(k,\epsilon)} -anonymity model is formulated by its graphical representation and a specific graph-anonymisation problem is studied by adopting graph modification with graph theory. Various cases are analyzed and methods are developed to make the updated graph meet (k,e){(k,\epsilon)} requirements. The methods are applied to two real-life data sets to demonstrate their efficiency and practical utility.     

Community-preserving anonymization of graphs

In this paper, we propose a novel edge modification technique that better preserves the communities of a graph while anonymizing it. By maintaining the core number sequence of a graph, its coreness, we retain most of the information contained in the network while allowing changes in the degree sequence, i. e. obfuscating the visible data an attacker has access to. We reach a better trade-off between data privacy and data utility than with existing methods by capitalizing on the slack between apparent degree (node degree) and true degree (node core number). Our extensive experiments on six diverse standard network datasets support this claim. Our framework compares our method to other that are used as proxies for privacy protection in the relevant literature. We demonstrate that our method leads to higher data utility preservation, especially in clustering, for the same levels of randomization and k-anonymity.     

Privacy-preserving graph publishing with disentangled variational information bottleneck

Social networks collect enormous amounts of user personal and behavioral data, which could threaten users' privacy if published or shared directly. Privacy-preserving graph publishing (PPGP) can make user data available while protecting private information. For this purpose, in PPGP, anonymization methods like perturbation and generalization are commonly used. However, traditional anonymization methods are challenging in balancing high-level privacy and utility, ineffective at defending against both various link and hybrid inference attacks, as well as vulnerable to graph neural network (GNN)-based attacks. To solve those problems, we present a novel privacy-disentangled approach that disentangles private and non-private information for a better privacy-utility trade-off. Moreover, we propose a unified graph deep learning framework for PPGP, denoted privacy-disentangled variational information bottleneck (PDVIB). Using low-dimensional perturbations, the model generates an anonymized graph to defend against various inference attacks, including GNN-based attacks. Particularly, the model fits various privacy settings by employing adjustable perturbations at the node level. With three real-world datasets, PDVIB is demonstrated to generate robust anonymous graphs that defend against various privacy inference attacks while maintaining the utility of non-private information.     

An Efficient Framework for Multiple Subgraph Pattern Matching Models

With the popularity of storing large data graph in cloud, the emergence of subgraph pattern matching on a remote cloud has been inspired. Typically, subgraph pattern matching is defined in terms of subgraph isomorphism, which is an NP-complete problem and sometimes too strict to find useful matches in certain applications. And how to protect the privacy of data graphs in subgraph pattern matching without undermining matching results is an important concern. Thus, we propose a novel framework to achieve the privacy-preserving subgraph pattern matching in cloud. In order to protect the structural privacy in data graphs, we firstly develop a k-automorphism model based method. Additionally, we use a cost-model based label generalization method to protect label privacy in both data graphs and pattern graphs. During the generation of the k-automorphic graph, a large number of noise edges or vertices might be introduced to the original data graph. Thus, we use the outsourced graph, which is only a subset of a k-automorphic graph, to answer the subgraph pattern matching. The efficiency of the pattern matching process can be greatly improved in this way. Extensive experiments on real-world datasets demonstrate the high efficiency of our framework.

     

应用预测链接的分布式社会网络隐私保护方法

针对单机工作站环境下处理大规模动态社会网络图时执行效率低,以及动态社会网络发布中数据可用性较差的问题,提出基于预测链接的分布式动态社会网络隐私保护方法D-DSNBLP。该方法通过Pregel-like消息迭代更新模型,实现匿名大规模图数据的并行处理。首先通过快速迭代完成结点分组;其次根据各个组内的结点属性值并行构建候选结点集合;最后通过构建互斥边集合添加边,实现结点的隐私保护。实验表明,D-DSNBLP方法提高了大规模动态社会网络发布的效率,保证了匿名图的数据可用性。