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

این الگوریتم دارای دو فاز اصلی است. در فاز اول که کشف^[۷۳] نام دارد به دنبال رئوسی با L’ ماکزیمم می­گردد و آن­ها را به گروه اضافه می­ کند. در فاز دوم که فاز تست^[۷۴] نام دارد هر یک از رئوس اضافه شده را مورد بررسی قرار می­دهد و تنها رئوسی که در شرط اول صدق می­ کنند نگه می­دارد و ما بقی را دور می­ریزد.
پیچیدگی این الگوریتم برابر با kd|S|) می­باشد. که در آن d میانگین درجات رئوس و k اندازه مجموعه­ D است. این الگوریتم قابلیت اجرا بر روی گراف­های درختی بسیاری هستند را ندارد. زیرا در این گراف­ها رئوس با درجه اندک بسیار مشاهده می­ شود. همچنین امکان گیر کردن در مینیمم (ماکزیمم) محلی وجود دارد.

بدون بهینه سازی هیچ معیاری

این روش­ها بر اساس بهینه‌سازی هیچ معیاری عمل نمی‌کنند و به دنبال وجود زیر اجزا ^[۷۵] با ساختار­های از پیش تعیین‌شده^[۷۶] می‌گردند[۲۹]. نمونه­ بارز این دسته روش Clique [29] می­یاشد که در گراف شبکه، برای پیدا کردن ساختار­هایی نظیر k-clique جستجو می­ کنند و بیان می­ کنند که تشکل­های موجود، با این ساختار­ها تناظر دارند. در علم کامپیوتر مسئله کلیک اشاره به یافتن زیر­گراف­های کامل دارد، یعنی مجموعه ­ای از عناصر که دو به دو به­هم متصل هستند.

روش­های مبتنی بر مدل

گروهی از روش­های مبتنی بر مدل ^[۷۷] نیز در دسته اول جای دارند. بسیاری از این روش­ها برای تخمین پارامتر­های مدل از مقادیر بسیار نزدیک^[۷۸] به پارامتر­ها استفاده می‌کنند که این روش­ها به دلیل وجود نویز^[۷۹] در دنیای واقعی پایدار و قابل‌اطمینان نیستند، اما در روش DSBM^[80] [۱۶]برای تخمین پارامترها از رفتار بیزی^[۸۱] استفاده‌شده که علاوه بر نشان دادن عدم قطعیت^[۸۲] در مقادیر پارامتر­ها نسبت به عوامل خطا ساز نیز پایدار­تر است.
نمونه­ دیگری از این روش، مدل GSB (بلوک تصادفی عمومی^[۸۳]) است. این مدل که نوعی از مدل بلوک تصادفی است، می تواند احتمال (likelihood) تولید لینک در شبکه ­های جهت­دار و یا بدون جهت را بر اساس ایده­ استفاده از لینک برای شناسایی جوامع را مدل کند. در اینجا نشان دهنده تعداد یال جهت­دار در شبکه می­باشد. همچنین فرض می­کنیم که یک جفت تشکل نهان^[۸۴] توسط هر لینک با احتمال تشکیل می­ شود. گره با احتمال توسط تشکل و گره با احتمال توسط تشکل نمونه­برداری می­شوند. در مدل GSB فرض می­ شود که احتمال ایجاد یک پیوند بین دو گره مرتبط است با وجود ارتباط بین خود جوامع. با این فرض، مدلGSB قادر به کشف جوامع به طور عمومی تر می­باشد. همچنین پارامتر این مدل توسط الگوریتم EM^[85] بدست می ­آید[۳۰] . نمایش گرافیکی این مدل در شکل ۲-۳ آورده شده است.
شکل ۲-۳- نمایش گرافیکی مدل GSB.
دایره­های توپر نشان دهنده مقادیر دیده شده و دایره­های توخالی نشان دهنده مقادیر پنهان هستند. خط پر به همراه فلش بین گره­های و نشان دهنده وجود یک یال جهت­دار بین آنها است. خط­چین­هایی که دو دایره را به هم مرتبط می­ کنند، بیان می­کنندکه رابطه بین این عناصر دیده نشده هستند و باید توسط مقادیر دیده شده یاد گرفته شوند. فلش­ها نشان­دهنده جهت رابطه هستند.

روش­هی مبتنی بر محتوا

در این قسمت به ارائه­ دو روش اکتفا می­کنیم.

روش ^[۸۶]CUT

این روش که از محتوای پست­های الکترونیکی برای شناسایی تشکل­ها استفاده می‌کند، نمونه ­ای از الگوریتم­های موجود برای دسته دوم است. در این روش تشکل­ها بر اساس ترکیب­های تصادفی از مدل کاربران که از علایق آن­ها به­دست می ­آید، مدل می­شوند. اما این روش از اطلاعات ارتباطات در گراف شبکه استفاده نمی‌کند، بنابراین مدل­هایی شبیه CUT برای زمانی که اعضای تشکل فعالانه باهم در ارتباط باشند مناسب هستند و در غیر این صورت جواب قابل قبولی ارائه نمی‌دهند[۵]. نمایش گرافیکی این روش در شکل ۲-۴ نشان داده شده است.
شکل ۲-۴- نمایش گرافیکی روش CUT.

روش LTCA^[87]

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

ارائه راه حل و روش­های پیشنهادی

مقدمه

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