پیاده سازی توزیع شده الگوریتم Louvain برای تشخیص اجتماع های گراف موازی و بهبودمقیاس پذیری با روش های اکتشافی

در اکثر شبکه های دنیای واقعی، گره ها به صورت اجتماعات یا خوشه های محکمی سازماندهی می شوند. تقسیم بندی به اجتماع ها اغلب با استفاده از معیار modularity صورت می گیرد. با این وجود، بهینه سازی این تقسیم بندی چالش برانگیز است. در سال ۲۰۰۸ ،الگوریتم Louvain با رویکردی چند مرحله ای و تکراری برای بهینه سازی modularity معرفی شد. این الگوریتم به دلیل سرعت و کیفیت تولید اجتماعات، همچنان یکی از ابزارهای محبوب برای تشخیص اجتماعات به صورت ترتیبی محسوب می شود. این مقاله یک پیاده سازی توزیع شده از الگوریتم Louvain برای تشخیص اجتماع ها در گراف های موازی ارائه می دهد. این پیاده سازی با استفاده از فرآینده های ۴ K سرعت های ۱.۸ تا ۴۶.۱۸ برابر نسخه اصلی را برای شبکه های مختلف دنیای واقعی به ارمغان آورده است. همچنین نتایج نشان می دهند که مدل های حاصل از پیاده سازی های مختلف الگوریتم Louvain در اکثر موارد با بهترین مدل های الگوریتم های تشخیص اجتماع سریال مقایسه پذیر هستند. این مقاله با ارائه بحث های جامع در مورد اجرای موازی، روش های اکتشافی و تحلیل های تجربی، به بهبود عملکرد الگوریتم های تشخیص اجتماع با ساختار تکراری حریصانه و محاسبات محوری کمک می کند. همچنین، مسیرهای آینده مطرح شده اند که باعث افزایش سرعت همگرایی الگوریتم می شود. به منظور افزایش مقیاس پذیری، از عملیات های مجاورتی جمعی استفاده می شود که در MPI-۳ تعریف شده است.

کلیدواژه ها:

اجتماعات گراف ، تشخیص اجتماعات ، الگوریتم Louvain ، پیاده سازی توزیع شده ، معیار Modularity ، مقیاس پذیری