Abstract: With the increasing popularity of online social networks (OSNs), more and more related applications need a computation framework for processing large social graphs in a real-time manner. However, the existing graph processing systems, such as Google’s Pregel, cannot achieve real-time performance due to processing the graph in global and batch manners. Therefore, this paper proposes a new graph computation model that restricts the computation to a local area when a node is updated. In essence, it transforms the traditional batch and global computations to a series of incremental and local computations. By this way, people achieve the goal of real-time computation, and avoid the overhead of duplicate computation on nodes that have not changed. Based on this new computation model, this paper designs IncGraph, a real-time large graph processing system. To achieve an efficient and scalable implementation, this paper uses graph partition techniques to exploit the computation locality in social graph, moreover, uses proactive computing trigger and inversing update chain to realize the real-time and reliable computing. Finally, this paper uses real social network data to validate the system performance. IncGraph can provide social network applications a more flexible computation framework.

Key words: graph processing system, incremental graph processing, graph partition, proactive computing trigger, inversing update chain

摘要： 随着社交网络的流行，越来越多的相关应用要求能够实时地在大规模社会网络图上进行分析和计算。而目前的图处理系统，如Google的Pregel，是全局、批量处理的图处理系统，并不能实现对图的实时计算。因此，提出了一种新的图增量处理模型，当一个节点发生变化时，只需要以传播的方式更新局部范围内受影响节点。它本质上将传统的批量全局计算模型，转化成一系列的增量的、局部的图计算，保证对图变化的实时处理，并通过避免没有更新节点的重复计算来降低开销。基于这种新的图计算模型，设计了一个低开销、实时的图处理系统——IncGraph，它通过图切分技术将计算局部化，保证了计算的低开销，同时利用主动计算触发和反向链式更新技术，保证了计算的实时性和可靠性。利用真实的社交网络数据证明了IncGraph的低开销、实时性和扩展性。IncGraph的提出会为社交网络应用提供更为灵活的计算框架。

关键词: 图处理系统, 增量图处理, 图切分, 主动计算触发, 反向链式更新