بعضی از این روش­ها فقط بر اساس ساختار لینک ارزیابی را انجام می­ دهند اما بعضی دیگر با وجود محتوا نیز قادر به ارزیابی الگوریتم هستند.
به­ طور کلی بخش بسیار کوچکی از مطالعات و تحقیقات در مبحث شناسایی تشکل­ها به آزمایشات کارایی و درست بودن الگوریتم­های پیشنهادی اختصاص داده شده است. دلیل این امر که خود یک نقص بزرگ در مطالعه­ این بخش از شبکه ­های اجتماع است، کمبود معیار­های ارزیابی مطمئن می­باشد. یعنی به دلیل کمبود معیار­های ارزیابی قابل اطمینان بسیاری از محققان صحت الگوریتم­های خود را بر روی داده ­های بسیار کوچکی آزمایش می­ کنند که ساختار تشکل موجود در آن­ها به راحتی با چشم قابل شناسایی است. نتیجه­ استفاده از این معیار­ها و داده ­های کوچک، زیاد شدن الگوریتم­های شناسایی تشکل­ها در شبکه ­های اجتماعی به علت عدم مقایسه درست است.
در این پایان نامه جهت ارزیابی الگوریتم پیشنهادی خود از معیار Modularity جهت بررسی فاز مبتنی بر لینک و معیار های Perplexity و Normalized Mutual Iinformation جهت بررسی کلی الگوریتم پیشنهادی CDBLC استفاده کرده­ایم که در ادامه به شرح این معیار­ها پرداخته­ایم.

معیار Modularity

اگر یک شبکه با تعدادی گره منفرد و لینک­های اتصالی که نشان دهنده یک درجه خاصی از تعامل بین گره ها می باشد نمایش داده شود، جوامع به عنوان گروهی از گره­های متراکم به هم پیوسته که با بقیه­ی شبکه به صورت پراکنده^[۱۷۴] متصل هستند تعریف می­شوند. از این رو، مشخص کردن تعریف جوامع در شبکه ضروری است چرا که جوامع ممکن است خواص کاملا متفاوتی از جمله درجه گره^[۱۷۵]، ضریب خوشه­بندی^[۱۷۶]، معیار مابین بودن^[۱۷۷]، تمایل به مرکزیت^[۱۷۸] و غیره در مقایسه با شبکه نرمال داشته باشد[۳۹]. ماژولاریتی از جمله معیارهای اندازه ­گیری است که در زمان حداکثر بودن، منجر به ظهور تشکل­ها در یک چنین شبکه­ داده شده­ای می­ شود.
زمانی که جواب حقیقی^[۱۷۹] برای مجموعه داده­ی موجود در دسترس نباشد کارایی الگوریتم­های مبتنی بر لینک با این معیار ارزیابی می­ شود. معیار Modularity در سال ۲۰۰۴ توسط Newman و Grivan برای سنجیدن بخش­^[۱۸۰]های تشکل­ها معرفی شد[۲۵].

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

. اگرچه این معیار دارای مشکلاتی است و زمانی که شبکه ها بسیار تنک باشند غیر قابل اعتماد است [۵۱ in alvari] اما به­هر حال از محبوبیت و معروفیت زیادی برخوردار است.
برای بخش­های تشکل معیار Modularity به صورت زیر تعریف می­ شود:

(۴-۱)

که مبین تمام گره­ها در شبکه اجتماعی است و نشان­دهنده گره­ها در در امین تشکل می­باشد. همچنین طبق تعریف آمده در [۳۴] داریم:

(۴-۲)

.ماژولاریتی نشان می­دهد یک شبکه چقدر شبیه ساختار تشکل­های پیشنهادی ساخته می­­شود نسبت به اینکه بخواهد با پردازش تصادفی ساخته شود. بنابراین بالاتر بودن این معیار نشان­دهنده ساختار تشکلی هست که بهتر شبکه اجتماعی مشاهده شده را بیان میکند.

معیار Normalized Mutual Information

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

(۴-۳)

نیز به صورت زیر تعریف می­ شود:

(۴-۴)

در اینجا و آنتروپی بخش­های و هستند. مقدار MI بین صفر و یک است و مقدار بیشتر MI نشان­دهنده این است که نتیجه­ اعلام شده توسط الگوریتم یعنی به جواب واقعی نزدیک­تر است. این معیار معمولا در شاخه­ های بازیابی اطلاعات کاربرد فراوانی دارد. [۴۰][۴۱][۱۸][۴۲]

معیار Perplexity

یک معیار سنجش کیفیت خوشه­بندی که به طبقه ­بندی^[۱۸۲] پیشین^[۱۸۳] داده ­ها احتیاج ندارد، احتمال^[۱۸۴] داده کنار گذاشته شده^[۱۸۵] تحت مدل آموزشی^[۱۸۶] است. به عبارت دیگر این معیار توانایی مدل را در تولید داده دیده نشده پیش ­بینی می­ کند. معمولا مقدار این احتمالات لگاریتمی مقادیر منفی بسیار بزرگی هستند. این معیار معمولا در پردازش زبان استفاده می­ شود. معیار Perplexity به صورت شهودی به این ترتیب تفسیر می­ شود: ” سایز واژگان^[۱۸۷] با توزیع کلمات یکنواخت^[۱۸۸] که یک مدل برای تولید یک مولفه^[۱۸۹] از داده ­های تست احتیاج دارد”[۴۳] مدلی که بهتر بتواند رشته کلماتی که پشت سر هم می­آ­یند را پیش ­بینی کند به احتمالات کمتری برای قرار دادن یک کلمه جدید در یک متن احتیاج دارد، بنابراین مقدار کمتر perplexity، بیان کننده­ خطای کمتر در ارائه­ کلمه­های موجود در اسناد آزمایشی تحت عناوین آموزشی است. به عبارت دیگر، مقدار کمتر Perplexity نشان دهنده Likelihood بیشتر مدل و بنابراین قدرت تولید کنندگی بیشتر مدل است[۴۴].
برای تشکل با رشته کلمات و تعداد مؤلفه­ی معیار Perplexity به صورت زیر تعریف می­ شود: