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

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

Keywords:

خوشه بندی گراف , گام تصادفی , personalized pagerank