张瑞　王三福

摘 要：文章结合GraphLab大数据框架应用技术最新的发展，全面分析研究了该技术在复杂网络研究中的具体应用。包括GraphLab并行框架并将其应用在复杂网络度计算、最短路径及聚集系数等计算方面，同时，还分析了处理该类型大数据时可能遭遇的问题。为搭建高效合理的复杂网络大数据处理计算提供了一种新思路，进而提升复杂网络研究的整体水平。

关键词：GraphLab；复杂网络；度计算；最短路径；聚集系数

全球互联网数据中心报告指出，2013年全球数据量为4.4ZB，2014年全球数据总量在6.2ZB左右，2015年全球数据总量在8.6ZB左右，2016年将在12ZB左右。在未来的几年时间内，全球数据流量将实现跨越式增长。到2020年，全球数据总量将增至40ZB。另外，大数据是由非结构化的数据与结构化数据构成的。其中，非结构化的占比最大，达到了85%。截至目前，非结构化数据的一般性特征、个体表现及其基本原理还未明朗化。为此，在后续研究过程中，应综合运用社会学、数学、管理科学等诸多学科进行探讨。复杂网络理论是以网络为研究对象的学科，是一种不同研究对象的统一抽象的表达方式，它迎合了目前大数据处理的机遇与挑战，开辟了一种新科学方法。

1 GraphLab大数据框架

大数据是这几年科技和应用领域炙手可热的话题，而GraphLab又是大数据非结构网络研究中最活跃的技术，该技术比较新，许多应用还处在探索阶段。利用该计算框架，我们写的程序可以充分利用大量资源，而不需要关心分布式系统的实现细节。GraphLab将数据抽象成Graph结构，将算法的执行过程抽象成Gather、Apply、Scatter三个步骤。其并行的核心思想是对顶点的切分，以下面的例子作为一个说明。如图1所示，首先，要求率先对V0邻接顶点实施求和计算，在串行实现中，依靠V0遍历其全部邻接点，紧接着实施累積求和。GraphLab先切分顶点V0，紧接着在两台处理器上分别部署V0的边关系及与之相对应的邻接点，同时实施部分求和运算，再由mirror顶点与master顶点的通信负责做好最终的计算工作。

图1 Graph对并行思想

边是机器学习算法中充分反映数据依赖性的重要形式，顶点是大数据中最小的通信粒度与并行粒度。当顶点设置于多台机器上时，应将其中一台机器视作master顶点，将剩下的所有机器视作mirror顶点。全部mirror顶点都需由Master负责管理，接收其下达的计算任务。而mirror是master顶点在各台机器中的代理实施者，因此要确保其数据和master数据的同步。在并行计算过程中，各个线程分摊进程中所有顶点的gather->apply->scatter操作。任何顶点在迭代过程中均需历经gather、apple、scatter这三个发展阶段，下面将对其展开具体地介绍。

1.1 Gather阶段

通过自身或者邻接顶点，工作顶点的边获取到相应数据，并做好gather_data_i的标注，然后由所有边的数据graphlab进行求和，用sum_data表示求和结果。在该阶段，所有的边与工作顶点均为只读的。

1.2 Apply阶段

Mirror向master顶点成功发送gather计算的结果sum_data后，由master负责归纳整理，结果用total表示。然后，Master结合业务的实际需求，在上一环节的顶点数据与total结果的基础上实施计算，针对master的顶点数据进行更新，并且同步mirror。这一发展阶段的边不支持修改，但工作顶点是可进行调整。

1.3 Scatter阶段

待工作顶点更新完毕后，应对边上的数据进行更新，并向与其关系较为密切的邻接顶点发布通知，使其更新状态。在该发展阶段，边上数据可写，工作顶点只读。

2 复杂网络理论

物理学家霍金说过“21世纪将是复杂性科学的世纪”。复杂网络（Complex Network），顾名思义，指的是具备小世界、自组织、无标度、吸引子、自相似中至少一种或全部性质的网络。最近几年时间以来，学界纷纷开始加大力度探究复杂网络，其中影响力最具影响力有两大具有开创意义的工作。其一，1998年，Strogatz与Watts合著的文章被刊登在Nature杂志中，该著作指出，小世界（Small-World）网络模型可用于阐释由完全规则网络逐步过渡到完全随机网络的过程，它具有平均路径长度小、聚类特性和规则网络相似的特征。其二，1999年，Albert与Barabasi发表了文章在Science上，其强调，大量复杂网络的连接度均呈幂律式分布。因幂律分布不存在显著的特征长度，因此该网络又叫无标度（Scale-Free）网络。随后，相关研究人员开始重视对复杂网络的特征的探究，其涉足的领域主要有计算机网络研究、图论、社会学、统计物理学、经济学以及生态学等，涉足的网络大致涵盖了蛋白质折叠网络、Internet/WWW网络、生命科学领域的网络、社会网络等。在研究过程中，主要采取物理学中的社会网络分析法、统计物理学法以及数学领域的图论。

截至如今，复杂网络的研究对象较之前有了进一步拓展，针对网络的演化动力学机制、形成机制、结构稳定性、网络中的模型性质以及网络发展的统计规律等问题均有涉猎。网络研究的基本测度主要有：度的相关性、最短距离及其分布特点、度及其分布特点、集聚程度及其分布特点、连通集团的规模分布以及介数及其分布特点。利用GraphLab大数据处理技术对上述复杂网络的计算研究起始于基本的三项内容，它们分别是度与度分布、平均路径长度和聚类系数。我们选取Facebook于2015年3月公开数据集，节点数18462135，链接数41963380。

3 GraphLab处理大数据注意问题

3.1成功的分析中绝大部分工作是数据预处理

数据是混乱的，在让数据产生价值之前，必须对数据进行清洗、处理、融合、挖掘和许多其他操作。特别是对大数据集，由于人们很难直接检查，为了知道需要哪些预处理步骤，甚至需采用计算方法。一般情况下，即使在模型调优阶段，在整个数据处理管道各个作业中，花在特征提取和选择上的时间比选择和实现算法的时间还要多。 比如，在构建Facebook社交数据网络模型时，数据科学家需要从许多可能的特征中进行选择。这些特征包括必填项个人、登录时间和转发点击等。在将特征转换成适用于机器学习算法的向量时，每个特征可能都会有不同的问题。系统需要支持更灵活的转换，远远不止是将二维双精度数组转换成一个数学模型那么简单。

3.2迭代与数据科学紧密相关

在利用GraphLab建模和分析经常需要对一个数据集进行多次遍历。这其中一方面是由机器学习算法和统计过程本身造成的。常用的优化过程，比如随机梯度下降 和最大似然估计，在收敛前都需要多次扫描输入数据。数据科学家自身的工作流程也涉及迭代。在初步调查和理解数据集时，一个查询的结果往往给下一个查询带来启示。在构建模型时，数据科学家往往很难在第一次就得到理想的结果。选择正确的特征，挑选合适的算法，运行恰当的显著性测试，找到合适的超参数，所有这些工作都需要反复试验。

3.3通过对大数据的研究，人类可知晓是何种数据，但无法知晓具体的原因

众所周知，在检测相关性方面，大数据的性能优越，甚至于可检测出小数据集不能测出的微小相关性，然而却无法告知研究人员，何种相关性的意义显著。举个例子，假定大数据分析结果显示，Facebook的数据与浏览时间在2015年1月至3月这一段时间内表现出极度相关性，且呈现出骤降的发展态势。然而，这一结果很难领研究人员信服。

3.4大数据可以辅助科学调查，但不可能成功地完全代替

比如，在利用Facebook数据的处理中想推导出潜在的网络数据演化模型，部分科学家已在试图通过大数据的方式使该问题得到妥善地处理。然而，不论是哪个科学家均无法纯粹地通过处理数据的方式达到目的，在实践过程中他们往往会综合利用数学理论与物理理论来对数据进行处理。

4 结束语

到目前为止，基于传统领域的计算方法对于复杂网络的研究越来越显示出局限性，其主要原因在于对目前大数据量的网络信息无法定量的加以研究。基于GraphLab大数据框架为复杂网络研究提供了一条新的思路，是研究者可以便利的开展复杂网络的计算研究。对网络图的搭建，以及演化机理的阐述，尝试从结构方面进行趋势的研究，从而引导复杂网络具体量化计算发展的趋势。

参考文献：

[1]赵刚.大数据：技术与应用实践指南[M] 北京：电子工业出版社，2013，20-163.

[2]李军.大数据：从海量到精准[M] 北京：清华大学出版社，2014，120-260.

[3]（美）卡劳.Spark快速大数据分析[M] 北京：人民邮电出版社，2015，20-150.

[4]何大韧，刘宗华，汪秉宏.复杂系统与复杂网络[M].北京：高等教育出版社，2009，143-202.

[5]郭雷，许晓鸣.复杂网络[M].上海：上海科技教育出版社，2006，128-132.

[6]（美）Tom White. Hadoop权威指南[M] 北京：清华大学出版社，2015，21-298.

[7]林敏.网络拓扑结构对自组织临界行为影响的研究[D].天津：南开大学，2005，1-30.

[8]韩定定.复杂网络的拓扑、动力学行为及其实证研究[D].上海：华东师范大學，2008，43-50.

（作者单位：1.兰州财经大学；2.天水师范学院）