ارائه یک روش خوشه بندی محلی گراف بر مبنای الگوریتم گام تصادفی

سال انتشار: 1398
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 821

فایل این مقاله در 14 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

ITCT06_073

تاریخ نمایه سازی: 24 شهریور 1398

چکیده مقاله:

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

نویسندگان

علی کرمی

عضو هیات علمی گروه مهندسی کامپیوتر، دانشگاه شیخ بهایی، اصفهان، ایران

نسرین مظاهری

عضو هیات علمی گروه مهندسی کامپیوتر، دانشگاه شیخ بهایی، اصفهان، ایران