陶晓玉 宁 博 李冠宇

(大连海事大学信息科学技术学院 辽宁 大连 116026)

0 引 言

随着信息网络的发展，大量的网络数据产生，如社交网络、通信网络和商业贸易网络等。这些网络数据一般采用图来表示，图中的节点可能表示的是个体及其属性或是一个公司机构等，边用来表示节点间存在一定的关系，其中，一些图的边上还带有一定的权重值，这些权重值可能代表着公司之间的交易金额或是关系的亲密程度等。图中的这些顶点和边可能包含着大量敏感信息，例如：个人的身份证号码、电话号码、银行账户和交易金额等信息。一直以来，从图数据集中挖掘频繁子图是图数据分析的重要任务。挖掘频繁子图可以发现一些公共的子结构，从而为进一步的研究分析提供帮助。然而，当图数据集中包含着敏感信息，直接发布挖掘到的频繁子图将会导致个人隐私的泄露。因此需要对频繁子图的挖掘过程采取保护措施。本文主要针对有权网络图的频繁子图挖掘过程中的隐私保护进行研究。

近年来，针对隐私保护方面的研究，已有许多匿名方法被提出。其中，Dwork等[1-2]提出的差分隐私保护方法是基于数据失真的一种方法，对隐私泄露风险有严格定量化的定义和证明且极大地保证了数据的可用性。在此定义下，对数据库的计算处理结果对于具体某个记录的变化是不敏感的，单个记录在数据集中或者不在数据集中，都对计算结果的影响微乎其微。……