随着Internet的迅猛发展,Web的功能和多样性达到了前所未有的顶峰,Web上各种全新的理念和应用急剧增多,标志着Web2.0时代的到来。这些便捷和新潮的服务吸引着成千上万的用户加入并参与其中。传统的互联网逐渐发展成一类全新的网络社区——社区化网络(Social Network)。大量的用户积极地在网络上分享自己的个人信息,交换生活中的新闻,让社区化网络数据越来越丰富。而这些海量的网络数据又反过来使用户更加依赖社区化网络。对社区化网络数据的深入研究促成了其在商业上的广泛应用,许多全新的信息挖掘技术被提出并产生实际应用价值。然而随之而来的还有网络数据的隐私安全问题。由于传统的隐私保护技术无法直接应用于维度更高的社区化网络数据,网络数据的大范围公开又没有相应的隐私保护策略,这种矛盾让用户的个人信息受到严峻的威胁。因此,基于社区化网络数据的隐私保护逐渐成为了当前的研究热点。社区化网络中的隐私保护涉及到三个方面的问题:(1)如何定义社区化网络中的隐私;(2)如何建立数学模型量化敌手所拥有的背景知识;(3)如何描述社区化网络数据的使用场合及其用途。其中第三个问题是整个研究课题中最核心的问题,它限定了问题的实际背景,但同时前面两个问题的解决也会影响到第三个问题的完整性。本文在全面综述当前关于社区化网络中的隐私保护课题的主要工作的前提下,以网络图为社区化网络的描述模型,关注于社区化网络中图论算法的研究。本文总结了目前社区化网络隐私保护研究成果的最新进展,对各种不同的隐私模型、背景知识和数据用途作了系统的分类和介绍,同时为两种广泛应用的图论问题设计了有效的算法。为此,本文针对如下几个方面展开研究:1.研究了两种社区化网络中用户的隐私评分标准,并比较了在实际应用中的效果差异,为用户管理个人信息的隐私公开度提供指导和反馈。2.提出了从社区化网络数据中发现最大团的一种高效算法,该算法充分应用了社区化网络的幂法则。3.提出了对社区化网络进行社区发现的高效算法,该算法相较于原有基于最小割的算法效率更高性能更好。