张素智 孙嘉彬 王 威

基于节点聚集系数的分布式标签传播算法

张素智 孙嘉彬 王 威

(郑州轻工业学院计算机与通信工程学院 河南 郑州 450002)

随着互联网的发展和普及，越来越多的用户加入到社交网络，逐渐形成了大规模、多样化的社区。对于新浪微博等社交服务来说，这些社区的发现可以为用户和商家提供有价值的信息。在社区发现算法中，标签传播算法(LPA算法)具有算法思想简单、复杂度低、无需初始化社区数量等优点，但准确率较低，同时在大数据环境下，效率还不够高。将节点聚类系数引入LPA的标签更新过程中，提出一种结合MapReduce分布式计算框架的社区发现算法——DisLPA算法。实验表明，该算法不仅提高了准确率，同时有效改善了计算瓶颈问题。

社区发现 标签传播 聚集系数 MapReduce

0 引 言

近年来，随着Web2.0的逐渐兴起，社交网络(SNS)的使用变得越来越普遍，越来越多的人利用SNS扩展个人交际圈，同时发布、查找和共享信息，吸引更多的人去关注热点信息。新浪发布的2012年第三季度财报显示，截止到2012年12月底，新浪微博注册用户数已超5亿，平均每天活跃用户达到4620万。这些用户发布文字、图片、视频，转发微博，搜索信息，关注其他人等等都会产生大量的数据，这对数据分析带来了巨大的挑战，这个挑战[1]不仅是数据量膨胀的问题，而且涉及到数据深度分析需求的增长。

对SNS社区进行挖掘，可以发现网络社区中的潜在的社区结构，从而对用户角色进行评估，扩展社交圈，以实现高效准确的个性化推荐，同时能够提供精准的商业定位，为商家带来更大的商机。……