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

چکیده مقاله

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