کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4946078 1439267 2017 34 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A feasible graph partition framework for parallel computing of big graph
ترجمه فارسی عنوان
یک چارچوب پارتیشن گراف قابل اجرا برای پردازش موازی گراف بزرگ
کلمات کلیدی
پارتیشن گراف، همبستگی گراف بزرگ، بهینه سازی هدف، الگوریتم حریص،
ترجمه چکیده
با در حال ظهور شبکه های پیچیده در مقیاس بزرگ، محاسبات گراف، مانند تشخیص جامعه، با چالش های فناوری جدید هزینه های بسیار محاسباتی بزرگ مواجه می شوند. برای مقابله با این چالش ها، موازی بودن لازم است. پارتیشن گراف یک مشکل اساسی از محاسبات موازی برای داده های گراف بزرگ است. چالش های پارتیشن بندی گراف شامل تعداد زیادی ارتباط بین پارتیشن ها، تکرار شدید رأس ها و پارتیشن نامتعادل است. در این مقاله، یک چارچوب پارتیشن گراف قابل اجرا برای محاسبات موازی گراف بزرگ پیشنهاد می کنیم. چارچوب مبتنی بر یک مشکل بهینه سازی هدف برای کاهش پهنای باند، حافظه و هزینه ذخیره سازی با این شرایط است که تعادل بار را می توان تضمین شده است. در این چارچوب، سه الگوریتم پارتیشن بندی حریصانه پیشنهاد شده است. با اجرای الگوریتم های مختلف گراف ها، از جمله نمودارهای واقعی و نمودارهای مصنوعی، نتایج تجربی نشان می دهد که الگوریتم های ما از حالت الگوریتم های هشتی هنری برتر هستند. به عنوان مثال، زمان اجرا بیش از 21.56 درصد کاهش می یابد و هزینه ارتباطی برای نمودار وزنی بیش از 17.90 درصد کاهش می یابد. آزمایش های کافی نشان می دهد که الگوریتم های ما قادر به حل مشکل پارتیشن گراف با نیازهای مختلف هستند.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش مقاله
یک چارچوب پارتیشن گراف قابل اجرا برای پردازش موازی گراف بزرگ
چکیده انگلیسی
With the emerging of large scale complex networks, graph computation, such as community detection, meets new technology challenges of extremely large computational cost. In order to deal with these challenges, the parallelism is becoming necessary. Graph partition is a fundamental problem of parallel computing for big graph data. The challenges of graph partition include large numbers of communications between partitions, extreme replication of vertices, and unbalanced partition. In this paper, we propose a feasible graph partition framework for parallel computing of big graph. The framework is based on an objective optimization problem to reduce the bandwidth, memory and storage cost on condition that the load balance could be guaranteed. In this framework, three greedy graph partition algorithms are proposed. By running the algorithms on the different kinds of graphs, including real-world graphs and synthetic graphs, the experimental results show that our algorithms surpass the state of the art heuristic algorithms. For example, running time is reduced more than 21.56% and the communication cost is decreased by more than 17.90% for weighted graph. The adequate experiments verify that our algorithms are capable of solving the problem of graph partition with different needs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Knowledge-Based Systems - Volume 134, 15 October 2017, Pages 228-239
نویسندگان
, , , ,