一种基于GN算法的动态图划分方法

随着图规模的急剧增长,对动态图进行实时处理的需求日益增加。大多现有的算法针对静态图划分是有效的,直接用其处理动态图会带来较大的通信开销。针对该问题,提出一种基于GN算法的动态图划分方法。首先收集一段时间内加入动态图中的顶点;然后,利用GN算法对这些新加入的顶点进行预划分,产生若干个内部联系紧密的社区;最后,将预划分产生的社区结果插入到已经划分好的当前图中。实验从交叉边数和负载均衡度两方面将该方法与传统流式划分方法进行比较,结果表明,在公开数据集上,该方法的交叉边数降低了13%,负载均衡度减少了42.3%。由此可见,该方法的划分质量明显优于传统的流式划分方法。     

GPLP:基于标签传播的大图多级划分算法

图数据划分问题是大图处理系统的关键问题,制约着图处理系统的计算效率。目前可用的划分算法可分为随机划分和多层次划分,已有的算法难以在划分速度和划分效果两个方面同时满足要求。提出了一种新的基于标签传播的多级划分算法GPLP,该方法将图划分过程分为数据标记、图粗糙化和数据迁移三部分,在多级划分框架下采用标签传播算法,并对其进行了改进。从数据划分时间和迭代计算时间两个方面对比GPLP算法、Hash算法和Par METIS算法的性能,实验结果表明GPLP算法能够提高迭代计算速度,减少了划分时间,并且数据规模越大,其优势越明显。     

BSP模型下基于边聚簇的大图划分与迭代处理

近年来随着互联网的普及和相关技术的日益成熟,大规模图数据处理成为新的研究热点.由于传统的如Hadoop等通用云平台不适合迭代式地处理图数据,研究人员基于BSP模型提出了新的处理方案,如Pregel,Hama,Giraph等.然而,图处理算法需要按照图的拓扑结构频繁交换中间计算结果而导致巨大的通信开销,这严重地影响了基于BSP模型的系统的处理性能.首先从降低消息通信的角度分析当前主流BSP系统的处理方案,然后提出了一种基于边聚簇的垂直混合划分策略(EC-VHP),并建立代价收益模型分析其消息通信优化的效果.在EC-VHP的基础上,提出了一个点-边计算模型,并设计了简单Hash索引和多队列并行顺序索引机制,进一步提高消息通信的处理效率.最后,在真实数据集和模拟数据集上的大量实验,验证了EC-VHP策略和索引机制的正确性和有效性.     

基于改进图划分的异构并行计算模型设计

为了实现大规模计算机集群上的高效分布式并行计算,设计了一种基于改进图划分和量子遗传算法的异构节点并行计算模型;首先,介绍了传统图划分模型并分析了其不足,然后从图的有向性、通信开销计算和负载均衡度等方面对传统的图划分模型进行了改进,从而得到一个改进的图划分模型;最后,以最小化通信开销和优化资源负载均衡为目标,通过设计编码方案,在改进的图划分模型上提出了采用量子遗传算法获取最优任务划分方案的最优解;仿真实验表明:文中方法能有效实现任务的并行计算,与其它方法相比,具有较小的通信开销和较好的负载均衡度,具有很强的可行性。     

分布式多维大图迭代计算性能优化方法

大规模图的复杂挖掘算法通常需要高频迭代分析,而在计算与存储方面扩展性良好的分布式计算是提高处理效率的有效方案.然而,图顶点之间存在自由分布的边关系,会在分布式计算任务之间产生大量消息,由此在迭代过程中产生的巨大通信开销严重制约性能收益.已有工作在传统消息推送框架下采用合并和备份等技术降低通信代价,但主要面向结构简单、易优化的单维消息类算法,并不适用于结构复杂的多维消息类算法,也难以与当前最先进的消息按需拉取框架兼容.因此提出一种新型轻量级顶点备份机制,通过备份顶点的按需同步以及本地消息的按需生成,可完美继承拉取框架在容错和内存管控等方面的系统优势,同时显著降低通信代价.此外,通过考虑通信收益与负载偏斜代价,可计算最优阈值以提高整体性能.最后在大量真实数据集上验证了相关技术的有效性.     

一种基于数据流约束的Web服务组合划分方法

在WebJet平台工具支撑下,针对数据流约束的应用环境,对Web服务采取集中式组合,分布式运行的技术路线。在满足划分之间数据流量最小化以及分布式系统吞吐量最大化的目标约束下,运用图划分的多级算法将Web服务组合划分成分布式代码片段。在划分过程中,以极小化边割权值和为目标,多资源负载均衡为约束条件。实例分析说明该算法能自动、快速地将集中式BPEL程序划分为分布式的BPEL程序,并对BPEL程序迁移到的分布式节点之间的负载进行基于多资源约束的均衡调整,使分布式运行系统达到负载均衡。     

基于图多层K路划分的仿真节点映射策略

为了提高网络仿真系统中,多物理服务器情况下,服务器资源的利用率,提出一种基于图多层K路划分的仿真节点映射策略。首先对仿真网络拓扑图进行多层K路划分,将节点映射问题转化为图划分问题,然后依据划分结果将仿真节点映射到物理服务器。经过试验表明,相对于随机映射策略,该策略在保证物理服务器负载均衡的同时,可以有效减少物理服务器资源的消耗。     

BHP：面向BSP模型的负载均衡Hash图数据划分

图数据划分是基于BsP（bulksynchronousparallel）编程模型的大规模图处理系统中一个关键技术问题。传统的图划分技术需要多次迭代,时间复杂度过高,且划分结果不具有图顶点到分区的映射信息,因此这些算法并不适用于BSP模型下的数据划分。提出了一种新的面向BSP模型的负载均衡Hash数据划分算法（balancedHashpartition,BHP）。为了实现各个分区的出边数尽可能均衡,该算法引入了虚拟桶的概念,通过贪婪算法将虚拟桶重组为实际分区,保证了每个实际分区负载均衡,同时数据本地化策略使本分片上的数据尽可能地保留在本节点上,从而减小在数据加载时的数据迁移开销。从三个方面对比了BHP算法和经典Hash算法的性能,结果表明BHP算法能够提高作业的执行效率,减少消息发送的数量,有效解决了经典Hash算法的负载不均衡和分区间交互边过多的问题,当数据量变大时,效果尤为明显。     

基于变换的大图点边可视化综述

大图可视化是信息可视化领域的前沿课题之一,也是在线社会网络、信息安全、电子商务等热点行业大数据分析的重要支撑技术.基于变换的大图点边可视化方法由于其具有在线处理时间短、可视复杂度低、交互方法灵活多样等优点,近年来在学术界与实际商用系统中得到广泛重视与应用.文中从图可视化的基本概念及其在大图上的关键挑战出发,梳理了基于变换的大图点边可视化方法的典型分类与主要流程;通过详述3类基于变换的大图点边可视化典型方法(图数据抽象、视图变换与视角转换),阐明了不同方案的优缺点与适用场景,并进一步指出了未来工作的可行方向与潜在难点.     

双目标优化的RDF图分割算法

分布式存储是解决大规模数据存储的一种比较有效的方法,而数据分割是实现分布式存储的前提。面对不断增长的RDF数据,提出一种基于双目标优化的RDF图分割算法（RDF Graph Partitioning algorithm based on Double Objective Optimization,RGPDOO）。RGPDOO将边割和分割平衡两项图分割指标融合到一个目标函数,并依据此目标函数,实现了RDF图的静态和动态分割。其中静态图分割通过对图进行初始划分,将图中顶点分成内核顶点、交叉顶点和自由顶点三类。然后通过计算目标函数增益对交叉和自由顶点进行分配。动态图分割部分,针对RDF元组的插入和删除给出相应的解决方案。同时,为了满足图分割目标,算法每隔一段时间[T]会根据子图的平衡性和紧密性进行一次动态调整。实验选择合成和真实数据集进行测试,并分别与几种通用的静态和动态图分割算法进行比较。实验结果表明提出的算法能够有效地实现RDF图的静态和动态分割。     

基于图非均衡划分的软件定义网络异构控制器负载优化部署

大规模软件定义网络(SDN)往往需要逻辑上集中的控制器在物理上分布式部署。针对控制器部署中控制器负载不均衡的问题,提出一种基于图非均衡划分的SDN异构控制器负载优化部署方法。首先,分析控制器部署要求以及部署带来的控制器负载均衡和时延问题;其次,利用图论和余弦相似度,量化描述和计算异构控制器情况下的控制器负载均衡和时延,并运用图划分理论将控制器负载优化部署问题转化为一个具体的图划分问题;最后,基于多级划分的图划分思想,提出控制器负载优化部署方法。对实际网络拓扑的模拟实验结果表明,提出的部署方法可以有效实现接近最优的控制器负载分布。     

基于分割图集的频繁闭图挖掘算法*

为了解决大规模图集挖掘算法PartGraphMining必须重复扫描图集才能得到全部频繁子图的缺点,提出了一种改进的IPMC算法,通过hash表保存同构图的hash地址和支持度,不必重复扫描图集就可快速得到全部频繁子图,再经过少量的子图同构判断得到全部频繁闭图。在实际数据集上运行的实验结果表明它比原算法的挖掘效率有所提高。     

基于通信负载均衡的社交网络图分割方法

海量社交网络数据中蕴含着丰富的信息,图论是挖掘这些信息的重要方法之一。面对日益增多的图数据,分布式计算成为处理大规模图数据的有效手段。在分布式图计算中,通信所消耗的时间占有很大的比例,通过图分割算法的设计可以有效地降低通信量并实现负载均衡,从而提高分布式图计算的效率,典型的例子包括Metis图分割算法。但是,用现有的图分割算法处理非均衡图数据会造成各个子图之间通信量不均衡,从而影响了计算效率。为了解决这一问题,提出一种新的图分割方法：通信均衡标签交换方法。该方法在保持子图规模一致的基础上,既降低了全图计算所需的通信量,又使各个子图之间的通信量达到均衡。实验结果表明,与Metis等典型的图分割算法相比,提出的图分割方法在各种数据集和集群配置情况下,能降低6%~30%的图计算时间,充分显示了该方法的有效性。     

分布式入侵检测中基于能力与负载的数据分割算法

针对高速网络环境下分布式入侵检测中海量数据并行检测处理的效率和检测率问题,提出一种基于能力与负载的数据分割算法。该算法依据采集到的集群内各数据分析节点的系统性能指标及运行状态,评估节点的数据处理能力与负载程度。基于节点的能力与负载适应因子,权衡节点在集群中检测和分析数据能力的权重,实现海量数据在集群内各数据分析节点间的动态数据分割,为节点分配适应其能力与实时负载的数据粒度。仿真测试结果表明,该算法具有较好的负载均衡性,降低了系统的检测时间,提高了数据并行处理的效率和检测率。     

一种基于图的人脸特征提取方法

当前主流特征提取方法主要从全局特征或局部特征出发实现降维。为了能充分反映样本的全局特征和局部特征,提出基于图的人脸特征提取方法。该方法首先通过对训练样本进行学习得到最佳投影方向,该方向保证投影后的样本类内紧密而类间松散;然后将测试样本映射到最佳投影方向上并利用最近邻分类器进行样本类属判定。标准人脸库上的比较实验结果证明了所提方法的有效性。     

基于Ncut准则的图分割的新算法

针对有权图分割时不能很好解决子图内部耦合度不高的问题,使用可以同时优化子图内部顶点耦合度和子图之间顶点耦合度的Ncut准则,提出了一种新的基于迭代改善策略的RNK分割算法。算法通过不断交换可以改善Ncut值的顶点对优化现有分割。与传统分割算法相比,可以同时保证子图内最大耦合度和子图间最小的耦合度。并提出一种散列技术,提高查找最优交换顶点对的效率。当图为稠密矩阵时,改善效果尤为明显。通过对随机图分割的实验结果表明,该算法较传统的KL算法可以得到更理想的分割结果。     

基于广度优先遍历加权图生成的启发式图分区

图分区质量极大程度上影响着计算机之间的通信开销和负载平衡, 这对于大规模并行图计算的性能是至关重要的. 然而, 随着图数据规模的越来越大, 图分区算法的执行时间成了一个不可避免的问题. 因此, 研究如何优化图分区算法的执行效率是有必要的. 本文提出了一个基于广度优先遍历加权图生成的启发式图分割方法, 该方法在实现较低的通信代价和较好负载平衡的同时, 只引入了少量的预处理时间开销. 实验结果表明, 本文的划分方法减少了复制因子, 降低通信开销, 并且引入的时间开销较小.     

大规模标签图中的动态Top-K兴趣子图查询

针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题,提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法DISQtop-K。该方法建立了包括节点拓扑结构特性（NTF）索引和边特性（EF）索引的图拓扑结构特性（GTSF）索引,利用该索引可有效剪枝过滤不满足限制条件的无效节点及边;基于GTSF索引提出了多因素候选集过滤策略,通过对查询图候选集进一步剪枝以获得较少的候选集;考虑到图的动态变化可能对匹配结果产生影响,提出了Top-K兴趣子图匹配验证方法——DISQtop-K,将匹配验证过程分为初始匹配和动态修正两个阶段,以尽可能保证查询结果的实时、准确。大量实验结果表明,相比RAM、RWM算法,DISQtop-K方法的索引创建时间较短且占用空间较少,能有效处理大规模标签图中的动态Top-K兴趣子图查询。