|
Title
|
ارائه یک الگوریتم بهینه تشخیص گروه در شبکه های اجتماعی با استفاده از خوشه بندی
|
|
Type of Research
|
Thesis
|
|
Keywords
|
شبکه های پیچیده، شبکه های اجتماعی ، تشخیص انجمن، قدرت نود
|
|
Abstract
|
امروزه در حوزههای گوناگونی همچون علوم کامپیوتر، زیست شناسی، شبکههای اجتماعی، شبکههای اطلاعاتی و اقتصاد، سیستمها به صورت گراف مدلسازی می شوند. گرافهای متناظر با سیستمهای واقعی دارای ویژگیهای توپولوژیکی بسیار متفاوت از شبکههای کلاسیک در نظریه گراف هستند. ویژگی برجسته این شبکههای واقعی، آن است که که توصیف یک مدل کلی برای ساختار، ویژگی و رفتار آنها غیرعملی میباشد. به دلیل همین پیچیدگی در مدل سازی و ساختار است که این گونه شبکهها، شبکههای پیچیده نامیده میشوند. یکی از مهمترین ویژگیهای قابل مشاهده در شبکههای پیچیده، وجود ساختارهای انجمنی است، به این معنا که در چنین شبکههایی می توان گرهها را به مجموعههایی جداگانه افراز نمود، به طوری که گرههای داخل هر مجموعه توسط تعداد زیادی یال به هم متصل باشند و در مقابل، تعداد بسیار کمتری یال، بین گرههای متعلق به مجموعههای متفاوت موجود باشد. از طرف دیگر افزایش روزافزون اندازه شبکههای پیچیده واقعی، نیازمند طراحی الگوریتمهای هر چه سریعتر جهت شناسایی ساختارهای انجمنی میباشد.یکی از الگوریتم های محبوب در این زمینه، الگوریتم انشار برچسب گذاری(LPA) می باشد. این الگوریتم با مرتبه زمانی خطی، استفاده از اطلاعات محلی، عدم وابستگی به هیچ پارامتر آزاد و بهینه سازی نکردن تابع خاصی جزء محبوب ترین الگوریتم تشخیص انجمن در چند سال اخیر بوده است. این الگوریتم با تمام ویژگی های خوبی که دارد از مشکلات مانند ناپایداری و همچنین کیفیت پایین به خاطر تشکیل انجمن ها بزرگ رنج می برد. در پایان نامه برای بهبود الگوریتم LPA دو راهکار پیشنهاد شده است که در این راهکارهای ارایه شده ویژگی هایLPA را حفظ کرده ایم و مشکلات ناپایداری و تشکیل انجمن های بزرگ را به خاطر رفتار تصادفی که دارد حذف کرده ایم. در روش های ارایه شده از اهمیت نودهای هسته برای انتخاب نود برای بروزرسانی و از اهمیت لینک های بین نودها برای قانون بروزرسانی استفاده کرده ایم.و با این راهکارهای ارایه شده الگوریتمLPA به پایداری و افزایش کیفیت انجمن دست پیدا کرده است.پس الگوریتم های ارایه شده با مرتبه زمانی خطی، استفاده از اطلاعات محلی، عدم وابستگی به هیچ پارامتر آزاد، پایداری و کیفیت بالا در تشخیص انجمن جزء بهترین الگوریتم های تشخیص انجمن به حساب خواهند آمد.
|
|
Researchers
|
Kamal Berahmand (Student)، Asgarali Bouyer (Primary Advisor)، Seyed Mahmoud Sheikholeslami Kavkani (Advisor)
|