مروری بر الگوریتم های تشخیص جامعه

بخش اول

چرا تشخیص جامعه؟

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

تشخیص جامعه در مقابل خوشه بندی

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

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

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

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