روش های متعددی برای تشخیص تشکل های همپوشان در شبکه های ایستا ارائه شده اند اما تا بحال روش متمایزی برای شبکه های پویا مطرح نشده است. در اینجا به اختصار به برخی از این روش ها اشاره می‌کنیم:

نفوذ دسته: این روش بر این فرض استوار است که یک تشکل دربرگیرنده چندین مجموعه همپوشان از زیرگراف‌های کاملا متصل است و تشکل‌ها را با جستجو در دسته‌ه ای مجاور تشخیص می‌دهد. در ابتدا دسته‌هایی با اندازه k پیدا شده و در قدم بعدی گراف جدیدی بر اساس اتصال این دسته‌ ها را تشکیل می‌دهد که در آن هر گره نشان دهنده یک دسته است. بخش هایی که در گراف جدید اتصال بیشتری با یکدیگر دارند، یک تشکل را نشان می‌دهند. از آنجا که یک گره از گراف اصلی می‌تواند در چندین دسته حضور داشته باشد، بنابراین امکان تشخیص تشکل‌های همپوشان وجود خواهد داشت. این روش برای شبکه‌هایی که اتصالات زیادی دارند مناسب است. مطالعات عملی نشان داده است که مقدار کوچک k ( بین ۳ تا ۶ ) می‌تواند جواب خوبی را به همراه داشته باشد. CFinder یکی از الگوریتم‌های مبتنی بر این روش است و می‌تواند با پیچیدگی زمانی چند جمله ای به حل مسئله بپردازد. این الگوریتم در کار روی شبکه‌های واقعی با اندازه بزرگ، معمولا با مشکل مواجه می‌شود.
افراز گراف و دسته بندی یال ها: در این روش بجای جستجوی مستقیم تشکل‌ها، اتصالات بین گره‌ها به چند مجموعه افراز می‌شوند. گره‌ای در گراف اصلی که اتصالات آن در بیش از یک مجموعه افراز شده باشد، به عنوان همپوشان تشخیص داده می‌شود. اگرچه این روش برای تشخیص همپوشانی منطقی به نظر می‌رسد اما تضمینی وجود ندارد که تشخیص از روی یال ها نتایج بهتری نسبت به بررسی خود گره‌ها ارائه دهد، زیرا این روش تعریف روشنی از تشکل‌ها ندارد. CDAEO یکی از الگوریتم‌هایی است که بر پایه این روش طراحی شده‌اند.
بسط محلی و بهینه سازی: این روش بر اساس توسعه تشکل‌های طبیعی یا تشکل‌های جزیی استوار است. همچنین برای تشخیص کیفیت تشکل‌های مشخص شده از تابعی محلی استفاده می‌کند. یکی از نقاط ضعف این روش این است که کیفیت تشکل‌های نهایی شناسایی شده و نتایج به انتخاب هسته‌های اولیه بستگی دارد. البته روش‌هایی برای انتخاب هوشمندانه هسته‌های اولیه نیز ارائه شده است که تا حدی به رفع این مشکل کمک می‌کند. LFM، OSLOM و GCE نمونه‌هایی از الگوریتم‌های طراحی شده بر اساس این روش هستند.
تشخیص فازی: در این روش، برای هر گره یک بردار از درجه عضویت‌های آن در تشکل‌های مختلف محاسبه می‌شود. هدف این روش تعیین مناسب‌ترین مقادیر عضویت^[۹۵] در تشکل‌ها برای هر گره، با بهره گرفتن از کمینه کردن یک تابع خطا می‌باشد. یکی از نقاط ضعف این روش، نیاز به انتخاب تعداد تشکل‌ها به عنوان یک پارامتر از ابتدا می‌باشد. برای حل این مشکل راه‌هایی از جمله اجرای الگوریتم به ازای مقادیر مختلف برای تعداد تشکل‌ها، تا جایی که جواب به دست آمده بهبود نیابد، ارائه شده است. MOSES از جمله الگوریتم‌هایی است که بر اساس روش تشخیص فازی طراحی شده‌اند.
الگوریتم های پویا و مبتنی بر عامل: انتشار برچسب نمونه‌ای از الگوریتم‌های پویا است که در آن گره‌هایی که یک برچسب را دارند یک تشکل را تشکیل می‌دهند و هر گره می‌تواند دارای چندین برچسب باشد. روش به این صورت است که در ابتدا به هر گره برچسبی (معمولا شناسه آن گره) نسبت داده می‌شود و در چندین مرحله این برچسب‌ها در شبکه گسترش یافته و برچسب‌هایی که طرفدار بیشتری دارند به عنوان برچسب یک تشکل شناخته می‌شوند. در برخی از نمونه‌ها، گره‌ها دارای حافظه‌ای می‌باشند که در آن اطلاعات برچسب‌هایی را که تا به حال مشاهده کرده‌اند نگهداری می‌کنند و از آن برای تصمیم‌گیری در مورد انتخاب برچسب بهره می‌برند. COPRA و SLPA دو نمونه از الگوریتم‌های پویا هستند.
همچنین روش‌های چند عامله^[۹۶] مبتنی بر تئوری بازی‌ها نیز ارائه شده است که در آن هر گره به عنوان یک عامل خودخواه شناخته شده و می‌تواند با توجه به تصمیم خود، به یک تشکل ملحق شده و یا از آن خارج شود. این فرایند زمانی خاتمه می‌یابد که گره‌ها به تعادل^[۹۷] برسند و تمایلی به تغییر در تشکل‌های خود نداشته باشند. زمان زیاد برای رسیدن به تعادل یکی از مشکلات این روش است. از الگوریتم‌هایی که بر اساس تئوری بازی‌ها طراحی شده‌اند، می‌توان به Game اشاره کرد.
روش های دیگر: علاوه بر موارد فوق، روش‌های متعددی با پیاده سازی مختلف وجود دارند که هر کدام دارای نقاط ضعف و قوت می‌باشند. برخی از این نقاط ضعف عبارتند از: زمان اجرای زیاد، حساسیت به شرایط اولیه، نیاز به تعیین مقادیر پارامترهای مختلف، عدم کارایی در گراف‌های با اتصال کم و عدم امکان مقیاس‌پذیری.
فصل سوم

فصل سوم: ارائه راه حل و روش های پیشنهادی

مقدمه

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

1. 1. روش اول برای بهبود کارایی الگوریتم SLPA که با توجه به نتایج منتشر شده، در حال حاضر یکی از بهترین الگوریتم های موجود برای تشخیص تشکل ها در شبکه های ایستا می‌باشد، ارائه شده است.

1. 1. روش دوم با رویکرد شبکه های پویا طراحی شده و هدف آن ارائه راهکاری برای تشخیص تشکل های همپوشان در شبکه های پویا است.

در ادامه، ابتدا نگاه دقیق تری به الگوریتم SLPA می‌کنیم و سپس دو روش پیشنهادی را به همراه تحلیل کارایی آنها ارائه می‌دهیم.

نگاهی دقیق تر به روش انتشار برچسب

همانطور که در فصل قبل اشاره شد، انتشار برچسب یکی از روش های تشخیص تشکل های همپوشان در شبکه های ایستا است که از کارایی خوبی برخوردار است. از آنجا که روش های پیشنهادی در این رساله، بر پایه انتشار برچسب طراحی شده اند، در اینجا به بررسی دقیق تر یک نمونه از الگوریتم های این روش به نام SLPA یا فرایند انتشار اطلاعات مبتنی بر گوینده-شنونده می‌پردازیم (۲۰).
الگوریتم SLPA نمونه ارتقا یافته ای از الگوریتم LPA است. در LPA، هر گره تنها یک برچسب را برای خود حفظ می‌کند و این برچسب در هر مرحله تکرار، با توجه به اطلاعات دریافتی از گره های همسایه، بروز رسانی می‌شود. پس از اتمام تکرارها، در پایان الگوریتم، تشکل های غیر همپوشان حاصل می‌شوند. یکی از راه هایی که می‌توان این روش را به گونه ای تغییر داد که بتواند برای تشکل های همپوشان نیز قابل استفاده باشد، این است که اجازه دهیم هر گره بیش از یک برچسب برای خود داشته باشد. الگوریتم SLPA از این ایده استفاده می‌کند.

الگوریتم

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

الگوریتم ۱: الگوریتم SLPA
به صورت خلاصه می‌توان عملکرد این الگوریتم را در سه مرحله تعریف کرد:

1. 1. در ابتدا حافظه هر گره، با برچسب همان گره (شناسه گره) مقداردهی می‌شود.

1. 1. سپس مراحل زیر تا زمان برآورده شدن شرط توقف به صورت تکراری ادامه می‌یابند:

      1. 1. یک گره به عنوان شنونده تعیین می‌شود.

       

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

       

      1. 1. گره شنونده یکی از برچسب های دریافت شده را بر اساس یک قانون دریافت مشخص می‌پذیرید و آن را به حافظه خود اضافه می‌کند. این انتخاب ممکن است بر اساس میزان فراوانی برچسب های دریافت شده باشد.

       

       

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

این الگوریتم از یک روش بروز رسانی غیر همزمان بهره می‌برد، به این صورت که هنگامی که یک گره حافظه خود را در زمان t بروز رسانی می‌کند، ممکن است برخی از همسایه های آن در زمان t و بعضی دیگر در زمان t-1 بروز رسانی شده باشند.
این ویژگی که هر گره دارای حافظه ای می‌باشد که مشاهدات خود را در آن ذخیره کرده و در هر بار تصمیم گیری، با مراجعه به حافظه خود، از اطلاعات گذشته برای تصمیم گیری فعلی استفاده می‌کند، قابلیتی است که در دیگر روش های انتشار برچسب به این شکل دیده نمی‌شود.
شرط خاتمه در این الگوریتم، به صورت ساده، با یک مقدار از پیش تعیین شده T مشخص می‌شود که حداکثر تعداد دفعات تکرار را نشان می‌دهد و با توجه به آزمایش های انجام شده معمولا عددی بزرگتر از ۲۰ در نظر گرفته می‌شود. این مسئله باعث می‌شود که شرط خاتمه، مستقل از اندازه شبکه و ساختار آن باشد.
در مرحله پردازش نهایی نیز، میزان تکرار برچسب هایی که در حافظه هر گره وجود دارند، میزان تعلق آن گره را به هر تشکل نشان می‌دهد. این میزان تعلق می‌تواند به صورت یک بردار فازی مورد استفاده قرار گرفته و یا حتی با انتخاب برچسبی با بیشترین فراوانی، تبدیل به یک روش برای تعیین تشکل های غیر همپوشان شود. اما به طور معمول، از یک عدد از پیش تعیین شده به عنوان آستانه پذیرش عضویت در تشکل استفاده می‌شود و برچسب هایی که احتمال حضور آنها در حافظه از این مقدار کمتر باشد، از حافظه گره حذف می‌شوند. در نهایت اگر بیش از یک برچسب در حافظه برخی از گره ها موجود باشد، تشکل های همپوشان نیز ممکن خواهند بود و این گره ها به عنوان گره های همپوشان شناسایی خواهند شد. همچنین می‌توان با حذف تشکل هایی که محیط در تشکل بزرگتری هستند نتایج بهتری به دست آورد.

تحلیل پیچیدگی زمانی

مقداردهی اولیه به حافظه گره ها نیاز به پیچیدگی زمانی O(n) دارد که در آن n نشانگر تعداد کل گره های شبکه است. حلقه تکرار الگوریتم نیز در صورتی که شبکه تنک باشد پیچیدگی زمانی O(Tn) دارد که در آن T تعداد دفعات تکرار و n تعداد کل گره های شبکه است. در غیر این صورت پیچیدگی زمانی O™ خواهد بود که در آن m تعداد کل یال های شبکه است. بنابراین می‌توان نتیجه گرفت که برای یک پیاده سازی ساده، پیچیدگی زمانی این الگوریتم نسبت به اندازه شبکه خطی است.

بهبود کارایی روش انتشار برچسب

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

الگوریتم

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

تصویر ۱۴: (a) یک نمونه از زیر شبکه های انتخاب شده به همراه تشکل های آن (b و c)

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

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

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

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