随着社交媒体的兴起,越来越多的用户选择将个性化的信息分享到社交网络服务,用户的个人信息也逐渐暴露在社交网络中,信息的公开化引起了人们对隐私保护的关注。因此,在数据发布之前需要对其进行处理,以达到对其进行隐私保护的目的。社交网络中的关系有很多是敏感信息,在发布社交网络时,应对用户之间的关系予以保护。如何有效保护社交网络中用户之间的连接隐私成为当前的研究热点。本文基于随机游走对社交网络的连接隐私进行保护,主要研究工作如下:1)本文研究了社交网络中用户与用户之间的连接隐私保护,将随机游走算法应用于加权社交网络中,提出了加权图上的随机游走连接隐私保护方案(WRW)。通过随机游走,随机选择假连接的目的节点,用假连接代替真连接,并为假连接提供了虚假的权重,在对用户与用户之间的关系进行了保护的同时,也能保持权重的分布变化不大。最后通过仿真实验,模拟链路预测攻击,对扰乱后的社交网络进行重构,结果证明该方案能够保护社交网络的连接隐私。从平均最短路径长度、度数分布、权重分布、边改变率等指标分析了扰乱后的社交网络图结构,证明了该方案在保护连接隐私的同时,保留了网络的结构特性,保持了网络可用性。2)在上述WRW算法的基础上,本文考虑了节点间的相似度,提出了改进的WRW算法。方案思想是将原始图中边的两端节点间的相似度排序,扰乱相似度高的连接。由于重点扰乱相似度高的连接,我们的方案可以更好的抵御链路预测攻击。同时方案并没有扰动所有的连接,因此可以更好的保持社交网络的可用性,如社交网络的最短路径、权重分布、度分布等。3)由于社交网络中的关系可能存在方向性,本文针对有向社交网络,提出了基于随机游走的有向网络的连接隐私保护方案。在扰乱连接时,考虑了连接的方向和节点的出度。在遍历社交网络中的节点时,只扰乱该节点的出边,同时添加一条虚假的出边。一方面,可以扰乱社交网络的连接,另一方面,可以保持节点的出度不变。最后实验表明,我们的方案能够保护有向社交网络的边隐私,同时可以保留社交网络的平均最短路径、出度分布等基本不变,可以保留图表更多的可用性。