论文部分内容阅读
随着互联网的快速发展,更多的人加入到互联网中。作为当前最火的一种互联网应用,社交网站俘获了广大的用户。如新浪微博,其用户数量已突破3亿;国外知名社交网站twitter用户数量突破了5亿。由于社交网络吸引了如此大规模的用户数量,无论是管理者还是使用者都将面临一个问题:怎样找到与自己有着共同兴趣或联系紧密的人来互动,即传统意义上的社区。社区结构的研究对于理解和分析网络结构及功能有着非常重要的作用,已经广泛应用到生物学、社会学等各种领域。社区挖掘正是基于这种目的而产生的,许多研究人员从不同角度出发提出了各种社区挖掘算法,目前的社区挖掘算法大都是迭代算法,这些算法不能将网络用户关系分割成独立的部分,无法采用并行计算的编程方式,往往只能适用小规模的用户数量,当用户数量增大时,它们会因计算量的增大而导致计算时间大大增加。MapReduce作为一种并行编程模型,擅长处理大规模的数据和计算量。如果采用MapReduce编程模型将传统的社区挖掘算法并行化,能很好的利用集群的计算优势处理大用户量数据,缩短算法的执行时间。本文提出了一种基于MapReduce的社区挖掘算法,此算法对传统的基于标签传播的社区挖掘算法进行了改进,将该算法成功运用到MapReduce编程模型中,既保持了原有算法的时间复杂度,又适合并行计算,能够快速的从大型社交网站中并行高效的挖掘出高质量的社区,提高了大型网络社区挖掘的计算效率。本论文的主要工作及创新点有以下几方面:第一,通过新浪微博API获取实验数据集,经过处理后得到270多万用户关系数据;第二,结合标签传播算法中的同步更新过程和异步更新过程,改进基于标签传播的社区挖掘算法,并重新设计了数据结构,使算法能够MapReduce化,提出基于MapReduce的社区挖掘算法;第三,通过计算节点的全网聚集系数和社区聚集系数对结果进行质量分析,分析结果表明了基于MapReduce的社区挖掘算法的可行性和有效性;第四,采用MapReduce编程模型计算聚集系数,缩短了结果分析时间,提高了分析效率。