مشخصات پژوهش

عنوان	ارائه یک الگوریتم بهینه تشخیص گروه در شبکه های اجتماعی با استفاده از خوشه بندی
نوع پژوهش	پایان نامه
کلیدواژه‌ها	شبکه های پیچیده، شبکه های اجتماعی ، تشخیص انجمن، قدرت نود
چکیده	امروزه در حوزه‎های گوناگونی همچون علوم کامپیوتر، زیست شناسی، شبکه‎های اجتماعی، شبکه‎های اطلاعاتی و اقتصاد، سیستم‎ها به صورت گراف مدل‎سازی می شوند. گراف‎های متناظر با سیستم‎های واقعی دارای ویژگی‎های توپولوژیکی بسیار متفاوت از شبکه‎های کلاسیک در نظریه گراف هستند. ویژگی برجسته این شبکه‎های واقعی، آن است که که توصیف یک مدل کلی برای ساختار، ویژگی و رفتار آن‎ها غیرعملی می‎باشد. به دلیل همین پیچیدگی در مدل سازی و ساختار است که این گونه شبکه‎ها، شبکه‎های پیچیده نامیده می‎شوند. یکی از مهم‎ترین ویژگی‎های قابل مشاهده در شبکه‎های پیچیده، وجود ساختارهای انجمنی است، به این معنا که در چنین شبکه‎هایی می توان گره‎ها را به مجموعه‎هایی جداگانه افراز نمود، به طوری که گره‎های داخل هر مجموعه توسط تعداد زیادی یال به هم متصل باشند و در مقابل، تعداد بسیار کمتری یال، بین گره‎های متعلق به مجموعه‎های متفاوت موجود باشد. از طرف دیگر افزایش روزافزون اندازه شبکه‎های پیچیده واقعی، نیازمند طراحی الگوریتم‎های هر چه سریع‎تر جهت شناسایی ساختارهای انجمنی می‎باشد.یکی از الگوریتم های محبوب در این زمینه، الگوریتم انشار برچسب گذاری(LPA) می باشد. این الگوریتم با مرتبه زمانی خطی، استفاده از اطلاعات محلی، عدم وابستگی به هیچ پارامتر آزاد و بهینه سازی نکردن تابع خاصی جزء محبوب ترین الگوریتم تشخیص انجمن در چند سال اخیر بوده است. این الگوریتم با تمام ویژگی های خوبی که دارد از مشکلات مانند ناپایداری و همچنین کیفیت پایین به خاطر تشکیل انجمن ها بزرگ رنج می برد. در پایان نامه برای بهبود الگوریتم LPA دو راهکار پیشنهاد شده است که در این راهکارهای ارایه شده ویژگی هایLPA را حفظ کرده ایم و مشکلات ناپایداری و تشکیل انجمن های بزرگ را به خاطر رفتار تصادفی که دارد حذف کرده ایم. در روش های ارایه شده از اهمیت نودهای هسته برای انتخاب نود برای بروزرسانی و از اهمیت لینک های بین نودها برای قانون بروزرسانی استفاده کرده ایم.و با این راهکارهای ارایه شده الگوریتمLPA به پایداری و افزایش کیفیت انجمن دست پیدا کرده است.پس الگوریتم های ارایه شده با مرتبه زمانی خطی، استفاده از اطلاعات محلی، عدم وابستگی به هیچ پارامتر آزاد، پایداری و کیفیت بالا در تشخیص انجمن جزء بهترین الگوریتم های تشخیص انجمن به حساب خواهند آمد.
پژوهشگران	کمال برهمند (دانشجو)، عسگر علی بویر (استاد راهنما)، سید محمود شیخ الاسلامی کاوکانی (استاد مشاور)