مشخصات پژوهش

عنوان	تعیین جوامع با استفاده از الگوریتم بهبود یافته ی گسترش برچسب با شاخص های محلی در شبکه های اجتماعی
نوع پژوهش	پایان نامه
کلیدواژه‌ها	کشف جوامع، شبکه های اجتماعی، انتشار برچسب، شاخص های محلی، گره هسته
چکیده	یک شبکه پیچیده می تواند بسیاری از پدیده های دنیای واقعی را مدل سازی کند، شبکه های پروتئینی، شبکه های اینترنتی، شبکه های اطلاعاتی و شبکه های اجتماعی نمونه هایی از شبکه های پیچیده هستند. تجزیه و تحلیل شبکه های پیچیده مختلف را می توان با اهداف متفاوتی انجام داد. به عنوان مثال، در شبکه های اجتماعی، می توان روابط بین افراد را با کشف جوامع مختلف دوستان تجزیه و تحلیل کرد [1]. به عنوان مثال دیگری، تجزیه و تحلیل شبکه های پروتئین می تواند عملکرد پروتئینهای جدید را کشف کند یا در شبکه های اطلاعاتی با تجزیه و تحلیل صفحات موجود در وب، می توان صفحات وب مشابه را در یک جامعه گروه بندی کرد [2, 3]. در شبکه خرید آنلاین، با کشف جوامع، دسته های مختلفی از مشتریان کشف می شوند تا با توجه به نیازهای خود خدمات ارائه دهند. یک جامعه، زیرگرافی از گراف اصلی است که در آن تعداد زیادی اتصالات بین گره های داخل جامعه وجود دارد، در حالی که ارتباطات بین گره های یک جامعه با گره های سایر جوامع، کمتر است. اما، پیدا کردن ساختار جامعه ای که بتواند رضایت بخش باشد در شبکه های بزرگ مقیاس مانند شبکه های اجتماعی، به دلیل اندازه بزرگ شبکه و محدودیت های پیچیدگی زمانی، یک چالش سخت است [4, 5]. بنابراین، تشخیص جوامع برای تحلیل شبکه های اجتماعی آنلاین، اهمیت بسیاری دارد. به همین خاطر، امروزه توسعه الگوریتم هایی که بتوانند با سرعت مناسب و دقت کافی، تغییرات را به صورت فوری شناسایی کرده و جوامع را به صورت دقیق بازشناسایی کنند، مورد توجه قرار گرفته است [6]. با افزایش مداوم شبکه های اجتماعی، روش های سراسری برای تشخیص دقیق جوامع در شبکه های متوسط و بزرگ، مناسب نیستند، زیرا نیاز به زمان های محاسباتی بالایی دارند که استفاده عملی از آنها را غیرممکن می کند [7]. الگوریتم انتشار برچسب LPA، اولین الگوریتم با پیچیدگی زمانی تقریبا خطی در این حوزه است [8]. اما به دلیل مشکلات بارز LPA مانند ناپایداری شدید و عدم دقت لازم در برخی مواقع که ناشی از رفتارهای تصادفی در مراحل اولیه و شرایط Tie break است، رویکردهای متفاوتی ارائه شده اند تا کیفیت پایین جوامع کشف شده توسط این روش را بهبود بخشیده و یا ناپایداری را کاهش دهند [9]. اما اکثر این توسعه ها، پیچیدگی زمانی-فضایی الگوریتم را افزایش داده و عملکرد قابل قبولی ندارند. در این تحقیق، سعی می کنی
پژوهشگران	فرانک فتحی (دانشجو)، عسگر علی بویر (استاد راهنما)، علیرضا روحی (استاد مشاور)