دانلود حاوی مقاله اصلی انگلیسی به همراه مقاله ترجمه شده در فایلword (در صورتی که فایل وورد کلماتش بهم چسپیده بود مشکل از نسخه وورد مشتری هست ) ترجیحا نسخه 2013 و 2010 و یا بالاتر داشته باشین) و در صورت بروز هر مشکلی به پشتیبانی اطلاع دهید

الگوریتم‌های اکتشافی (هیورستیک) موازی برای تشخیص تشکل مقیاس‌پذیر

الگوریتم‌های اکتشافی (هیورستیک) موازی برای تشخیص تشکل مقیاس‌پذیر

Parallel heuristics for scalable community detection
Hao Lu a, Mahantesh Halappanavar b, Ananth Kalyanaraman a,
a School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, United States
b Fundamental and Computational Sciences Directorate, Pacific Northwest National Laboratory, Richland, WA 99352, United States
a r t i c l e i n f o
Article history:
Available online 14 March 2015
Keywords:
Community detection
Parallel graph heuristics
Graph coloring
Graph clustering
a b s t r a c t
Community detection has become a fundamental operation in numerous graph-theoretic
applications. It is used to reveal natural divisions that exist within real world networks
without imposing prior size or cardinality constraints on the set of communities. Despite
its potential for application, there is only limited support for community detection on
large-scale parallel computers, largely owing to the irregular and inherently sequential
nature of the underlying heuristics. In this paper, we present parallelization heuristics
for fast community detection using the Louvain method as the serial template. The
Louvain method is a multi-phase, iterative heuristic for modularity optimization.
Originally developed by Blondel et al. (2008), the method has become increasingly popular
owing to its ability to detect high modularity community partitions in a fast and memory
efficient manner. However, the method is also inherently sequential, thereby limiting its
scalability. Here, we observe certain key properties of this method that present challenges
for its parallelization, and consequently propose heuristics that are designed to break the
sequential barrier. For evaluation purposes, we implemented our heuristics using
OpenMP multithreading, and tested them over real world graphs derived from multiple
application domains (e.g., internet, citation, biological). Compared to the serial Louvain
implementation, our parallel implementation is able to produce community outputs with
a higher modularity for most of the inputs tested, in comparable number or fewer itera
tions, while providing absolute speedups of up to 16 using 32 threads.
2015 The Authors and Battelle Memorial Institute. Published by Elsevier B.V. This is an
open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/

................................................................................

ترجمه چکیده مقاله به صورت رایگان

الگوریتم‌های اکتشافی (هیورستیک) موازی برای تشخیص تشکل مقیاس‌پذیر

کلمات کلیدی: تشخیص تشکل، روش‌های اکتشافی گراف موازی، رنگ‌آمیزی گراف، خوشه‌بندی گراف

چکیده:

تشخیص تشکل در بسیاری از برنامه‌های کاربردی نظری گراف به عملیات اساسی تبدیل شده است. این روش برای نشان دادن تقسیمات طبیعی که در شبکه‌های دنیای واقعی وجود دارد استفاده می‌شود بدون اینکه محدودیت‌های اصلی یا پیشین روی مجموعه تشکل‌ها اعمال شود. با وجود پتانسیل این روش برای برنامه‌های کاربردی، در کامپیوترهای موازی مقیاس بزرگ، تنها پشتیبانی محدودی برای تشخیص تشکل وجود دارد که عمدتاً به دلیل ماهیت ذاتی ترتیبی و بی نظم روش‌های اکتشاف پایه است. در این مقاله روش‌های اکتشاف موازی‌سازی را برای تشخیص تشکل با استفاده از روش Louvain  ارائه می‌کنیم که به عنوان یک قالب سریال مورد استفاده قرار می‌گیرد. روش Louvian یک روش چندمرحله‌ای و اکتشاف تکراری برای بهینه‌سازی ماژولاریتی است. این روش در اصل توسط بلاندل[3] و همکاران توسعه یافته است (2008)  و این روش به دلیل قابلیت‌هایی که برای تشخیص بخش‌های تشکل ماژولار دارد  از نظر کارآمدی حافظه و سرعت بسیار معروف شده است. با این حال ماهیت این روش ترتیبی است و مقیاس پذیری آن را محدود می‌کند. در اینجا خواص کلیدی و مهم این روش را می‌بینیم که چالش‌هایی برای موازی سازی و روش‌های اکتشافی نتیجه فراهم آورده است و به منظور شکستن موانع ترتیبی ارائه شده‌اند. به منظور ارزیابی روش‌های اکتشافی خود را با استفاده از چندنخی OpenMP ارائه کردیم و آنها را در گراف‌های دنیای واقعی در دامنه‌های کاربردی مختلف بررسی کرده‌ایم (برای مثال اینترنت، استناد و بیولوژیک) در مقایسه با پیاده‌سازی Louvian سریال، پیاده‌سازی موازی ما می‌تواند خروجی تشکل‌ها را با ماژولاریتی بالاتر برای اکثر ورودی‌های مورد آزمایش تولید کند که این میزان قابل مقایسه بوده و تعداد تکرارهای کمتری داشته باشند و همچنین میزان تسریع مطلوب تا 16برابر با استفاده از 32 نخ ارائه می‌کند.


 


اشتراک بگذارید:


پرداخت اینترنتی - دانلود سریع - اطمینان از خرید

پرداخت هزینه و دریافت فایل

مبلغ قابل پرداخت 18,000 تومان
کدتخفیف:

درصورتیکه برای خرید اینترنتی نیاز به راهنمایی دارید اینجا کلیک کنید


فایل هایی که پس از پرداخت می توانید دانلود کنید

نام فایلحجم فایل
Parallel-heuristics-for-scalable-community-detecti_1777698_2728.zip4 MB





الگوریتم فوق موازی برای مثلث بندی درون هسته و برون هسته داده بزرگ در E2 و E3

الگوریتم فوق موازی برای مثلث بندی درون هسته و برون هسته داده بزرگ در E2 و E3   Volume 51, 2015, Pages 2613–2622ICCS 2015 International Conference On Computational Science Highly Parallel Algorithm for Large DataIn–Core and Out–Core Triangulation in E2 and E3    AbstractA triangulation of points in E2, or a tetrahedronization of points in E3, is used in many applica ...

توضیحات بیشتر - دانلود 10,000 تومان