ویرگول
ورودثبت نام
محمد فاتحی
محمد فاتحیعلاقه مند به تحلیل داده و داده کاوی. لینکدین:https://www.linkedin.com/in/mohammad-fatehi-09654062/
محمد فاتحی
محمد فاتحی
خواندن ۱ دقیقه·۵ سال پیش

معیار ماژولاریتی در خوشه بندی گراف

متد Louvain یک متد نسبتا سریع برای پیدا کردن گروه ها در شبکه های بزرگ است.

در این متد با استفاده از روش های حریصانه بر روی ماژولاریتی آن را بهینه کرده و به خوشه بندی راس های گراف می پردازد.
این بهینه سازی در دو مرحله انجام می شود:

  1. با بهینه سازی محلی متد به دنبال گروه های کوچک میگردد.
  2. سپس با ادغام گروه های کوچک که توانایی ایجاد گروه های بزرگتر را دارند خوشه بندی را ادامه می دهد.

این مراحل را مرتبا تکرار می شود تا به مقدار ماکزیمم ماژولاریتی برسیم.

در این پست قصد داریم یک مثال را پیاده سازی کنیم. معیار ماژولاریتی به صورت زیر محاسبه می شود:

گراف زیر را در نظر بگیرید:

ماتریس مجاورت گراف بالا به صورت زیر است:

فرض کنید گره های 1 و 3 و 4 متعلق به بخش الف و 2 و 5 نیز متعلق به بخش ب باشد. مقدار m نیز برابر 5 و درجه همه گره ها برابر 2 است. همچنین اگر دو گره در یک بخش باشند مقدار تابع سیگما برابر یک و در غیر این صورت برابر صفر است.

مقدار ماژولاریتی را برای گره یک محاسبه می کنیم:

در ادامه این معیار برای همه گره ها برابر است با

به همین ترتیب محاسبه ماژولاریتی با تغییر بخش ها ادامه پیدا می کند.

در نهایت گرافی که ایجاد می شود شامل دو بخش مجزا است. گره های 1و 2 و 5 در یک بخش و گره های 3 و 4 در بخش دیگر قرار می گیرند.

منابع

https://medium.com/walmartglobaltech/demystifying-louvains-algorithm-and-its-implementation-in-gpu-9a07cdd3b010

گراف
۴
۰
محمد فاتحی
محمد فاتحی
علاقه مند به تحلیل داده و داده کاوی. لینکدین:https://www.linkedin.com/in/mohammad-fatehi-09654062/
شاید از این پست‌ها خوشتان بیاید