社交网络作为一个新兴事物正被越来越多的人所接受,其发展到今天已经与我们的生活息息相关。过去几年里,人们只是把“社交化”加在媒体、游戏等前面进行大肆宣传,所以现在我们需要真正了解它的意义,并考虑把它应用到未来商业及媒体领域中另外,社交网络正影响着人们的行为方式,没有什么比影响人们决策以及最终行为方式更重要的事情了。所以,面对海量的社交网络数据,对数据所形成的用户规律进行挖掘聚类,井理解消费者、更好地满足消费者具有重要的现实意义。从计算机科学的角度来说,社交网络是一张图,其中结点是网络中的个人或参与者,边是参与者之间的关系。所以,对社交网络的聚类问题使转化为对图的聚类问题。目前有很多图聚类技术,如图分割技术PageRank Clustering,图重叠聚类技术CPM等。但是,上述算法无论图中结点是否有用,均对整个图的所有结点进行聚类，导致较大的资源消耗。在现实中,某些应用如社交网络中的个别弱结点,对整个社交网络的分析影响并不大,可以视为无用。社交网络仅需要那些强连接,也就是说,我们只需对社交网络的聚类结果进行概率保证即可。所以,对整个图进行聚类的算法,其效率相对低卜。相反,返回图中最紧密聚类的算法,则相对更加快捷和实用。对聚类问题的改进本质上是对速度和精度进行权衡。2010年国际超大型数据库会议中,Kathy Macropol教授提出了将位置敏感哈希算法(LSH)应用于图聚类技术的TopGC算法。TopGC能够针对大型数据集进行聚类运算,具有良好的可扩展性。本文改进TopGC图聚类技术,提出概率化的图聚类算法PGC,它能够对大型有向/无向未加权图进行快速地聚类。该算法基于概率与推断技术,对于其他算法受内存限制而不能聚类的大型实际社交网络图数据,PGC可以较好地完成聚类。与TopGC相比,PGC返回的每个聚类中结点个数总是多于TopGC,且得分与TopGC基本相等。PGC通过比较图中各结点邻居集的相似度来实现聚类。为了实现可扩展性,PGC首先将社交网络图的邻按矩阵采用改进后Minhash算法进行降维,得到图的签名矩阵;然后利用位置LSH来进行哈希比较,将每个结点根据其邻居集哈希至相应的哈希桶;最后利用统计推断验证技术,对每个哈希桶中的结点进行校验,修剪掉相应的孤立点和噪声。全文共分为5章。第1章为绪论,介绍了本文研究的背景、意义等内容;第2章为基本介绍和知识准备;第3章阐述了PGC的详细步骤,本文针对TopGC技术做了两处修改,一是改进了常规的Minhash算法,二是提出了使用贝叶斯统计推断的方式进行概率验证;第4章通过实验验证并分析了PGC各参数变化时间对聚类结果的影响,并证明了PGC的正确性,可扩展性和鲁棒性;第5章为总结展望。总之,对于大型真实的社交网络图进行聚类,PGC是一个有效的解决方案。