مشخصات پژوهش

عنوان	ارائه یک راهکار بسیارهدفه مبتنی بر الگوریتمهای تکاملی برای تشخیص جوامع
نوع پژوهش	پایان نامه
کلیدواژه‌ها	تشخیص جامعه بهینه سازی بسیار هدفه خوشه بندی گراف تشخیص جامعه همپوشان
چکیده	ساختار جوامع یکی از خاصیتهای مهم شبکههای پیچیده است که کشف آن نقش عمدهای در درک ساختار توپولوژیکی شبکه داشته و در حوزههای بسیاری از جمله علوم اجتماعی، زیستشناسی و دیگر علوم کاربرد دارد. در سالهای اخیر تشخیص جامعه توجه بسیاری از محققان را به خود جلب کرده است. به طورکلی یک جامعه به مجموعهای از گرههای گراف گفته میشود که ارتباطاتشان با یکدیگر متراکمتر از بقیهی گرههای گراف است. تاکنون روشهای تکاملی بسیاری برای مسئلهی تشخیص جوامع ارائه شدهاند که با چالشهایی مانند ناتوانی در شناخت جوامع با اندازههای مختلف، دقت پایین و نیاز به تعداد واقعی جوامع بهعنوان دانش پیشین روبرو هستند.در این پژوهش دو روش تکاملی مبتنی بر الگوریتم ژنتیک، برای مسئلهی تشخیص جامعه پیشنهاد شده است. تا به حال تشخیص جامعه به عنوان یک مسئله تکهدفه یا چندهدفه در رویکردهای مبتنی بر تکاملی مطرح شده است، ازآنجایی که هر هدف، جنبه ای از ویژگی شبکه را پوشش میدهد، تحقیق در مورد این مسئله با بیش از دو هدف میتواند منجر به یافتن بهترین ساختار جامعه شود. در روش پیشنهادی اول، که بر تشخیص جوامع مجزا تمرکز دارد، مسئلهی تشخیص جامعه به عنوان یک الگوریتم بسیارهدفه فرموله شده و با بهینهسازی هم-زمان چندین هدف سعی در پیدا کردن ساختار دقیقتر جامعه شده است. در روش پیشنهادی دوم، یک الگوریتم تکاملی مبتنی بر مفهوم کلیک برای تشخیص جوامع هم پوشان در شبکه های پیچیده پیشنهاد شده است. نوآوری روش پیشنهادی دوم تغییر بازنمایی مورداستفاده در روش اول است بهگونهای که قابل اعمال بر شبکههای همپوشان نیز باشد. هیچ یک از دو روش پیشنهادی نیازی به دانستن تعداد واقعی جوامع بهعنوان دانش پیشین ندارند.اثربخشی روش پیشنهادی اول با یک الگوریتم تکهدفه و یک الگوریتم چندهدفه بر هردو مجموعه-ی مصنوعی و واقعی مقایسه شده است که نتایج حاکی از آن است که الگوریتم فوق در شبکه های مصنوعی در مجموع 80% موارد و در شبکه های واقعی 75% موارد نسبت به دو روش دیگر برتر بوده است. روش پیشنهادی دوم نیز با سه الگوریتم شناختهشدهی تشخیص جوامع همپوشان مقایسه شده است که نتایج آزمایشات روی شبکههای مختلف، دقت معقول و کارایی مناسب روش دوم را در هر دو شبکهی مصنوعی و واقعی تأیید میکند.
پژوهشگران	علیرضا عبداله پوری (استاد مشاور)، پرهام مرادی دولت آبادی (استاد راهنما)، سحر طهماسبی (دانشجو)