تکنیک های تشخیص جامعه

بخش دوم:

تکنیک های تشخیص جامعه

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

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

  

   

1-تشخیص جامعه لووان

الگوریتم تشخیص جامعه Louvain در ابتدا در سال 2008 به عنوان یک روش آشکارسازی سریع جامعه برای 

شبکه های بزرگ پیشنهاد شد.این رویکرد مبتنی بر مدولار بودن است، که سعی می‌کند تفاوت بین تعداد واقعی یال‌ها

 در یک جامعه و تعداد مورد انتظار لبه‌ها در جامعه را به حداکثر برساندبا این حال، بهینه سازی مدولاریت در یک شبکه

 NP-hard است، بنابراین باید از اکتشافی استفاده کرد. الگوریتم Louvain به دو فاز تکرار شونده تقسیم می شود.

 حرکت محلی گره ها)تجمیع شبکه(

الگوریتم با یک شبکه وزنی از N گره شروع می شود. در مرحله اول، الگوریتم یک جامعه متفاوت را به 

هر گره شبکه اختصاص می دهد.سپس برای هر گره، همسایگان را در نظر گرفته و با حذف گره خاص از جامعه

 فعلی و قرار دادن در جامعه همسایه، به دست آوردن مدولار بودن را ارزیابی می کند. اگر سود مثبت و حداکثر 

شود، گره در جامعه همسایه قرار می گیرد. اگر سود مثبتی وجود نداشته باشد، گره در همان جامعه باقی 

خواهدماند.این فرآیند به طور مکرر و برای همه گره ها اعمال می شود تا زمانی که هیچ بهبود دیگری وجود

 نداشته باشد.فاز اول الگوریتم Louvain زمانی متوقف می شود که ماکزیمم محلی مدولاریت به دست آید. در مرحله

 دوم، الگوریتم با در نظر گرفتن جوامعی که در فاز اول بهعنوان گره یافت می شوند، یک شبکه جدید می سازد.

 پس از تکمیل فاز دوم، الگوریتم فاز اول را مجدداً در شبکه حاصل اعمال خواهد کرد.این مراحل تا زمانی که

 تغییری در شبکه ایجاد نشود و حداکثر ماژولاریت به دست آید تکرار می شود.الگوریتم تشخیص جامعه

 Louvain جوامع جوامع را در طول فرآیند آشکار می کند. به دلیل سهولت اجرا و همچنین سرعت الگوریتم

 بسیار محبوب است.با این حال، یکی از محدودیت های اصلی الگوریتم استفاده از ذخیره سازی شبکه در

 حافظه اصلی است. استفاده از الگوریتم تشخیص جامعه Louvain با استفاده از کتابخانه cdlib پایتون در

 زیر آورده شده است.

from cdlib import algorithms
import networkx as nx
G = nx.karate_club_graph()
coms = algorithms.louvain(G, weight=’weight’, resolution=1., randomize=False)

 2. تشخیص جامعه سورپرایز

با توجه به محدودیت‌های مدولاریته، معیاری مبتنی بر احتمالات کلاسیک به نام Surprise برای

 ارزیابی کیفیت پارتیشن یک شبکه به جوامع معرفی شده است. این الگوریتم تقریباً شبیه به الگوریتم

 تشخیص جامعه Louvain است با این تفاوت که به جای مدولار بودن از شگفتی ها استفاده می کند.گره ها

از یک جامعه به جامعه دیگر منتقل می شوند به طوری که شگفتی ها حریصانه بهبود می یابند. این 

رویکرد احتمال وجود یک پیوند در یک جامعه را در نظر می گیرد. استفاده از سورپرایز در محدوده

 بسیاری از جوامع کوچک و استفاده از مدولاریت در محدود تعداد کمی از جوامع بزرگ به خوبی کار 

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

شده است.

from cdlib import algorithms
import networkx as nx
G = nx.karate_club_graph()
coms = algorithms.surprise_communities(G)

3. تشخیص جامعه لیدن

در تحقیقات بعدی (2019)، V.A. تراگ و همکاران نشان داد که تشخیص جامعه Louvain تمایل 

به کشف جوامعی دارد که به صورت داخلی قطع شده اند(جامعه های بد مرتبط).درالگوریتم

 Louvain، انتقال یک گره که به عنوان پل بین دو جزء در یک جامعه عمل کرده است،به یک 

جامعه جدید ممکن است جامعه قدیمی را قطع کند. اگر جامعه قدیمی بیشتر تقسیم شود،این مشکلی 

نخواهد بود. اما طبق گفته تراگ و همکاران، این چنین نخواهد بود. گره های دیگر در جامعه

 قدیمی به دلیل ارتباطات قوی به آن اجازه می دهند تا به عنوان یک جامعه واحد باقی بماند. 

همچنین به گفته آنها، لووین تمایل به کشف جوامع مرتبط بسیار هفتگی دارد.بنابراین، آنها

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

 متصل هستند.علاوه بر فازهای مورد استفاده در الگوریتم Louvain، لیدن از یک فاز دیگر استفاده 

می کند که سعی می کند پارتیشن های کشف شده را اصلاح کند. 

سه فاز در الگوریتم لیدن عبارتند از:

 حرکت محلی گره ها

اصلاح پارتیشن ها

تجمیع شبکه بر اساس پارتیشن های تصفیه شده

در مرحله پالایش، الگوریتم سعی می کند پارتیشن های تصفیه شده را از پارتیشن های

 پیشنهادی فاز اول شناسایی کند. جوامع پیشنهاد شده توسط فاز اول ممکن است در مرحله

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

و ممکن است یک گره را با یک جامعه به طور تصادفی انتخاب شده ادغام کند که عملکرد

 کیفیت را افزایش می دهد. این تصادفی بودن امکان کشف فضای پارتیشن را به 

طور گسترده تر می دهد. همچنین در مرحله اول، لیدن رویکرد متفاوتی را به لووین 

دنبال می کند. لیدن به جای بازدید از تمام گره‌های شبکه پس از تکمیل اولین بازدید

 از همه گره‌ها، فقط از گره‌هایی بازدید می‌کند که همسایگی آنها تغییر کرده است.

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

در زیر آورده شده است.

from cdlib import algorithms
import networkx as nx
G = nx.karate_club_graph()
coms = algorithms.leiden(G)

4. تشخیص جامعه Walktrap

Walktrap روش دیگری برای تشخیص جامعه بر اساس پیاده روی تصادفی است که در آن 

فاصله بین رئوس از طریق پیاده روی تصادفی در شبکه اندازه گیری می شود.

 Walktrap یک الگوریتم کارآمد است که در پیچیدگی زمانی O(mn²) و در بدترین حالت

 پیچیدگی فضای O(n²) اجرا می شود. اما در بیشتر سناریوهای دنیای واقعی، Walktrap در

 O((n²) log n) پیچیدگی زمانی و O(n²) پیچیدگی فضایی اجرا می شود. شهود اصلی این الگوریتم

 این است که پیاده‌روی‌های تصادفی روی یک گراف/شبکه ​​تمایل دارند در بخش‌های بهم پیوسته

 مرتبط با جوامع به دام بیفتند. Walktrap از نتیجه پیاده روی تصادفی برای ادغام جوامع جداگانه

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

 کیفیت موجود ارزیابی کرد. این می تواند مانند ماژولار بودن در تشخیص جامعه Louvain

 یا هر معیار دیگری باشد.استفاده از الگوریتم تشخیص جامعه Walktrap با استفاده از کتابخانه

 cdlib پایتون در زیر آورده شده است.

from cdlib import algorithms
import networkx as nx
G = nx.karate_club_graph()
coms = algorithms.walktrap(G)

نتیجه

تشخیص جامعه در درک و ارزیابی ساختار شبکه های بزرگ و پیچیده بسیار کاربردی است.

 این رویکرد از ویژگی‌های لبه‌ها در نمودارها یا شبکه‌ها استفاده می‌کند و از این رو 

برای تحلیل شبکه به جای رویکرد خوشه‌بندی مناسب‌تر است. الگوریتم های خوشه بندی تمایل دارند

 تا گره های محیطی منفرد را از جوامعی که باید به آن تعلق داشته باشند جدا کنند. الگوریتم های 

مختلفی برای تشخیص جامعه شبکه پیشنهاد و پیاده سازی شده است. هر یک از اینها بسته به ماهیت

 شبکه و همچنین دامنه مشکل اعمال شده دارای مزایا و معایب مختلفی هستند.

References

[1] Girvan, Michelle & Newman, Mark. (2001). “Community structure in social and biological networks,” proc natl acad sci. 99. 7821–7826.

[2] Blondel, V., Guillaume, J., Lambiotte, R. and Lefebvre, E., 2008. Fast unfolding of communities in large networks. IOPscience.

[3] Traag, V., Aldecoa, R. and Delvenne, J., 2015. Detecting communities using asymptotical surprise. PHYSICAL REVIEW.

[4] V. A. Traag, L. Waltman, and N. J. van Eck, “From Louvain to Leiden: guaranteeing well-connected communities,” Sci. Rep., vol. 9, no. 1, pp. 1–12, 2019, doi: 10.1038/s41598–019–41695-z.

[5] Pons, P. and Latapy, M., n.d. Computing communities in large networks using random walks.