基于差分隐私与博弈论的动态网络发布算法研究

摘要

信息网络（比如社交网络，电子邮件网络等）对于数据挖掘与分析来说具有非常高的价值，但是它们往往包含高度敏感的个人数据，比如社会联系和私人通信记录。为了保护网络中个体用户的隐私，这些网络数据在被发布给第三方机构用于公共访问和科学研究之前需要进行适当的隐私安全保护。
　　本文借助差分隐私保护模型来对网络图中的隐私信息进行处理。为了减少添加的差分隐私噪声量，本文使用层次随机图模型来表示网络图，对图中节点之间的连接概率添加噪声，而不是直接对边加噪。为了进一步控制噪声量，本文在建立层次随机图之前先在网络图中进行社区发现，向社区内部的节点连边添加较多的噪声，向社区之间的节点连边添加较少的噪声。
　　现实世界的网络通常是动态变化的，为了处理动态网络的隐私保护问题，本文在差分隐私与层次随机图的基础上，提出时间窗口划分与动态网络社区发现算法，每个时间窗口发布一份净化图。为了应对动态性带来的挑战，本文将每个时间窗口进一步划分为若干层次，通过分层抽样与过滤相似图的方式降低时间开销，减少累积误差，同时尽量保持该时间窗口的网络结构特征。
　　本文在真实数据集上对提出的算法执行检验。实验证明，本文所提算法发布的图在满足差分隐私保护模型的前提下，能很好地保留原始图的三个重要网络结构特征:节点度分布，最短路径长度分布，Top-K中心点覆盖率。

目录

声明

摘要

第1章 绪论

1．1 课题研究背景与意义

1．2 国内外研究现状

1．2．1 网络数据隐私保护

1．2．2 动态网络社区发现

1．3 本文主要工作与组织架构

第2章 相关背景与概念介绍

2．1 差分隐私模型

2．1．1 拉普拉斯机制

2．1．2 指数机制

2．1．3 组合性质

2．2 博弈论

2．3 层次随机图

2．3．1 定义与表示

2．3．2 评价指标

2．3．3 构建方法

2．4 社区发现

2．5 本章小结

第3章 结合差分隐私与博弈论的动态发布算法

3．1 原始的数据发布算法

3．1．1 基于层次随机图的数据发布算法

3．1．2 存在的问题

3．2 动态网络时间窗口划分方法

3．2．1 图相似度模型

3．2．2 时间窗口划分算法

3．3 博弈论与动态网络社区发现

3．3．1 算法出发点

3．3．2 动态网络博弈论模型

3．3．3 结合博弈论的动态社区发现算法

3．4 适用于动态网络的层次随机图发布算法

3．4．1 算法目标

3．4．2 层次随机图到三角矩阵的转换

3．4．3 适用于动态网络的发布算法

3．5 隐私分析

3．5．1 隐私预算分配

3．5．2 算法隐私分析

3．6 本章小结

第4章 实验设计与结果分析

4．1．2实验数据

4．1．3 实验方案

4．1．4 评价指标

4．2 结果分析

4．2．1 动态网络社区发现算法

4．2．2 动态网络层次随机图发布算法

4．3 本章小结

第5章 总结与展望

5．1 本文工作总结

5．2 未来工作展望

参考文献

攻读学位期间公开发表论文情况

致谢