CAJ | 학술논문

随着社交网络的流行，越来越多的相关应用要求能够实时地在大规模社会网络图上进行分析和计算。而目前的图处理系统，如Google的Pregel，是全局、批量处理的图处理系统，并不能实现对图的实时计算。因此，提出了一种新的图增量处理模型，当一个节点发生变化时，只需要以传播的方式更新局部范围内受影响节点。它本质上将传统的批量全局计算模型，转化成一系列的增量的、局部的图计算，保证对图变化的实时处理，并通过避免没有更新节点的重复计算来降低开销。基于这种新的图计算模型，设计了一个低开销、实时的图处理系统--IncGraph，它通过图切分技术将计算局部化，保证了计算的低开销，同时利用主动计算触发和反向链式更新技术，保证了计算的实时性和可靠性。利用真实的社交网络数据证明了IncGraph的低开销、实时性和扩展性。IncGraph的提出会为社交网络应用提供更为灵活的计算框架。
수착사교망락적류행，월래월다적상관응용요구능구실시지재대규모사회망락도상진행분석화계산。이목전적도처리계통，여Google적Pregel，시전국、비량처리적도처리계통，병불능실현대도적실시계산。인차，제출료일충신적도증량처리모형，당일개절점발생변화시，지수요이전파적방식경신국부범위내수영향절점。타본질상장전통적비량전국계산모형，전화성일계렬적증량적、국부적도계산，보증대도변화적실시처리，병통과피면몰유경신절점적중복계산래강저개소。기우저충신적도계산모형，설계료일개저개소、실시적도처리계통--IncGraph，타통과도절분기술장계산국부화，보증료계산적저개소，동시이용주동계산촉발화반향련식경신기술，보증료계산적실시성화가고성。이용진실적사교망락수거증명료IncGraph적저개소、실시성화확전성。IncGraph적제출회위사교망락응용제공경위령활적계산광가。
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 dupli-cate 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 parti-tion 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.