روش های تشخیص تشکل های همپوشان در شبکه های ایستا

نفوذ دسته: این روش بر این فرض استوار است که یک تشکل دربرگیرنده چندین مجموعه همپوشان از زیرگراف‌های کاملا متصل است و تشکل‌ها را با جستجو در دسته‌های مجاور تشخیص می‌دهد. در ابتدا دسته‌هایی با اندازه k پیدا شده و در قدم بعدی گراف جدیدی بر اساس اتصال این دسته‌ها را تشکیل می‌دهد که در آن هر گره نشان دهنده یک دسته است. بخش هایی که در گراف جدید اتصال بیشتری با یکدیگر دارند، یک تشکل را نشان می‌دهند. از آنجا که یک گره از گراف اصلی می‌تواند در چندین دسته حضور داشته باشد، بنابراین امکان تشخیص تشکل‌های همپوشان وجود خواهد داشت. این روش برای شبکه‌هایی که اتصالات زیادی دارند مناسب است. مطالعات عملی نشان داده است که مقدار کوچک k ( بین 3 تا 6 ) می‌تواند جواب خوبی را به همراه داشته باشد. CFinder یکی از الگوریتم‌های مبتنی بر این روش است و می‌تواند با پیچیدگی زمانی چند جمله ای به حل مسئله بپردازد. این الگوریتم در کار روی شبکه‌های واقعی با اندازه بزرگ، معمولا با مشکل مواجه می‌شود.

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

بسط محلی و بهینه سازی: این روش بر اساس توسعه تشکل‌های طبیعی یا تشکل‌های جزیی استوار است. همچنین برای تشخیص کیفیت تشکل‌های مشخص شده از تابعی محلی استفاده می‌کند. یکی از نقاط ضعف این روش این است که کیفیت تشکل‌های نهایی شناسایی شده و نتایج به انتخاب هسته‌های اولیه بستگی دارد. البته روش‌هایی برای انتخاب هوشمندانه هسته‌های اولیه نیز ارائه شده است که تا حدی به رفع این مشکل کمک می‌کند. LFM، OSLOM و GCE نمونه‌هایی از الگوریتم‌های طراحی شده بر اساس این روش هستند.

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

الگوریتم های پویا و مبتنی بر عامل: انتشار برچسب نمونه‌ای از الگوریتم‌های پویا است که در آن گره‌هایی که یک برچسب را دارند یک تشکل را تشکیل می‌دهند و هر گره می‌تواند دارای چندین برچسب باشد. روش به این صورت است که در ابتدا به هر گره برچسبی (معمولا شناسه آن گره) نسبت داده می‌شود و در چندین مرحله این برچسب‌ها در شبکه گسترش یافته و برچسب‌هایی که طرفدار بیشتری دارند به عنوان برچسب یک تشکل شناخته می‌شوند. در برخی از نمونه‌ها، گره‌ها دارای حافظه‌ای می‌باشند که در آن اطلاعات برچسب‌هایی را که تا به حال مشاهده کرده‌اند نگهداری می‌کنند و از آن برای تصمیم‌گیری در مورد انتخاب برچسب بهره می‌برند. COPRA و SLPA دو نمونه از الگوریتم‌های پویا هستند.

همچنین روش‌های چند عامله[2] مبتنی بر تئوری بازی‌ها نیز ارائه شده است که در آن هر گره به عنوان یک عامل خودخواه شناخته شده و می‌تواند با توجه به تصمیم خود، به یک تشکل ملحق شده و یا از آن خارج شود. این فرایند زمانی خاتمه می‌یابد که گره‌ها به تعادل[3] برسند و تمایلی به تغییر در تشکل‌های خود نداشته باشند. زمان زیاد برای رسیدن به تعادل یکی از مشکلات این روش است. از الگوریتم‌هایی که بر اساس تئوری بازی‌ها طراحی شده‌اند، می‌توان به Game اشاره کرد.

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

 

 

[1] Membership values

[2] Multi agent

[3] Equilibrium

دیدگاه‌ خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد.