基于MapReduce模型的大规模社交网络高效分析算法研究

发布时间：2018-07-12 18:14

本文选题：在线社交网络 + MapReduce　；参考：《上海交通大学》2014年硕士论文

【摘要】：自从Web2.0的兴起，在线社交网络吸引了许多国内外研究者的兴趣。这些社交网络有许多独特的结构性质如度的幂律分布、极短的网络半径和较明显的社区聚集特性。这些结构方面独特的性质直接或间接影响着网络中的信息传播以及人与人之间的交流互动，对于研究人类社会的组织架构形式以及人际关系的演化方式有着极为重要的作用。目前主流的社交网络的用户数已达到上亿规模，而用户之间的关系则达到了几十亿甚至上百亿的数量级。传统的工具（如关系型数据库）以及传统的算法（基于单CPU的串行算法）已无法胜任。针对探索在线社交网络结构的问题，本文主要以新浪微博和Twitter为例，并参照对比了其他有向社交网络的测量结果，全面探究了在线社交网络的结构特征，包括度的分布、关系的相互性、聚集性、度的相关性、路径长度和社区等。其中，新浪微博的数据集是本文通过一个分布式爬虫，经过3个月的时间从其网站爬取的结果，包含了1.35亿个用户和104亿条关系。针对大规模在线社交网络数据的处理问题，本文提出了若干种基于MapReduce模型的社交网络分析算法。其中最基础最核心的是半并行广度优先搜索算法。该算法在运算量和I/O负载等性能方面都要远远优于业界公认的图的挖掘算法类库——Pegasus。本文给出了所提出算法的理论性能分析结果，，同时基于新浪微博的网络结构特征给出了经验性能分析结果和实测结果。
[Abstract]:Since the emergence of Web 2.0, online social networks have attracted the interest of many researchers at home and abroad. These social networks have many unique structural properties such as power law distribution of degree, very short radius of network and obvious community aggregation. The unique nature of these structures directly or indirectly affects the information dissemination and the interaction between people in the network, and plays an extremely important role in the study of the organizational structure of human society and the evolution of interpersonal relationships. The number of users of mainstream social networks has reached hundreds of millions, while the relationship between users has reached billions or even tens of billions of orders of magnitude. Traditional tools (such as relational databases) and traditional algorithms (single CPU based serial algorithms) have been incompetent. Aiming at the problem of exploring the network structure of online social networks, this paper mainly takes Sina Weibo and Twitter as examples, and compares the measurement results of other directed social networks, and probes into the structural characteristics of online social networks, including the distribution of degrees. Interactivity, agglomeration, correlation of degree, path length, community, etc. Among them, the data set of Sina Weibo is the result of a distributed crawler crawling from its website in three months. It contains 135 million users and 10.4 billion relationships. Aiming at the problem of data processing of large-scale online social networks, this paper presents several analysis algorithms of social networks based on MapReduce model. The most basic and core is the half parallel breadth-first search algorithm. The algorithm is much better than the class library of graph mining in terms of computation and I / O load. In this paper, the theoretical performance analysis results of the proposed algorithm are given, and the empirical performance analysis results and the measured results are given based on the network structure characteristics of Sina Weibo.
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.092

【共引文献】