OnFlyP:基于定向边交换的分布式在线大图划分算法

随着大数据时代的到来,基于云环境的大图迭代计算已经成为新的研究热点,其中提高图划分算法的执行效率和降低划分后子图之间的通信边规模是改善计算性能的关键.已有工作主要分为离线划分和在线划分两大类,无法在执行效率和通信边规模方面同时满足迭代处理需求.文中针对真实世界的大图,提出了聚簇系数概念,定量分析了顶点分布的局部性,以此为基础设计了一种基于定向边交换模型的分布式在线图划分算法(OnFlyP),可在迭代计算的数据加载阶段快速完成图划分,同时通过出边的交换有效降低通信边规模,以满足迭代计算需求.OnFlyP采用实时控制和最小对称矩阵控制实现负载均衡,前者具有较高的执行效率,而后者对降低通信边规模有较好的优化效果,可根据实际应用的处理需求灵活选择.最后,作者使用多种真实数据验证了OnFlyP算法的有效性.

DisHAP:基于层次亲和聚类的分布式大图划分算法

平衡图划分是改善并行图计算性能的关键.一个良好的划分算法应保证划分后的子图在负载均衡的前提下,减少子图之间的交互边(切割边)规模,从而减少网络通信.对此,本文设计一种基于层次亲和聚类的分布式大图划分算法(DisHAP).该算法采用亲和聚类的思想,将图初始划分为规模相等的k个子图;再将结果映射成顶点序列,以线性嵌入顺序处理节点,通过局部交换策略优化割边率;最后将DisHAP应用在MapReduce框架中,使用多种真实及理论图数据,与现有的大图划分算法做比较分析.以Twitter图为例,划分2,4,8,16,32个子区,相较于现有的大图划分算法(LDG,BLP,Spinner,Fennel,ParMetis及PSA-MIR算法),割边率减少1.7%~30.2%,说明了该算法的优越性.同时该算法具有良好的可扩展性,划分的子区数量及图的规模对划分时间具有较低的影响.

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

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