BLADYG: چارچوب پردازش گراف برای گراف های پویای بزرگ
اخیرا، پردازش توزیع شده ی گراف های پویای بزرگ، مخصوصا در زمینه های خاصی مانند آنالیز شبکه اجتماعی، آنالیز گراف وب و آنالیز شبکه فضایی مشهور گشته است. در این راستا، سیستم های پردازش گراف توزیع شده/موازی زیادی پیشنهاد شده اند که شامل Pregel ، PowerGraph ، GraphLab و Trinity می باشند. با این حال، این سیستم ها تنها در رابطه با گراف های ایستا هستند و بحث پردازش گراف های پویا و در حال تکامل را در نظر نمی گیرند. در این مقاله، بحث های مقیاس و پویایی را در مورد سیستم های پردازش گراف در نظر می گیریم. چارچوب پردازش گراف با عنوان BLADYG ، را ارائه می کنیم که بحث پویایی را در گراف های مقیاس بزرگ مطرح می سازد. پیاده سازی BLADYG را بر روی چارچوب AKKA نیز ارائه می کنیم. بطور تجربی به ارزیابی کارایی چارچوب پیشنهادی با اعمال آن در مسائلی مانند تفکیک k هسته توزیع شده و پارتیشن بندی گراف های پویای بزرگ می پردازیم. نتایج تجربی نشان می دهند که کارایی و مقیاس پذیری BLADYG برای گراف های پویای مقیاس بزرگ، مطلوب هستند.
کلمات کلیدی: پردازش گراف توزیع شده، گراف های پویا، چارچوب AKKA ، پارتیشن بندی گراف، تفکیک k هسته.
BLADYG: A Graph Processing Framework for Large Dynamic Graphs
Volume 9, September 2017, Pages 9-17
Abstract
Recently, distributed processing of large dynamic graphs has become very popular, especially in certain domains such as social network analysis, Web graph analysis and spatial network analysis. In this context, many distributed/parallel graph processing systems have been proposed, such as Pregel, PowerGraph, GraphLab, and Trinity. However, these systems deal only with static graphs and do not consider the issue of processing evolving and dynamic graphs. In this paper, we are considering the issues of scale and dynamism in the case of graph processing systems. We present BLADYG, a graph processing framework that addresses the issue of dynamism in large-scale graphs. We present an implementation of BLADYGon top of AKKA framework. We experimentally evaluate the performance of the proposed framework by applying it to problems such as distributed k-core decomposition and partitioning of large dynamic graphs. The experimental results show that the performance and scalability of BLADYG are satisfying for large-scale dynamic graphs.
Keywords: Distributed graph processing, Dynamic graphs, akka framework, Graph partitioning, k-Core decomposition
