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

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

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

فرض کنید گره های 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