异构集群下基于标签传播的大规模图划分算法

近年来,大规模图数据处理在众多领域得到广泛应用,图划分算法是分布式图计算系统的基础,但大规模图在异构集群中的划分尚未得到充分研究。为此,针对异构集群,提出基于标签传播的大规模图划分算法(heterogeneous label propagation, HLP),根据计算节点负载能力进行图划分,以实现负载均衡和边割率最小化为目标。HLP算法规避了传统标签传播中顶点迁移的步骤,提高了算法效率。实验结果表明,HLP算法在分区质量以及划分效率方面均有较好表现。     

一种松弛的优化均衡流式图划分算法研究

在大规模图数据的分布式处理中,往往需要将图数据进行划分并放置在不同的节点上。如果数据划分得不均衡,那么部分节点可能会成为分布式系统的瓶颈。为了提高图数据划分的均衡性,并且有效地应对图数据的快速更新,提出了一种松弛的优化均衡流式图划分算法。首先,定义了一种同时包含划分内部代价和划分之间的割的代价的目标函数作为图划分的整体框架。然后,在图划分框架的基础上通过最大化和最小化两种优化函数分析了均衡图划分问题,并给出了二者之间的关系。最后,针对流式图数据,提出一种贪婪的图最优k划分算法。该划分算法以最大化优化函数为基础,通过最大化顶点放置产生的目标函数增加值进行节点划分块的选取。实验表明,提出的图划分算法与相关算法相比,不仅均衡性好,而且通信开销小,在基于该算法进行图划分时上层应用的计算性能得到了明显的提高。     

动态图划分算法研究综述

图划分是大规模分布式图处理的首要工作,对图应用的存储、查询、处理和挖掘起基础支撑作用.随着图数据规模的不断扩大,真实世界中的图表现出动态性.如何对动态图进行划分,已成为目前图划分研究的热点问题.从不同动态图划分算法的关注点和特点出发,系统性地介绍当前可用于解决动态图划分问题的各类算法,包括流式图划分算法、增量式图划分算法和图重划分算法.首先介绍图划分的3种不同的划分策略及问题定义、图的两种不同的动态性来源以及动态图划分问题;然后介绍3种不同的流式图划分算法,包括基于Hash的划分算法、基于邻居分布的划分算法以及基于流的优化划分算法;其次介绍单元素增量式划分和批量增量式划分这两种不同的增量式图划分算法;再次,分别介绍针对图结构动态的重划分算法和针对图计算动态的重划分算法;最后,在对已有方法分析和比较的基础上,总结目前动态图划分面临的主要挑战,提出相应的研究问题.     

基于邻域的大规模图数据动态分割算法

随着图数据的规模日益增大,出现大量以动态图数据为基础的分布式处理需求,划分问题在动态图数据分布式处理领域尤为重要. 对大规模动态图数据上的划分问题进行研究,根据图结构性质及动态图特点,提出并实现基于邻域的动态图分割算法. 算法分为静态切分和动态调整两个阶段,其中基于割边算法整合现有最优化策略提出了大规模图数据的静态切割算法. 在优化后的静态切割算法的基础上,根据图数据的动态扩张的特性提出动态分割算法. 根据迁移顶点所达到的最小负载值进行顶点迁移,并在此基础上进行性能及割边控制优化操作. 最后,改进算法在各类图数据集上进行了验证,验证的结果显示在平衡度和割边等指标上优化后的算法效果显著,提高了划分的合理性,并且在保证割边不增加的情况下提高了图分割的平衡度.     

面向异质图的在线图划分算法

图划分算法是分布式图计算系统里的重要组成部分, 它将一个图划分为若干子图以便在分布式系统中运行, 并将子图上的点和边数据及子图上的计算任务分配到各分区. 异质图是现实世界中广泛存在的一种图, 它是指具有多种节点类型或边类型的图, 在针对异质图的计算过程中, 现有的图划分算法对于异质图的处理没有考虑到以下问题: 在图计算过程中, 不同类型的节点和边携带的数据量可能不同; 不同的节点和边类型, 可能会采用不同的处理算法, 其计算时间也会不同. 针对现有图划分方法的不足, 本文提出一种面向异质图的在线图划分算法OGP-HG算法, 并对现有的GraphX图计算引擎进行改进, 将OGP-HG算法在改进后的图计算引擎中实现. 本文提出的OGP-HG算法通过计算节点划分到不同分区上的负载均衡得分和边划分到不同分区上的数据均衡得分, 得到使异质图负载和内存占用均衡的划分结果. 实验表明, 与传统图划分算法相比, 该算法提高异质图计算效率1.05–1.4倍.     

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

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

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

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

SpecGraph:基于并发更新的分布式实时图计算模型

随着互联网的快速发展,越来越多的应用需要在大规模图结构数据上作分析和计算,面对动态变化的图结构,人们希望能够实时地得到反映最新图结构的计算结果.传统的图处理系统都是面向静态图结构,不能满足动态图结构的实时性要求.已经提出的增量图计算模型,其算法适用范围受限,而且都是基于串行执行增量更新,当图结构变化比较迅速时,往往结果的实时性不够高.提出了一种新的基于并发更新的图计算模型SpecGraph,它通过解耦合的计算模型、异步执行引擎和基于推测执行的并发更新机制,达到更广的算法适用性和更高的实时性要求.SpecGraph通过解耦合的计算模型,使得顶点状态只依赖于接收到的邻居信息,为增量更新和并发更新提供了透明实现的可能;通过异步计算引擎,使得系统在增量更新时更加灵活,资源占用低,同时保证了并发的可执行性;通过基于推测执行的并发增量更新,SpecGraph能够达到更高的实时性要求.     

基于分布式的RDF数据分割方法研究

基于分布式的RDF数据分割方法能够解决大规模RDF数据的分割和存储问题。为保证RDF数据的分布式存储和解决数据分割效率提出了一种基于贪婪策略的分割方法。先通过启发式贪心策略根据子图的负载均衡，依次选择度数最高的节点或者度数相对较高的节点，将其放入同一个子图中，后进行相邻顶点的优化。然后通过分区策略将子图分配到对应节点，存储到neo4j数据库并建立相应的索引将数据保存到Redis数据库。实验对比了几种数据分割算法以及图形数据库与关系型数据库的RDF数据存储方案，并验证了RDF图数据的存储方案和分割算法的有效性。     

一种嵌入式系统软硬件划分算法

软硬件划分是嵌入式系统软硬件协同设计中的一个关键问题.传统划分算法具有局部最优,收敛速度慢的缺陷.为使组成系统性能达到最优化,提出一种新的嵌入式系统软硬件划分算法.先采用嵌入式系统转化成有向无环图,可将嵌入式系统软硬件划分问题转换成一个多条件约束问题,用蚂蚁放置于有向无环图顶点上,对系统软硬件的划分准确率作为蚁群算法优化目标,通过蚁群算法搜索最优目标函数值,有效避免传统划分算法搜索陷入局部最小,大幅度降低搜索时间.实验结果表明,采用蚁群算法能够高效、快速获得准确地划分结果,为嵌入式系统设计提供了依据.     

知识图谱划分算法研究综述

知识图谱是人工智能的重要基石,因其包含丰富的图结构和属性信息而受到广泛关注.知识图谱可以精确语义描述现实世界中的各种实体及其联系,其中顶点表示实体,边表示实体间的联系.知识图谱划分是大规模知识图谱分布式处理的首要工作,对知识图谱分布式存储、查询、推理和挖掘起基础支撑作用.随着知识图谱数据规模及分布式处理需求的不断增长,...     

大图结构特征对划分效果的影响

针对大图结构特征如何影响划分效果这一问题,提出一种通过顶点度分布特征来描述大图结构特征的方法。首先,基于真实的图数据产生若干顶点数和边数相同、但结构特征不同的仿真数据集,通过实验计算真实图与仿真图之间的相似度,证明该方法对描述真实大图结构特征的有效性。然后,通过Hash和点对交换划分算法,验证图结构特征与划分效果之间的关系。当点对交换划分算法执行到5万次时,划分一个有6301个顶点和20777条边的真实图其交叉边数比Hash划分算法降低了54.32%,划分仿真图数据集中结构特征差异明显的两个图时,交叉边数分别为6233和316。实验结果表明,点对交换划分算法能够减少交叉边数,图的顶点度分布差异越大,划分后交叉边数越少,划分效果越好,因此大图结构特征影响其划分效果,这为建立图的结构特征与划分效果之间的关系模型研究奠定了基础。     

一种增量式约简方法求解最小顶点覆盖问题

最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转化为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间;实验结果表明该算法的可行性和有效性。     

异构计算中一种图的非均衡划分算法

现有的图的划分算法大多是均衡划分,要求划分块的权值相等,划分块之间的连接代价尽量最小。但是在异构计算环境中,不同的处理机的计算能力不尽相同,从而在并行任务调度时所分配的计算任务量也应随之不同。所以为了适应更广泛意义上的异构负栽均衡,本文提出了异构计算中的一种任务图的非均衡划分算法。该算法根据任意给定的需求,使得划分好的各个子集权值不均等。其中划分子集的个数等于异构环境中处理机的个数,各子集的大小比例于不同处理机的计算能力。算法包括3步：粗化阶段、非均衡划分阶段以及精化还原阶段。本文通过用格林威治大学提供的系列开放图来测试该算法,实验结果表明算法是准确有效的。     

面向大规模二部图的分布式Tip分解算法

Tip分解作为图数据管理领域的热点研究问题,已被广泛应用于文档聚类和垃圾邮件组检测等实际场景中.随着图数据规模的爆炸式增长,单机内存已无法满足其存储需求,亟需研究分布式环境下Tip分解技术.现有分布式图计算系统的通信模式无法适用于二部图,为此,首先提出一种基于中继的通信模式,以实现分布式环境下处理二部图时消息的有效传递...     

Distributed Tip Decomposition on Large Bipartite Graphs

Tip decomposition has a pivotal role in mining cohesive subgraphs in bipartite graphs. It is a popular research topic with wide applications in document clustering, spam group detection, and analysis of affiliation networks. With the explosive growth of the bipartite graph data scale in these scenarios, it is necessary to use distributed methods to realize its effective storage. For this reason, this paper studies the problem of the tip decomposition on a bipartite graph in the distributed environment for the first time. Firstly, a new relay-based communication mode is proposed to realize effective message transmission when the given bipartite graph is decomposed in a distributed environment. Secondly, the Distributed Butterfly Counting (DBC) algorithm and the Distributed Tip Decomposition (DTD) algorithm are designed. In particular, a controllable parallel vertex activation strategy is proposed to solve the problem of memory overflow when DBC decomposes large-scale bipartite graphs. Finally, the message pruning strategy based on vertex priority and message validity pruning strategy are introduced to further improve the efficiency of the algorithm by reducing redundant communication and computing overhead. The experiment is deployed on the high-performance distributed computing platform of the National Supercomputing Center. The effectiveness and efficiency of the proposed algorithms are verified by experiments on several real datasets.     

iGraph: an incremental data processing system for dynamic graph

With the popularity of social network, the demand for real-time processing of graph data is increasing. However, most of the existing graph systems adopt a batch processing mode, therefore the overhead of maintaining and processing of dynamic graph is significantly high. In this paper, we design iGraph, an incremental graph processing system for dynamic graph with its continuous updates. The contributions of iGraph include: 1) a hash-based graph partition strategy to enable fine-grained graph updates; 2) a vertexbased graph computing model to support incremental data processing; 3) detection and rebalance methods of hotspot to address the workload imbalance problem during incremental processing. Through the general-purpose API, iGraph can be used to implement various graph processing algorithms such as PageRank. We have implemented iGraph on Apache Spark, and experimental results show that for real life datasets, iGraph outperforms the original GraphX in respect of graph update and graph computation.     

基于谱方法的无向赋权图剖分算法*

在多水平方法初始剖分阶段提出了一种基于谱方法的无向赋权图剖分算法SPWUG,给出了基于Lanczos迭代计算Laplacian矩阵次小特征值及特征向量的实现细节。SPWUG算法借助Laplacian矩阵次小特征值对应的特征向量,刻画了节点间相对距离,将基于非赋权无向图的Laplacian谱理论在图的剖分应用方面扩展到无向赋权图上,实现了对最小图的初始剖分。基于ISPD98电路测试基准的实验表明,SPWUG算法取得了一定性能的改进。实验分析反映了在多水平方法中,最小图上的全局近似最优剖分可能是初始图的局部最