تشخیص شبکه‌های چگال از شبکه‌های شبه‌درختی برای پیش‌بینی لینک بر مبنای معیارهای همگنی و ناهمگنی

Authorsمهرداد رفیعی پور,زهرا عبدالعلی زاده,مهدی وحیدی پور
Conference Titleدومین کنفرانس ملی انفورماتیک ایران
Holding Date of Conference۲۰۲۰-۱۲-۲۳ - ۲۰۲۰-۱۲-۲۴
Event Place1 - تهران
Presented byپژوهشگاه دانش‌های بنیادی IPM
PresentationSPEECH
Conference LevelInternational Conferences

Abstract

پیش‌بینی لینک، وجود یا عدم وجود ارتباط بین دو موجودیت را بر اساس ویژگی¬های موجودیت¬ها و دیگر لینک¬های مشاهده شده در گراف بررسی می‌کند. الگوریتم¬های پیش¬بینی لینک متفاوتی تا بحال معرفی شده‌اند. این مقاله دو نوع الگوریتم پیش¬بینی لینک را برای شبکه¬های خلوت و چگال بررسی می‌کند؛ در ریاضیات، یک گراف چگال گرافی است که تعداد یال‌های آن نزدیک به بیشینه تعداد یال‌ها باشد و در مقابل یک گراف با کمینه‌ی تعداد یال‌ها یک گراف خلوت است. در این مقاله مقدار ضریب خوشگی برای گراف¬ها با ساختار همگنی و ناهمگنی متفاوت محاسبه شد. سپس بهترین الگوریتم پیش‌بینی لینک برای آن گراف‌ها مشخص شد. در نتیجه، مقداری از ضریب خوشگی بدست آمد که با استفاده از آن می¬توان الگوریتم مناسب برای پیش¬بینی لینک در شبکه را تشخیص داد. به این دلیل که تعداد گراف کافی برای بدست آوردن مقدار مناسب ضریب خوشگی وجود نداشت، روشی را برای تولید گراف تصادفی معرفی کردیم و با استفاده از آن، نقطه مرزی برتری الگوریتم¬های مبتنی بر همسایه مشترک و الگوریتم¬های مبتنی بر درجه نود گراف را بدست آوردیم.

Paper URL

tags: 'گراف شبه درختی، همگنی، ناهمگنی، گراف، شبکه، پیش‌بینی لینک، باراباسی-البرت، ضریب خوشگی، همسایه مشترک