图作为一种复杂的数据结构通常用来对现实世界中的问题进行建模,随着大数据时代的到来,现实世界图的规模迅速增长并超过普通单台计算机的内存容量。为了能够在有限的内存中对大图数据进行处理,研究人员提出许多核外(基于磁盘的)图处理系统,这些核外图处理系统使得人们在没有分布式集群和大内存机器的情况下也能处理大规模图数据,这些系统还提供了友好的编程接口方便用户的使用。但这些图处理系统的缺点也很明显:根据顶点编号划分子图忽略了图数据中顶点间的相邻关系,每轮迭代中每个顶点只处理一次导致新消息传播缓慢、图算法需要多次迭代才能收敛。针对这些问题,提出了核外块更新方法并基于核外图处理系统GraphChi实现该方法(新系统为BlockGraphChi),还提出了一种适应于该方法的有向多层图划分方法。借助核外块更新方法,图算法在执行过程中产生的新消息仅需一次迭代就可以在块中得到充分传播,从而减少了图算法的迭代次数,加速了图算法的收敛。通过有向多层图划分方法划分子图,由于划分时考虑了现实世界图的结构和图算法的特点,使得子图内部具有良好的局部性,子图间边的方向更加一致,从而方便新消息的传播和避免子图频繁的磁盘I/O,最终达到加速图算法执行的目的。实验结果表明,BlockGraphChi相比于GraphChi具有更好的性能。在相同的实验环境下,图算法在使用核外块更新方法的BlockGraphChi上收敛速度比GraphChi上的最多快30.4倍,迭代次数最多减少98.1%。对于固定点算法,在其他划分方法结合核外块更新方法无法发挥作用的时候,有向多层图划分方法仍然能取得较明显的性能优势。