طراحی الگوریتمی جدید برای تشخیص جامعه در شبکه های اجتماعی مبتنی بر آتوماتای یادگیر
چکیده:
این تحقیق شامل ارائه¬ی الگوریتم¬هایی جدید برای تشخیص جامعه در شبکه¬های اجتماعی مبتنی بر آتوماتای یادگیر است. شبکه¬های اجتماعی یکی از انواع شبکه¬های پیچیده است. شبکه¬های پیچیده مجموعه¬ای از گره¬ها و اتصالات میان آن¬ها هستند. در شبکه¬های اجتماعی افراد بهعنوان گره¬ها و ارتباطات اجتماعی آن¬ها بهعنوان اتصالات میان گره¬ها تعریف می¬شوند. در این شبکه¬ها، جامعه به مجموعه¬ای از گره¬ها گفته می¬شود که تراکم اتصالات داخلی آن¬ها زیاد و تراکم اتصالات متقابل آن¬ها کم باشد. تشخیص جوامع در شبکه¬های اجتماعی روشی مؤثر برای بهره¬گیری از اطلاعات این شبکه¬ها است که تاکنون الگوریتم-های متعددی برای آن ارائه شده است. در این تحقیق الگوریتم¬هایی جدید از ترکیب روش¬های پیشین کشف جوامع با آتوماتاهای یادگیر طراحیشده که بهمنظور بهبود نتایج و سرعت روش¬های پیشین است.
در روش¬های پیشنهادی، یک آتوماتای یادگیر به هر گره شبکه الحاق شده است؛ تعداد اقدام آتوماتاهای یادگیر ثابت و برابر با تخمین تعداد جوامع شبکه است. در هر مرحله، هر کدام از آتوماتاهای یادگیر یک اقدام از مجموعه اقدامات خود را انتخاب می¬کند. انتخاب هر یک از این اقدام¬ها بهمنزلهی انتساب برچسب آن جامعه به گره است. اقدام انتخابشده توسط هر آتوماتا بر اساس اقدام¬های انتخابی همسایگانش ارزیابی می¬شود. این ارزیابی به شکل محلی و سراسری انجام می¬شود. ارزیابی محلی از طریق معیار شباهتی مانند آدامیکآدار، ژاکارد و ... و همچنین از تطبیق برچسب گره¬های همسایه انجام می¬شود و ارزیابی سراسری از طریق معیار ماژولاریتی انجام می¬شود. نتیجه¬ی ارزیابی منجر به صدور پاداش و جریمه برای آتوماتاها است. با دریافت پاداش احتمال انتخاب مجدد اقدام انتخابی توسط آتوماتا، یا همان برچسب جامعه، افزایش می¬یابد و در غیر این صورت با دریافت جریمه احتمال این اقدام کاهش می¬یابد. با تکرار الگوریتم، اقدام بهینه مشخص می¬گردد تا آنجا که با تکرارهای بیشتر هیچ تغییری در برچسب انتخابی آتوماتای متناظر هر گره رخ نمی¬دهد و درنتیجه جوامع بهینه به¬عنوان خروجی الگوریتم مشخص می¬گردند. مقایسه نتایج حاصل از آزمایشهای انجامشده کارایی روش پیشنهادی ما را در مقایسه با روش-های پیشین نشان می¬دهد.