《社交关系网络图数据挖掘论文-精品文档 (2).docx》由会员分享，可在线阅读，更多相关《社交关系网络图数据挖掘论文-精品文档 (2).docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、社交关系网络图数据挖掘论文1相关工作1.1分布式框架下的图计算工具1.1.1Pregel为了解决MapReduce在一些机器学习算法中性能瓶颈问题，Google针对大规模图运算提出了Pregel框架，它是严格的BSPbulksynchronousparallel模型BSP模型，即“大块同步模型，其概念由哈fo大学的Valiant和牛津大学的BillMcColl提出，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步，采用“计算-通信-同步形式面向顶点的迭代方式完成机器学习的数据同步，这种灵敏的面向顶点的方法和高效的容错机制的设计形式能够描绘一系列的算法，并在有上千台的计
2、算节点的集群中得以实现。在集群环境中，从远程机器上读取数据难以避免地会有延迟，Pregel选择了一种纯消息传递的形式，通过异步和批量的方式传递消息，通过分享内存的方式，有效地缓解了远程读取数据的延迟，提升了集群的性能，并且Pregel应用一组抽象的API隐藏了分布式编程的相关细节，展现给使用者一个易编程和易使用的大型图算法处理计算框架。但是Google一直没有将Pregel的详细实现开源，外界对Pregel的模拟实如今性能和稳定性方面都未能到达工业级应用的标准。同时，在图计算中，由于图的顶点、边密度的不平衡性的特点，带来BSP模型的“木桶效应木桶效应是由美国管理学家彼得提出的，本文指的是先完成
3、的任务需要等待后完成的任务，处理速度最慢的任务将成为整个系统的效率制约瓶颈的限制，网络、计算机硬件中的差异性也会使这种现象愈加明显。1.1.2SparkSpark是UCBerkeleyAMP实验室开发的通用的并行计算框架，是Pregel的优化模型，它是基于MapReduce算法实现的分布式计算框架。Spark拥有MapReduce所具有的优点，但不同于MapReduce的是，Spark采用了一种弹性分布式数据集resilientdistributeddataset，RDD的抽象数据构造，Spark是一个基于内存计算的开源的集群计算系统。RDD是一个具有容错机制的特殊集合，它提供了一种抽象的数据
4、架构，使用RDD逻辑转换而来的可重复使用的分享内存，而不再需要反复读写HDFS，解决了MapReduce框架在迭代计算式中要进行大量磁盘I/O操作的问题，这让数据分析愈加快速，为构建低延迟的并行性大数据分析处理框架提供了稳定的基础。同时，Spark提供了REPLread-eval-printloop的交互式查询以及函数式编程，支持围绕RDD抽象的API，同时包括一套transformation转化和action动作操作以及针对大量流行编程语言的支持，比方Scala、Java和Python。在图计算方面，Spark原生的Bagel以及Graphx提供了对于图操作的API，为大规模的图计算提供了低
5、延迟，负责优化交互式的大规模并行处理框架，但是Spark的磁盘索引是简单的静态机制，无法随着迭代状态的变化而动态优化。1.1.3GraphlabGraphlab是CMU的Select实验室提出的基于内存分享机制且面向机器学习的流处理并行框架，它的分布式处理是基于MPImessagepassinginterface，消息传递接口实现的，并且将数据抽象成图构造，它是以图的顶点为计算单元的大规模图处理系统，支持稀疏的计算依靠异步迭代计算等，解决了MapReduce不适应需要频繁数据交换的迭代机器学习算法问题，是继Google的Pregel之后的第一个开源的大规模图处理系统。Graphlab的核心思想
6、是“以图顶点的方式考虑问题，以最小化集群计算节点之间的通信量和平衡计算节点上的计算和存储资源为原则，对图的顶点进行切分。类似于MapReduce中的map和reduce经过，它将机器学习抽象成GASgather收集、apply运算、scatter更新3个步骤，然后按该抽象模型设计顶点程序实现算法。在gather阶段，当前点收集邻接点和边的值，结合本身的值，进行简单的用户定义的sum求和操作；在apply阶段，当前点根据sum得到的值及其前一时刻本身的值计算新的点值；scatter阶段当前点利用本人的新值，结合邻接点/边前一时刻的值来计算邻接边的新值，并更新邻接边。GraphLab的算法被应用于
7、很多推荐系统，也包括银行的欺诈侦测和电脑网络中的入侵侦测等领域。1.1.4PowerGraphPowerGraph是卡内基梅隆大学设计的一种强大的图计算分布式并行框架，它结合了Graphlab和Pregel关于图计算的优点，有效改善了Pregel和Graphlab等框架的并行化受限于顶点的邻居个数的问题。现实世界中的图，都是典型的Power-Law幂律分布图，其中少部分顶点连接到图中大部分的顶点上，这种图的划分对于并行的分布式框架来讲是一个非常大的难题，并且图的划分效率直接影响系统的通信开销。一般的并行框架采用的是散列随机分配方案，但这种方案没有考虑局部性，划分完成后各任务负责的子图之间的强耦
8、合性导致后续的迭代计算经过产生大量的消息通信，严重影响负载平衡。PowerGraph使用了支持同步处理和异步处理机制的GAS模型，并且提出了一种P-路顶点切割分区方案，在减少计算中通信量的同时保证了负载平衡，很好地解决了图的Power-Law问题。1.2单机图计算工具Graphchi除了以上介绍的分布式图计算框架外，还能够使用单机的图算法库，如BGL、LEAD、NetworkX、JDSL、StandfordGraphBase、FGL等进行图的挖掘和计算，但这种单机的方式由于内存限制的原因，对图本身的规模有了很大的限制2。为解决单机图计算的内存瓶颈问题，卡内基梅隆大学的Select实验室开发了G
9、raphchi，它是Graphlab的一个分支，采用基于磁盘的以顶点为中心的计算模型，它能够在PC上进行大规模的类似于社会网络分析的图计算，而不需要分布式的集群和云服务，也不需要考虑内存的限制。1.2.1基于磁盘的计算要想利用单机而不利用集群来并行地进行大规模的图计算，首当其冲面临的是存储问题。庞大的图数据在内存中处理上百万条边需要几十或几百吉字节的DRAM，由于其价格昂贵，目前只对高端服务器有可用性，所以Graphchi将目光投向了价格低廉、容量大的磁盘作为其外部存储，用基于磁盘的计算模型减少内存的使用和随机存取问题。然而，怎样从磁盘上处理大规模的图数据是一个难题。为了处理这个问题，Grap
10、hchi采用了新颖的PSWparallelslidingwindow，并行式滑动窗口模型，从磁盘上处理大的图数据。1.2.2PSW模型Graphchi采用了PSW模型从磁盘处理大的图数据，不同于分布式框架通用的BSP模型，PSW模型能够异步处理存储在硬盘上的可扩展图数据，有效躲避了“木桶效应。PSW模型中，边的信息分区shard采用不相交子集顶点集被分为P个子集interval(i)的形式关联存储，这种存储方式将每个子集以滑动窗口的形式分别从硬盘装入内存。Graphchi分屡次取节点子集interval(i)，每次取1个，并且根据节点子集中的点信息构造子图进行计算。在第p次操作所需的子图数据载
11、入后，每个节点并行地执行用户定义的更新函数，并更新节点，节点子集更新后的块文件将被写入磁盘。图2表示PSW模型进行一次迭代的滑动窗口示意，顶点被分为4个不相交的子集，每个本人都关联一个分区，计算经过是构建一次子图顶点的子集。从内存的分区中读取顶点的入边，从每个滑动的分区中读取出边，每个分区的最顶端为当前的滑动窗口。1.2.3Graphchi基于PSW模型的改良为了支持Graphchi的可扩展性，Graphchi对PSW模型进行了改良，通过实现一个简化的、高效的I/O缓存树来支持图边的增加和删除，改良的PSW模型如图3所示。2Graphchi应用前景2.1分布式图计算局限性基于图的分布式框架通过
12、云平台的计算资源处理上百万条边的图数据有很高的效率，但是利用分布式集群进行图计算仍然面临较高的硬件和技术要求，对于那些没有分布式专业背景、没有足够的硬件资源的人来讲，仍然是个宏大的挑战。首先，使用分布式框架时，使用者面临怎样将强耦合性的图数据进行分割，部署到集群计算节点上的问题3。其次，图的分布式计算涉及复杂的处理经过，需要大量的迭代和数据通信，大多数分布式系统用到的是BSP模型，是一种同步计算模型，对于消息的处理容量有限，网络的延迟以及节点间的通信会造成“木桶效应。再次，分布式框架处理需要计算耗时的大规模图数据时，重复计算以及系统故障使效率大大降低，同时系统的容错性也是制约运算效率和稳定性的
13、关键瓶颈。最后，对于编程者来讲，调试和优化分布式算法有很大的难度。相对于复杂的分布式集群框架来讲，简单的单机进行大规模的图计算，能够躲避分布式框架的问题。使用者不需考虑强耦合性的图数据怎样分割放置到分布式的集群节点中，也不需管理和部署诸多的集群节点，并且能够减少分布式集群节点中的通信开销，躲避网络延迟、“木桶效应等问题。例如，企业假如想要在同一张图上计算多种任务个性化推荐、图的社团发现等，在不同的国家、不同的利益集团都要计算同一个任务的情况下，企业要想提高运算速度，就必需要增加集群节点，也就是讲要增加成本。但是，假如一台机器上能够处理一个这样的大任务，企业能够为每台机器分配一个任务，每台机器之
14、间无需相互通信，当增加机器数量时，吞吐量也随之增加，这样多种任务的处理将会变得非常简单、有效。仅仅需要一台机器就能够对大规模的图数据进行分析处理和挖掘，这能够大大简化分布式集群处理框架的复杂性，如图5所示。本文对单机处理图数据技术Graphchi的发展、应用场景以及性能进行了研究，并进行了试验。2.2单机Graphchi应用前景在图挖掘方面，Graphchi实现了PageRank、连通分支、社区发现等算法处理和分析现实世界中大规模的图数据；另外，应用在协同过滤算法的推荐系统中，Graphchi从纷繁复杂的信息中找出可向用户推荐的有价值的信息。不仅在图挖掘和协同过滤方面，Graphchi还提供了
15、通用的编程框架，支持使用者调用本人的算法对图进行分析和计算，这使得Graphchi使用起来愈加灵敏，也有愈加个性化的可用性。当前Graphchi中一些应用的算法设计还不尽完善，但是随着技术的发展以及应用的普及，Graphchi因其在图计算方面独特的模型，其单机运行的简便、高可用和可观的运行效率，将在大规模图计算方面表现出越来越广阔的应用前景。为了验证Graphchi在不同硬件环境下，不同数量级别社交网络图数据应用中的可行性和可用性，下文对不同数量级的数据在两种不同的环境进行了相应的测试，并且和其他分布式框架进行了比照。3Graphchi的可行性、可用性评估实验3.1测试环境Intel(R)Co
16、re(TM)2DuoCPUT66002.20GHz、RAM2GB、Ubuntu11.04。Dell服务器QEMUVirtualCPUVersion(cpu64-rhel6)6核CPU、4GB内存未特殊注明，本文中数据测试环境均为服务器环境、CentOS6.4。3.2数据集讲明本文采用的数据集来自斯坦福的Snap网站4以及Netflix网站。测试的数据集为Wiki、Twitter、Facebook、Friendster等流行的社交网站，数据集大小为40MB30GB。表1是对实验中使用到的测试数据集的讲明，其中V表示测试数据集的顶点数目，E表示测试数据集边的数目。3.3Graphchi测试结果图6
17、表示的是PageRank和CommunityDetection两种算法对除Netflix数据集外所有数据集进行的测试，X轴表示边集的数量，Y轴表示对应的运行时间。从图中能够看出，对于两种不同算法，随着数据集的增大，运行时间大体呈线性增长。图7表示PageRank和CommunityDetection两种算法以及CommunityDetection分别在4次和10次迭代经过中，吞吐量随边数的变化。X轴为边集的数量，Y轴表示吞吐量系统每秒处理边的数量。Graphchi每秒能够处理的边的数量为0.21062106个。Graphchi测试Twitter2010年所有的user-follower关系，1
18、4亿条边、4千万个顶点共20GB的数据，PageRank算法需要46min，CommunityDetection算法10次迭代需要70min，Trianglecounting算法需要130min；测试在线游戏Friendster，18亿个顶点、6千万条边共30GB的数据集com-friendster.ungraph，PageRank算法4次迭代需要54min。可见，Graphchi能够在1h左右完成对社交网络一年数据的分析。这种处理能力完全能够知足使用者对大规模图数据进行计算的需求，并且具有较好的吞吐量。图8表示的是Graphchi测试两种数据集smallNetflix和Netflix协同过滤
19、的7种算法进行6次迭代的运行时间。X轴表示7种协同过滤算法：SGD、ALS、RBM、SVD+、biasSGD、CCD+和PMF，Y轴对应的是各种算法的运行时间。Graphchi在协同过滤中的运行时间最长为450s，Netflix数据集的时间不超过300s。图9表示的是SGD算法运行50次迭代的运行时间以及RSMErootsquaremeanerror均方差的变化曲线。迭代20次时，算法的RSME已经趋于稳定，无限接近于0.92，而此时的运行时间约为350s。可见，Graphchi在协同过滤方面表现出良好的性能，能够在几百秒的时间内处理2GB规模的数据。图10表示的是PageRank、Commu
20、nityDetection和ConnectedComponents3种算法，wiki-Talk和com-orkut两种测试集分别在2核CPU和6核CPU上运行时间的比照。X轴表示运行时间，Y轴表示3种算法以及两种数据集。从图10中能够看出，在一样数据集上6核CPU的运行时间要比2核CPU运行时间快了近10倍。图11表示的是协同过滤的3种算法，Netflix测试集分别在2核CPU和6核CPU上运行时间的比照。X轴表示运行时间，Y轴表示协同过滤4种不同算法。Netflix数据集在6核CPU上的运行时间比在2核CPU上的运行时间快了510倍。图11表示协同过滤4种算法在不同核数CPU运行时间的比照。
21、随着CPU数目的增加，运行速度也有明显的提升。相信在配置更高的单机上运行Graphchi将会有愈加可观的性能。3.4可行性、可用性分析比照本文比照了一些分布式的图处理框架，参考了一些其他文章的测试结果，见表2。在有50个节点、100个CPU的Spark框架下，在Twitter-2010数据集上运行5次迭代的PageRank算法的时间比Graphchi在4核CPU的环境中运行一样数据集快了大约5倍。在有1636个节点的Hadoop框架运行Twitter-2010数据集的PageRank算法迭代一次，Graphchi比Hadoop快45倍，比Powergraph慢了155倍。与运行在AMD服务器上
22、的Graphlab相比，用ALS算法测试Netflix数据集，Graphchi运行时间是Graphlab的2.5倍。Trianglecounting算法测试Twitter-2010数据集在1636个节点的Hadoop环境，Graphchi比Hadoop快了3倍。相对于Hadoop来讲，Graphchi的大规模图数据方面的性能远优于Hadoop；在协同过滤方面，Graphchi和Graphlab性能相差不大；与性能较好的Spark相比，Graphchi的性能表现也在能够接受的范围内；对于性能强大的Powergraph，Graphchi性能还是有一些差距。总体来讲，Graphchi以单机运行方式进
23、行图运算所表现出的性能能够和一些分布式的框架相媲美，固然不及性能强大的Powergraph，但是这样的性能表现已经能够知足一定规模的图运算了。这样的性能表现已足以为成本缺乏、硬件设备配置不高的中小企业或者个人提供高可行、高可用的社交关系网络图数据分析和挖掘平台。4Graphchi电信图数据挖掘应用为验证Graphchi对电信大规模图数据的处理能力，本文构造了电信通话清单数据约20GB，有4000万个顶点、14亿条边已对数据进行匿名处理，格式见表3。4.1PageRank算法挖掘核心人物PageRank算法是Google用于用来标识网页的等级/重要性的一种方法，是Google用来衡量一个网站好坏
24、的唯一标准。它基于马尔科夫状态转移理论，通过网页的链入数对网页进行投票来得出重要性排名。发展到目前，PageRank算法也被广泛用于关键人物挖掘等社交关系网络分析中。本文应用Graphchi的Pagerank算法，对电信关系网络数据进行Rank值的计算，进而找出关键人物。表4是采用Graphchi的Pagerank算法对电信数据集进行计算Rank值的排名前10的结果，在4000万个用户中，标号为1653的用户的重要性最高，为核心用户，应该对其重点挖掘和营销推广。4.2CommunityDetection算法进行社区发现CommunityDetection社区发现算法用于发现网络中的社区构造，可
25、以以看作是一种聚类算法。同一社区之间的节点与节点之间的关系比拟严密，而社区与社区之间的关系比拟稀疏。假如两者之间的联络越频繁，那么其社交关系就越严密。如图12所示，能够找到3个关系严密的社区。表5为采用Graphchi的CommunityDetection算法对电信数据集进行社团发现的结果，共发现社区1733613个，最大社区有35558616个用户。运营商能够对每一个社团分析其类似特征，进行潜在客户挖掘以及后续的客户关系维护。5结束语电信技术的发展带来了大规模的电信数据，面对日趋剧烈的市场竞争环境，电信运营商怎样从通信数据抽象成大规模的图网络数据中挖掘有价值的信息，维护客户关系，进行针对性服
26、务成了关注的焦点。本文阐述了能够对大规模电信社交网络图数据进行挖掘和计算的几种分布式框架和单机计算框架。并且通过实验和比照，讲明单机的Graphchi运行各算法在不同规模数据集所用的时间和其他能够运行这些算法的框架相比在合理的范围内，使用廉价的硬盘和普通的服务器就能够实现大规模的图计算，并且有良好的性能，它能够像其他分布式框架一样，在解决大规模社交关系网络图数据时有很好的运行效率。同时，Graphchi简单、高可用的性能使其在解决其他分布式系统能解决的大规模电信社交关系网络图数据方面也有很高的运行效率，其在一定规模的图数据量上的应用前景不可限量。但是，随着当前信息时代数量的不断扩增，对图数据处理的需求越来越高，Graphchi能否继续承载更高数据量的分析处理任务仍然是一个问号，本文也提到了并行分布式框架在超大规模的社交关系网络图数据挖掘中，表现出强大的处理能力和效率，相信并行处理将是超大规模社交关系网络图数据处理发展的必然趋势。