• در این معادلات، و و به ترتیب آنتروپی متغیر تصادفی و می‌باشند. همچنین آنتروپی شرطی نسبت به همه ی اجزای تشکیل دهنده ی متغیر است. در نهایت آنتروپی شرطی نرمال سازی شده ی نسبت به خواهد بود.

نتایج آزمایش ها

در این بخش به ارائه نتایج عملکرد الگوریتم های مورد آزمایش می‌پردازیم. برای این منظور از دو مجموعه داده LFR (به عنوان مجموعه داده مصنوعی) و High school friendship (به عنوان مجموعه داده طبیعی) استفاده شده است. نتایج نیز بر اساس معیار NMI ارزیابی شده اند (۹).

نتایج آزمایش ها بر روی مجموعه داده های LFR

در آزمایش هایی که بر روی مجموعه داده های LFR انجام شده است، چندین نوع شبکه با پارامترهای مختلف بکار رفته اند.
در نمودار ۱، عملکرد الگوریتم ها به ازای مقادیر مختلف (از ۲ تا ۸ تشکل) برای تعداد تشکل های گره های همپوشان (O_m)، اندازه های مختلف شبکه (۱۰۰۰ و ۵۰۰۰ گره) و همچنین مقدار µ (۰.۰۱ و ۰.۰۳) بر حسب معیار NMI (محور عمودی) ارائه شده است. در کل می‌توان گفت که با افزایش مقدار µ که باعث پیچیده تر شدن ساختار شبکه می‌شود، نتایج تولید شده ضعیف تر خواهند بود. از سوی دیگر، با بزرگتر شدن اندازه شبکه از ۱۰۰۰ به ۵۰۰۰ گره، نتایج اندکی بهبود یافته است. همچنین با افزایش O_m از ۲ تا ۸ تشکل (محور افقی)، فرایند تشخیص تشکل ها پیچیده تر شده و نتایج افت کرده است.
در نمودار ۲، تاثیر میزان گره های همپوشان (O_n) و اندازه تشکل ها بر عملکرد الگوریتم ها در حالات مختلف، ارائه شده است. در دو نمودار آبی رنگ، میزان گره های همپوشان ۱۰% و در دو نمودار قرمز رنگ، ۵۰% از تعداد کل گره های شبکه (۵۰۰۰ گره) است. در دو نمودار نقطه ای، اندازه تشکل ها بین ۱۰ و ۵۰ (که با حرف s در کنار تعداد گره ها مشخص شده است،) و در دو نمودار مربعی، بین ۲۰ تا ۱۰۰ گره (b) متغیر است. همانطور که انتظار می‌رود، نتایج با افزایش تعداد گره های همپوشان، به طور قابل ملاحظه ای افت کرده است. افزایش اندازه تشکل ها نیز سبب افت عملکرد الگوریتم ها شده است.
در نمودارهای ۳ و ۴، نتایج همه الگوریتم ها برای دو شبکه LFR با میزان گره های همپوشان ۱۰%، اولی با اندازه تشکل های ۱۰ تا ۵۰ و دومی با ۲۰ تا ۱۰۰ گره آورده شده اند.
در نمودارهای ۵ و ۶، نتایج همه الگوریتم ها برای دو شبکه LFR با میزان گره های همپوشان ۵۰%، اولی با اندازه تشکل های ۱۰ تا ۵۰ و دومی با ۲۰ تا ۱۰۰ گره آورده شده اند.
در ادامه، نتایج حاصل از عملکرد الگوریتم ها بر روی شبکه های LFR با اندازه ها و پارامترهای مختلف، آورده شده است.

نمودار ۱: مقایسه تاثیر اندازه شبکه (N)، تعداد تشکل های گره های همپوشان (O_m) و پیچیدگی ساختار (µ) بر روی میزان NMI (محور عمودی) حاصل از عملکرد الگوریتم ها

نمودار ۲: مقایسه تاثیر میزان گره های همپوشان (O_n)، اندازه تشکل ها و تعداد تشکل های گره های همپوشان (O_m) بر روی میزان NMI (محور عمودی) حاصل از عملکرد الگوریتم ها

نمودار ۳: عملکرد الگوریتم ها بر روی شبکه با اندازه ۵۰۰۰ گره، µ=۰.۰۳، میزان گره های همپوشان ۱۰% و اندازه تشکل ها بین ۱۰ تا ۵۰ گره

نمودار ۴: عملکرد الگوریتم ها بر روی شبکه با اندازه ۵۰۰۰ گره، µ=۰.۰۳، میزان گره های همپوشان ۱۰% و اندازه تشکل ها بین ۲۰ تا ۱۰۰ گره

نمودار ۵: عملکرد الگوریتم ها بر روی شبکه با اندازه ۵۰۰۰ گره، µ=۰.۰۳، میزان گره های همپوشان ۵۰% و اندازه تشکل ها بین ۱۰ تا ۵۰ گره

نمودار ۶: عملکرد الگوریتم ها بر روی شبکه با اندازه ۵۰۰۰ گره، µ=۰.۰۳، میزان گره های همپوشان ۵۰% و اندازه تشکل ها بین ۲۰ تا ۱۰۰ گره

نتایج آزمایش ها بر روی مجموعه داده های واقعی

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

تصویر ۱۳: شبکه دوستی دانش آموزان دبیرستان و تشکل های آن

جدول ۲: نتایج حاصل از عملکرد الگوریتم های مورد آزمایش بر روی مجموعه داده شبکه دوستی دانش آموزان دبیرستان، به همراه تعداد تشکل های تشخیص داده شده، گره های همپوشان (یا تعداد آنها) و معیار NMI

تحلیل نتایج

با توجه به بررسی های انجام شده و نتایج به دست آمده از آزمایش ها، می‌توان نتیجه گرفت که الگوریتم های SLPA، OSLOM، LFM، COPRA و GCE در مقایسه با سایر الگوریتم ها، در شبکه های بزرگتر عملکرد بهتری داشته اند و الگوریتم های SLPA، LFM، CIS و Game در شبکه های تنک^[۹۴]، کارایی بهتری ارائه داده اند. همچنین COPRA، GCE و UEOC در برخی از شبکه ها، دچار تشخیص بیش از حد شده اند که این موضوع می‌تواند باعث کاهش دقت و بازدهی آنها شود.
علاوه بر ارزیابی هایی که به آنها اشاره شد، معیارهای دیگری نیز در انتخاب الگوریتم مناسب تاثیرگذار هستند. یکی از مهم ترین این معیارها، پیچیدگی زمانی الگوریتم است. روشی که بتواند با پیچیدگی زمانی کمتری به نتایج مطلوب برسد برای کاربردهای واقعی گزینه مناسب تری محسوب می‌شود. از آنجا که تحلیل های ارائه شده، تنها بر روی گراف های بدون وزن و بدون جهت ارائه شد، در مواردی که نیاز به تحلیل شبکه های وزن دار یا جهت دار باشد، الگوریتم هایی که امکان پوشش این نوع شبکه ها را نیز داشته باشند، توانایی بهتری خواهند داشت. برای نمونه، الگوریتم های SLPA و CPM امکان تطابق برای کار روی گراف های وزن دار و جهت دار را نیز دارا می‌باشند.

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

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

• هنوز زمینه های مطالعاتی زیادی در شبکه های ایستا وجود دارد.

• با یک فرض ساده، می‌توان یک شبکه پویا را به صورت یک سری از شبکه های ایستا در طول زمان در نظر گرفت.

• مجموعه داده هایی که مورد پذیرش عمومی بوده بتوان بر روی آنها مطالعه و آزمایش انجام داد، در حوزه شبکه های پویا بسیار کم و یا حتی غیر قابل دسترس است.

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

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

جمع بندی

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