大尺度在线社会网络结构研究

在线社会网络（OSN：Online Social Network）是由大规模（千万级以上）互联网用户及其相对稳定的联接关系构成的集合，目前已经成为人们日常交流的重要方式。此类网络在一定程度上，可以看作是现实社会关系（如共同兴趣者、家人及朋友等）在网络空间的一种映射，是物理世界在网络空间的重现。在线社会网络由早期的Email网络发展到现在，规模越来越庞大。在可预见的未来，在线社会网络会越来越多地影响人类的生活，改变物理世界中人类社会的组织结构，影响人类社会的发展进程。目前，在线社会网络已成为业界和学术界关注的热点。 在在线社会网络的研究中，主要分为三部分研究内容：（1）网络节点如何相互链接而构成在线社会网络的拓扑结构；（2）网络用户在这样的网络中发布消息的类型；（3）消息是如何在网络拓扑之上传播的。由于在线社会网络发展迅猛，用户规模庞大，因此，认识在线社会网络的结构，实时发现用户发布的消息类型，以及预测消息如何在网络拓扑上传播都成为计算机研究领域的挑战。然而，发现用户是如何链接而构成在线社会网络的拓扑机构成为认识在线社会网络，并进行其他研究的基础。 以MySql和Hadoop为基础建立一个海量数据爬取和存储系统，在大约3,000万用户数据的基础之上，通过数据分析和挖掘，从用户特征和网络拓扑特征入手，分析了新浪微博的系统特征，指出新浪微博是一个大尺度，自组织，小世界，不均衡，高动态的网络。新浪微博拥有超过3.5亿的用户，并且用户是通过自组织的方法来构建网络拓扑，因此新浪微博是一个大尺度自组织的网络。同时，测量结果显示用户之间的平均距离在6步左右，显示新浪微博是一个小世界网络。微博用户之间的关注关系变动频繁，用户每天改变2个左右的关注用户，而有些用户的粉丝数目每天变化在3,000左右，显示新浪微博是一个高动态的网络。新浪微博用户在地域/性别分布，粉丝/关注数目分布，相互关注率方面又显示出明显的不均衡特征。依据这些特征，提出把在线社会网络分为两种基本类型：信息驱动型在线社会网络和关系驱动型在线社会网络。结果明确显示新浪微博与Facebook等关系驱动型社会网络不同，同时，在互相关注率等特征方面，新浪微博和Twitter也有较大区别。 为了更深刻的理解新浪微博的拓扑结构，识别拓扑结构内部的社区，提出FriendFinder算法。该算法以社会网络中存在的三元闭包理论为基础，使用局部搜索和启发式算法，来识别网络中含有的社区结构。该算法首先利用最大度来寻找两个节点作为初始社区，分析社区的邻居节点集合，把合适的社区邻居节点加入已经存在的社区中，对于新形成的社区，迭代以上规则，直至社区不能再扩大为止，一个社区便形成了。和经典的社区划分算法相比，FriendFinder具有较好的时间复杂度，同时社区识别的准确度较高，并且该算法具有一定的可并行性，能够处理有向和无向网络，同时可以实现快速对网络拓扑结构的划分。在测试中，发现了新浪微博中存在的7个规模较大的社区，包含31,152用户。 在新浪微博的网络特征以及社区特征的基础之上，拟合新浪微博网络中用户的关注数目曲线，建立用户关注数目函数。根据新浪微博的特征，使用用户粉丝数目作为标准，把新浪微博网络分为核心网络和外围网络。在核心网络中，128.5万的用户吸引了全网36.71%的关注链接，同时核心用户的关注中57.68%指向核心网络内部。通过分析新浪微博的自组织规则，发现了新浪微博用户的链接机制，提出LinkProbability算法来计算用户的被选择概率，利用真实的新浪微博拓扑特征的参数和新浪微博中关注关系形成的机制，Group-Based演化模型可以用来描述新浪微博的拓扑结构以及演化特征。Group-Based演化模型借鉴经典的演化模型框架，在候选节点集合选择以及候选节点被选择的概率方面使用新浪微博中的用户链接机制，因此能更好的反映新浪微博的拓扑结构。 在全面理解和认识新浪微博的拓扑结构和其形成机制的基础之上，不考虑主观因素，仅以新浪微博的拓扑特征为基础，设计WeiRank算法用以量化新浪微博中用户的重要性。WeiRank算法模拟人类社会中存在的投票方法，使用迭代的方法来为每个节点的投票赋予不同的权重，计算每个用户被投票的次数和每次投票的权重来量化不同用户所具有的不同的网络影响力。和HITS以及PageRank等经典排序算法相比，WeiRank算法能更好的对社会网络中的用户进行影响力排序，并完成对新浪微博中粉丝数最多的前150万人进行排序。