基于GraphX的传球网络构建及分析研究

虽然大数据技术在社交网络、金融、公共安全、医疗卫生等领域的应用不断成熟,但在竞技体育方面的应用还处于探索阶段.常规篮球统计中缺乏对传球数据的记录,更缺乏对传球数据的统计分析、价值挖掘及应用等方面的研究.1)由于传球数据汇聚形态为图,在传球数据获取、数据清洗及格式转化、Vertex与Edge表构建的基础上,通过GraphX构建传球网络图为其应用打下基础;2)提出PlayerRank值区分球员重要度、球员位置个性化图顶点等方法提高传球网络可视化质量;3)通过GraphX构建的传球网络分析传球数量与质量对比赛结果的影响,并例举了传球网络在球队传球数据分析、战术人员选择、临场战术制定、网络子图及游戏体验改进等方面的应用.

基于GraphX传球网络的传球质量量化研究

虽然大数据技术在不断成熟,但它在竞技体育领域的相关应用研究还处于探索阶段。常规篮球统计缺乏对传球数据的记录,更缺乏对传球数据的统计分析、价值挖掘及应用等方面的研究。首先,在GraphX基础上将传球数据构建成图,为传球质量的研究奠定基础;其次,提出传球质量评估方法PESV(Pass Expectation Score Value),相比于传统的助攻数与失误数的比值ATR(Assist Turnover Ratio),PESV能更全面地评价球员传球的质量;最后,介绍基于传球网络及传球质量评估方法 PESV的几种应用场景,包括传球质量对比赛结果的影响分析、基于PESV值的传球路线选择,并以华人球员林书豪为例,计算其2015-2016赛季的传球得分期望值。

一种Spark GraphX框架下的关键词抽取方法

TextRank算法根据文本词语的位置关系构造图,应用图排序的算法计算出词语的权重,在计算过程中需要进行大量的迭代运算,在数据规模较大的时候,计算时间尤为可观.针对此问题,提出了一种基于Spark GraphX的关键词抽取方法,利用Spark GarpX所提供的分布式计算的图框架,将文本图数据分布式存储在不同的节点上,高效地实现了文本关键词的抽取.实验表明,本文中提出的基于Spark GraphX的关键词抽取方法,不仅计算时间短,抽取的关键词与人工标注的结果非常接近,具有一定的合理性.

Spark框架的Graphx算法研究

随着搜索引擎对网页的排名的需要,以及社交网络的兴起,海量关系所产生的大数据需要得到处理。图计算在数据关系的分析上发挥着其巨大的潜能。Spark框架是Hadoop大数据平台上整合能力强,处理速度快的内存模型框架,它的图处理Graphx也得到快速发展。该文先介绍Spark框架与Graphx的关系与发展。接着分析了Graphx中的三个典型的算法。最后总结了Graphx的场景应用。

基于Spark GraphX的异构网络社区检测

大多数社区检测任务仅适用于小型数据集,未能考虑大数据的快速并行处理。文中提出并改进了一种基于Spark GraphX的异构网络社区检测方法,解决了大型网络数据的并行性问题。其次,改进和优化了用于异构网络中社区检测的RankClus算法,将改进后的基于Spark GraphX的算法进行并行优化。最后给出了并行算法的实验结果,比较了不同的实验结果,证明了该方法的有效性和适用性。

KDSG-DBSCAN:一种基于K-D Tree和Spark GraphX的高性能DBSCAN算法

DBSCAN是一种基于密度的聚类算法,其能从包含噪声点的数据集中发现任意形状的聚类并且无需预先设定聚类个数,因此得到了广泛应用。但随着数据规模的增大,迭代式的点间距离计算导致经典单机串行DBSCAN算法的性能显著下降,使之无法满足实际应用的效率需求。为此,该文提出一种性能改进的分布式并行聚类算法——KDSG-DBSCAN。该算法利用K-D Tree邻域查询减少点间距离计算次数,利用图连通算法优化局部类簇合并过程,并基于Apache Spark MapReduce平台实现了计算过程的并行化。通过4组对比实验,分析了KDSGDBSCAN、经典DBSCAN与未使用图连通的KDS-DBSCAN算法的执行效率、KDSG-DBSCAN各子阶段执行时间占比、不同数据规模下KDSG-DBSCAN的扩展性以及不同计算节点数量和CPU核数下KDSG-DBSCAN的扩展性。结果表明,KDSG-DBSCAN算法具有良好的可扩展性和加速比。

基于Spark GraphX和社交网络大数据的用户影响力分析

利用社交网络大数据进行用户影响力分析,有助于识别网络环境中影响力强的用户实现其社会和商业价值。传统方法无法高效处理海量社交网络数据,定量准确地分析用户影响力,为解决该问题,提出一种基于PageRank算法的改进的用户影响力评价模型。综合考虑了用户连接程度和活跃程度,并以支持大规模并行图计算的Spark Graph X为工具,快速高效地实现了微博用户影响力的定量分析与评价。实验结果表明,所提方法效率更高,得到的用户影响力结果更接近真实情况。

基于GraphX的分布式幂迭代聚类

为解决幂迭代聚类算法并行实现中存在的编程繁琐、效率低下等问题,基于Spark大规模数据通用计算引擎及其Graph X组件,提出了一种在分布式环境下实现幂迭代聚类的方法。首先,利用某种相似性度量方法,将原始数据转换成一个可以视为图的亲和矩阵;然后,通过顶点切割,把行归一化后的亲和矩阵切分成若干个小图,分别存储在不同的机器上;最后,利用Spark基于内存计算的特点,对存储在集群中的图进行多次迭代计算,得到这个图的一个切割,图的每一个划分子图对应一个类簇。在不同规模的数据集和不同executor个数下进行的实验结果表明,基于Graph X的分布式幂迭代聚类算法具有良好的可扩展性,算法运行时间与executor个数呈负相关的线性关系,在6个executor下,与单个executor相比,算法的加速比达到了2.09到3.77。同时,通过与基于Hadoop的幂迭代聚类进行对比,在新闻数量为40 000篇时,运行时间降低了61%。

Spark的图计算框架:GraphX

Spark是UC Berkeley AMP Lab所开源的类Hadoop MapReduce的通用并行框架,是专为大规模数据处理而设计的快速通用的计算引擎,在如今的大数据环境下,Spark所发挥的作用正越来越大。介绍Spark的图计算框架GraphX。

一种有效的基于GraphX的分布式结构化图聚类算法

结构化图聚类是大图数据分析的主要技术之一,在社区检测、生物功能发现和图可视化等许多实际应用中具有重要意义。目前的分布式结构化图聚类算法大多基于Hadoop的MapReduce框架,但该框架需要精确计算图中所有邻接顶点之间的相似性且需要大量的磁盘I/O开销,极大增加了算法的运行时间。针对以上问题,主要工作和贡献点如下:(1)提出两个削减规则,第一个削减规则用来减少邻接顶点之间相似性计算次数,第二个削减规则通过非精确计算邻接顶点间的相似性来减少计算时间。(2)提出一种基于Spark中GraphX的结构化图聚类算法GXDSGC,该算法在运行期间不需要大量的磁盘I/O开销。(3)通过在大量真实数据集和合成数据集上的实验,证实提出的GXDSGC算法的有效性。GXDSGC算法比基于Hadoop中MapReduce框架的算法快30多倍,能够显著提高结构化图聚类在大图数据分析中的效率。

基于GraphX的社交网络用户推荐算法研究

针对PageRank等传统算法在分析大规模分布式集群数据过程中存在耗时长、推荐不精准等问题,提出一种基于GraphX的社交网络用户推荐算法,以期提升用户体验。综合搜索引擎中的相互超链接计算技术,采用PageRank算法和GraphX组件中的Triangle Counting算法等建立评估模型,并利用该模型用户间的活跃度和网络关联度等关键参数来获取用户好友推荐表。通过Sougou数据对模型进行验证,并与单一的PageRank算法模型进行对比分析,结果表明:算法评估模型运行速度和推荐率有显著提升,推荐用户好友更接近真实情况。

Spark GraphX上的SPARQL查询处理算法

资源描述框架(resource description framework,RDF)由于其表示的灵活性和天然的图数据模型而变得越来越流行。与此同时,RDF数据的数据量也在以惊人的速度增长。由于数据量的增长,在单机上存储和查询RDF数据变得越来越不方便,从而激发了分布式存储查询的需求。学术界在分布式存储查询系统,例如Hadoop、Spark上已经做了大量的工作。基于Hadoop的分布式存储查询方式的主要缺点是中间结果需要被写回磁盘,从而产生大量的I/O操作。提出了一种新的在Spark Graph X上进行SPARQL查询评估的方法SQX,将RDF数据视为一个带标签的属性图,提出了一种新的查询计划生成方案并且通过图并行的方式实现SPARQL查询评估。SQX采用了一种"查询树匹配"+"结果过滤"的方法。针对每一个SPARQL查询,产生相应的查询树和约束条件。在每一轮的超级步中,查询树中的多条边可以被并行处理,对迭代执行完毕后的结果进行过滤,满足约束条件的将作为最终的结果。实验结果表明,算法能够有效处理SPARQL查询并且具有良好的可扩展性。

基于Spark/GraphX图聚类算法的入室盗窃串并案研究

随着我国城镇化进程的不断加速,广泛的人口流动使社会治安环境日趋复杂,犯罪分子系列性作案居高不下,给人民的生命财产安全构成极大的威胁。针对刑事犯罪活动中日益突出的系列入室盗窃案件,提出采用图聚类算法来进行串并案分析。首先利用Spark/Graph X分布式图计算框架,通过提取入室盗窃案的案件特征,计算两两案件之间的相似度,构建案件相似度矩阵;然后依据图论理论,采用图聚类算法实现串并案分析模型。实战工作表明该模型可为侦破案件提供有效的串并线索,极大地减少人工作业,提高了侦查工作的效率。

GraphX图模型智能软件死码发现机制

本文在对GraphX图处理技术进行系统研究的基础上,提出了一种软件死码发现机制。运行软件源代码,生成函数调用关系,利用本文机制发现在程序操作过程中永远不可能被执行到的代码,即软件死码。利用CodeViz对100个左右的源代码文件进行筛选需要1个多小时的运算时间。而使用本文机制有效提高了死码的发现效率,可以将运算效率提升数倍。

基于SPARK GraphX的YELP社区发现研究

本文重点研究了复杂网络中的社区发现问题,并采用Spark GraphX对YELP数据集进行社区发现实现及可视化。YELP社交网络属于复杂网络中的无标度网络结构,其特征是网络中的大部分节点只和很少节点连接,其社区结构的发现对于后续研究其社交网络中信息传播具有一定的实际意义。

基于分布式图计算的台区负荷预测技术研究

随着智能电网数据采集技术的发展,电网公司积累的海量数据为台区负荷预测提供了数据基础。该文重点研究基于Apache Spark计算框架的台区短期负荷预测技术。首先,建立了包含温度、湿度、日类型等因素及负荷时间序列的动态贝叶斯网络,作为台区负荷预测模型。其次,为解决基于海量数据的模型参数计算及大规模配变负荷预测的并行化问题,搭建了基于Spark GraphX并行图计算组件的分布式计算平台,利用GraphX的Vertex Cut和并行边检索快速计算概率矩阵,以Pregel计算模型并行处理前向-后向算法,实现预测方法的分布式集群计算,保证全局预测任务的并行化。最后,通过实验结果表明,基于分布式图计算的台区负荷预测技术具有较高的预测精度和较快的计算速度,是一种高效可行的电力大数据分析技术。

PLRD-(k,m):保护链接关系的分布式k-度-m-标签匿名方法

现有的匿名技术多关注匿名后数据的可用性,忽略了攻击者可以通过多种背景知识进行攻击的问题。此外,随着用户规模的逐年递增,传统的匿名技术已不能满足实际需求。为此,提出一种保护链接关系的分布式匿名方法PLRD-(k,m)(distributed k-degree-m-label anonymity with protecting link relationships)。该方法利用GraphX的消息传递机制,通过将互为N-hop邻居的节点分为一组并进行k-degree匿名和m-标签匿名,保证攻击者无法通过度和标签识别出目标并保护链接关系不被泄露。最后,扩展了PLRD-(k,m)方法,提出一种个性化匿名方法以满足用户不同的需求。基于真实社会网络数据集的实验结果表明,提出的方法不仅能提高处理大规模社会网络的执行效率,同时具有很好的数据可用性。

大规模社会网络K-出入度匿名方法

现有社会网络隐私保护技术在处理大规模社会网络有向图时数据处理效率较低,且匿名数据发布通常不能满足社区结构分析的需求。为此,提出一种基于层次社区结构的大规模社会网络K-出入度匿名(KIODA)算法。该算法基于层次社区结构划分社区,采用贪心算法分组并匿名K-出入度序列,分布式并行添加虚拟节点以实现K-出入度匿名,基于GraphX图数据处理平台传递节点间的信息,根据层次社区熵的变化情况选择虚拟节点对并进行合并删除,从而减少信息损失。实验结果表明,KIODA算法在处理大规模社会网络有向图数据时具有较高的执行效率,并在匿名后保证了数据发布时社区结构分析结果的可用性。

保护社区结构的社会网络匿名技术

针对当前社会网络隐私保护方法存在社区结构破坏严重、单工作站处理数据能力低等不足,提出一种保护社区结构的社会网络度匿名SNDA-PCS(social network degree anonymity for protecting community structure)方法。社会网络社区发现使用分裂聚集算法,由聚合向量构造的压缩二叉树分组匿名度序列,添加虚拟顶点构造匿名图,根据顶点所属社区设计虚拟顶点删除-添加算法以提高发布图数据可用性。SNDA-PCS算法基于大规模并行图处理系统GraphX实现,实验结果表明,SNDA-PCS算法在满足匿名要求的同时保证了社区结构的可用性。

关联影响力传播最大化方法

社会网络中影响力传播最大化是社会网络分析领域所关注的重要问题。针对多个影响力同时进行传播,且影响力间存在传播促进的情况,提出关联影响力传播最大化问题。首先,对经典线性阈值模型进行扩展,提出关联影响力线性阈值模型对关联影响力传播过程进行建模;其次,定义了关联影响力传播最大化问题,证明了该问题是NP-hard的,以及问题目标函数满足子模性;再次,针对该问题提出基于结点激活贡献估计的求解算法;然后,利用结点激活贡献估计存在相互独立性,进一步提出了并行化求解算法,并在Spark GraphX并行图计算框架上实现了该算法;最后,在真实的社会网络数据集上,通过实验测试验证了所提出方法的有效性。