论文部分内容阅读
自从Web2.0的兴起,在线社交网络吸引了许多国内外研究者的兴趣。这些社交网络有许多独特的结构性质如度的幂律分布、极短的网络半径和较明显的社区聚集特性。这些结构方面独特的性质直接或间接影响着网络中的信息传播以及人与人之间的交流互动,对于研究人类社会的组织架构形式以及人际关系的演化方式有着极为重要的作用。目前主流的社交网络的用户数已达到上亿规模,而用户之间的关系则达到了几十亿甚至上百亿的数量级。传统的工具(如关系型数据库)以及传统的算法(基于单CPU的串行算法)已无法胜任。针对探索在线社交网络结构的问题,本文主要以新浪微博和Twitter为例,并参照对比了其他有向社交网络的测量结果,全面探究了在线社交网络的结构特征,包括度的分布、关系的相互性、聚集性、度的相关性、路径长度和社区等。其中,新浪微博的数据集是本文通过一个分布式爬虫,经过3个月的时间从其网站爬取的结果,包含了1.35亿个用户和104亿条关系。针对大规模在线社交网络数据的处理问题,本文提出了若干种基于MapReduce模型的社交网络分析算法。其中最基础最核心的是半并行广度优先搜索算法。该算法在运算量和I/O负载等性能方面都要远远优于业界公认的图的挖掘算法类库——Pegasus。本文给出了所提出算法的理论性能分析结果,同时基于新浪微博的网络结构特征给出了经验性能分析结果和实测结果。