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

Authorsعلیرضا احمدی,کوثر آذری آرانی,مهدی وحیدی پور
Conference Titleسومین کنفرانس ملی مهندسی کامپیوتر فناوری اطلاعات و پردازش داده ها
Holding Date of Conference۲۰۱۸-۱۰-۲۷ - ۲۰۱۸-۱۱-۰۶
Event Place1 - ایران
Presented byعلامه طباطبایی
PresentationSPEECH
Conference LevelNational Conferences

Abstract

الگوریتم‌‌هایی که برای تشخیص جوامع استفاده می‌شوند، به زمان و فضای ذخیره‌سازی بالایی نیاز دارند. در این مقاله یک روش فراابتکاری برای افزایش کارایی الگوریتم‌های تشخیص جامعه در شبکه‌های پیچیده پیشنهاد شده ‌است. این روش شامل یک پیش‌پردازش و یک پس‌پردازش است که بر روی الگوریتم‌های مختلف تشخیص جوامع قابل پیاده‌سازی است. یک الگوریتم مشخص تشخیص جوامع در شبکه‌های پیچیده را در نظر بگیرید. در فاز پیش‌پردازش و قبل از اعمال الگوریتم، گره‌هایی با درجه بالا فیلتر می‌شوند؛ یعنی الگوریتم آنها را در نظر نمی‌گیرد. بعد از تشخیص جوامع توسط الگوریتم مرحله پس‌پردازش انجام می‌شود. در این مرحله، گره‌های فیلتر شده به شبکه بازگردانده می‌شوند و در جوامع موجود جایابی می‌گردند. روش پیشنهادی در این مقاله بر روی 5 مجموعه داده با استفاده از الگوریتم Girvan-Newman از کتابخانه networkx پیاده‌سازی شده است. نتایج آزمایش‌ها بهبود 39.99 درصدی زمان پردازش تشخیص جامعه را نشان می‌دهد.

Paper URL

tags: تشخیص جوامع، الگوریتم گیروان-نیومن، شبکه‌های اجتماعی