رهيافت‌هايي مبتني بر جست‌وجوي محلي در الگوريتم‌هاي فرا ابتكاري براي تشخيص جوامع در شبكه¬هاي پيچيده

كارشناسي ارشد

تجزيه و تحليل ساختاري و عملكردي شبكه‌ها با استفاده از شناسايي جوامع آن‌ها يك مسئله مهم در بسياري از حوزه‌هاي تحقيقاتي از جمله علوم اجتماعي، علوم كامپيوتر، بيولوژي و فيزيك است. مسئله‌ي تشخيص جوامع يك مسئله‌ي NP-hard است. بنابراين يكي از راه‌هاي حل آن استفاده از روش‌هاي فرا ابتكاري است و در اين راستا روش‌هاي گوناگوني توسط محققان مختلف ارائه شده است. چالش اصلي اين روش‌ها زمان اجراي زياد و دقت كم آن‌هاست. به همين دليل، در اين تحقيق به ارائه دو روش نوين فرا ابتكاري براي تشخيص جوامع با استفاده از الگوريتم ژنتيك به نام‌هاي EGACD و MOGGA مي‌پردازيم. در اين الگوريتم‌ها از يك عملگر نوين جستجوي محلي، كه منجر به افزايش نرخ همگرايي و افزايش دقت مي‌شود، استفاده شده است. براي محدود كردن فضاي جستجو، از يك نمايش كه از اطلاعات ساختاري شبكه در فرآيند مقداردهي و بازتوليد جمعيت استفاده مي‌كند بهره برده‌ايم. علاوه بر اين، اين الگوريتم‌ها نيازي به دانستن تعداد جوامع شبكه در ابتداي كار ندارند. بسياري از الگوريتم‌هاي موجود تشخيص جوامع گراف محور هستند و در صورتي كه ساختار گراف پيچيده شود قادر به تشخيص دقيق جوامع نيستند. به همين دليل، در اين تحقيق همچنين به ارائه يك روش متفاوت تشخيص جوامع بر اساس اين فرضيه كه هر جامعه در برگيرنده‌ي يك زيرفضاي جدا در فضاي اقليدسي است مي‌پردازيم. به صورتي كه هر گره مي‌تواند به صورت تركيب خطي از گره‌هاي ديگري كه در همان زيرفضا هستند تعريف شود. اخيرا روشي تحت عنوان خوشه‌بندي قله‌هاي چگال براي خوشه‌بندي موثر و كاراي داده‌ها منتشر شده است. ما با الهام از اين روش، خوشه‌بندي را بر روي شبكه‌هايي كه به فضاي داده نگاشت شده‌اند اعمال كرده و آن را تحت عنوان روش پيشنهادي سوم ارائه مي‌دهيم. نتايج آزمايش‌هاي ما بر روي مجموعه داده‌هاي واقعي و مصنوعي نشان‌دهنده‌ي كارايي بيشتر الگوريتم‌هاي پيشنهادي از نظر دقت بيشتر در مقابسه با روش‌هاي موجود است. واژه‌هاي كليدي: تشخيص جوامع، جستجوي محلي، نگاشت زيرفضايي، خوشه‌بندي قله‌هاي چگال، خوشه‌بندي

192695

دانشگاه علم و صنعت ايران

نرم‌افزار

دكتر سعيد پارسا