تشخیص جامعه‌های همپوشان بر اساس انتشار برچسب با روش نگاشت-کاهش

Abstract

تشخیص جامعه در شبکه‌های اجتماعی از نظر محاسباتی کاری چالش برانگیز است و توجه محققان زیادی را در دهه اخیر به خود جلب کرده است. بیشتر مقالات در این حوزه بر مدل‌سازی ویژگی‌های ساختاری تمرکز کرده‌اند. در اکثر این مقالات، روش‌ها جوامع را یکی پس از دیگری و به صورت سری یا نوبتی تشخیص می‌دهند. با هدف افزایش سرعت محاسبات، الگوریتم‌های تشخیص جامعه موازی‌سازی شدند. الگوریتم انتشار برچسب (LPA) به دلیل بازدهی زمانی، روش مؤثری برای موازی‌سازی است. در این مقاله، این الگوریتم به صورتی بازنویسی شده است که جوامع همپوشان را تشخیص دهد؛ در جوامع همپوشان یک فرد/گره می‌تواند همزمان به بیش از یک جامعه متعلق باشد. همچنین، مبتنی بر مدل نگاشت-کاهش الگوریتم جدید پیاده‌سازی شده است. آزمایش‌های طراحی شده نشان می‌دهد که الگوریتم پیاده‌سازی شده از الگوریتم‌های مشابه تشخیص جوامع همپوشان مانند LPA،SLPA وCOPRA بر اساس معیار ماژولاریتی کارکرد بهتری دارد.