在线社交网络为相关研究者提供了有价值的信息。越来越多的第三方应用利用社交网络来改进其功能,电子商务应用程序利用社交网络中的连接关系来提高销量,数据挖掘研究人员也依赖社交网络中的连接关系进行功能分析。然而,在社交网络数据发布时,容易暴露用户的隐私。连接关系与用户的社会身份有关,属于用户的敏感信息。此外,社交网络中存在一些节点与其它节点联系密切,称为关键节点。这些关键节点在社交网络中起到重要的作用。现有技术大多只保护了社交网络中连接的隐私,具有大量邻居的关键节点很容易暴露给攻击者。因此,攻击者可以轻易识别出关键节点,进而推出网络中真实连接存在的概率。另一方面,现有技术在保护网络隐私的同时较难兼顾网络数据的可用性,如传统随机扰动算法对网络结构的影响较大,导致扰动网络的可用性不高。基于随机游走的连接扰动算法在一定程度上提升了扰动网络的可用性,但依旧存在对网络结构特征影响较大的问题。为了解决上述问题,本文提出了一种基于关键节点与连接关系的社交网络隐私保护方法KLPP(Privacy Preserving for Social Networks Based on Key Nodes and Links),可以同时保护社交网络中关键节点和连接的隐私,且保留网络数据的可用性。通过随机度扰动算法,对网络中的关键节点施加更多保护,大幅度提升了网络数据的隐私性。另一方面,通过对节点进行聚类,将网络划分为子图,并在子图内部扰动网络中的连接,可以减少扰动过程对网络结构的影响。算法在保护网络数据隐私性的同时,兼顾了扰动网络的可用性,能够较好地保留网络结构特征。KLPP算法吸取了基于随机游走的连接扰动方法的优点,在解决传统随机扰动方法存在问题的同时,进一步提升了隐私保护效果和扰动网络的可用性。本文在实验部分首先提出了衡量可用性与隐私性的两个指标,接着使用实际社交网络与模型网络进行综合实验来评估扰动网络的可用性与隐私性。实验部分对输入参数的影响、网络结构特征保留效果、扰动网络数据的可用性与隐私性等方面进行了分析,研究了输入参数变化对KLPP算法性能的影响,并对KLPP算法与传统随机扰动、基于随机游走的连接扰动方法在扰动网络数据可用性、隐私保护效果等方面进行了分析对比。实验结果表明,KLPP算法能够解决基于随机游走的连接扰动方法存在的问题,同时获得更好的隐私保护效果,有效保留网络数据的可用性。