Community Detection

انواع روش های استخراج جوامع

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

انواع روشهای استخراج جوامع

به طور کلی این روشها عبارتند از: 1-استفاده از پارامترهای ارزیابی کیفی و پارامترهای شباهت در استخراج جامعه؛ 2-استفاده از روشهای خوشه بندی؛ 3-بخش بندی گراف، 4-روشهای طیفی و 5-متدهای بیزین.

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

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

  • روشهای طیفی: روشهای طیفی نیز حجم زیادی از تحقیقات در این زمینه را شامل می شوند،چرا که اصولا نتایج این دسته از الگوریتمها در مقایسه با روشهای شباهت از کیفیت بالاتری برخوردار هستند.درر این روش براساس بردارهای ویژه ی ماتریس مجاورت یا ماتریس شباهت جوامع شناسایی می شوند به این صورت که k تعداد از برترین بردارهای ویژه به عنوان نقاط یک فضای k بعدی از گره های موجود شبکه تعریف می شوند و سپس الگوریتمهای کلاسیک خوشه بندی جوامع آنها را کشف می نماید،هر چند کیفیت این روش از روشهای خوشه بندی محض بیشتر می باشد ولی سربار محاسباتی بالایی نیز غالبا دارند.

  • متدهای بیزین: این دسته نیز غالبا با استفاده از توزیع دریکله به تشخیص جوامع کمک می کنند،این روش برای ایجاد جوامع مخصوصا از روی متون استفاده می شود.که جز پرهزینه ترین روشها از نظرر محاسبات نیز به شمار می روند.این روش به کمک احتمالات افراد را در جوامع عضو می سازد.استفاده از این راهکار در اکثر روشهای ترکیبی نیز مشاهده می شود.

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

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

به طور کلی برخی از چالش هایی متدهای تشخیص جوامع عبارتند از:

  1.  مشخص نبودن بهترین الگوریتم برای تشخیص جامعه متناسب با نوع شبکه:تعداد زیادی از الگوریتم ها توسط محققین معرفی شده اند ولی تنها بر روی یک تعداد محدودی از شبکه ها با تعداد نودهای کم ارزیابی گشته اند که این خود اثباتی بر صحیح و جامع بودن آنها در تمامی شبکه های اجتماعی نمی باشد.
  2.  پارامترهای اولیه ی ورودی برای الگوریتم ها: این پارامترها در بسیاری از موارد برای ما مشخص نیستند مثل تعداد جامعه ها،حداقل و حداکثر اعضای عضو هر جامعه،داشتن قابلیت هم پوشانی و ...
  3.  محاسبات زیاد در تعیین مسیرها برای دسته ای از الگوریتم ها و محدودیت های خوشه بندی برای دسته دیگری از این الگوریتم ها کیفیت نتایج خروجی را تحت تاثیر قرار خواهند داد.
  4. کارا نبودن برخی از روشها برای شبکه های بزرگ از نظر مقیاس پذیری

 با توجه به مطالب ذکر شده می توان منشا کاهش صحت تشخیص جوامع را در دو دلیل خلاصه نمود. 1.استفاده از منابع اطلاعاتی محدود در ایجاد شبکه 2.استفاده از راهکارهایی که به ذات محدودیتها و نواقصی در جهت تشخیص جوامع خواهند داشت.

نظرات (0)
امکان ثبت نظر جدید برای این مطلب وجود ندارد.