• شرط دوم، در شبکه هایی که ساختار تشکل آن ها دارای همپوشانی نیست به صورت بیان می‌شود. اگر در شبکه ی مورد نظر، هم ساختارهای تشکل دارای همپوشانی و هم ساختارهای تشکل غیر همپوشان داشته باشیم، هر دو حالت مورد نظر از شرط دوم، برقرار می‌باشد.

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

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

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

• به طور کلی محققان شبکه های اجتماعی سه تعریف کلی را برای ساختار تشکل ارائه داده اند:

• محلی^[۴۵] : طبق این تعریف، هر تشکل مستقل از کل گراف ارزیابی می‌شود.

• جهانی^[۴۶] : در اینجا هر تشکل با توجه به کل گراف بررسی می‌شود.

• شباهت رأس^[۴۷] : تشکل ها را گروه هایی از رئوس شبیه به یکدیگر در نظر می‌گیرند.

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

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

روش نفوذ دسته^[۴۸]

روش نفوذ دسته بر این فرض استوار است که یک تشکل شامل مجموعه های همپوشانی از زیرگراف های کاملا متصل^[۴۹] است و با جستجو برای یافتن دسته های^[۵۰] مجاور، تشکل ها را تشخیص می‌دهد. این روش با تشخیص دسته های با اندازه k در شبکه آغاز می‌کند. پس از اینکه دسته ها شناسایی شدند، گراف جدیدی تشکیل می‌شود که در آن هر گره نمایانگر یک دسته با اندازه k می‌باشد. در صورتی که دو گره مجاور، k-1 عضو مشترک داشته باشند، این دو گره توسط یک یال به یکدیگر متصل می‌شوند. زیرگراف های متصل در گراف جدید، تشکل ها را شکل می‌دهند. از آنجا که یک راس می‌تواند در چندین دسته باشد، امکان همپوشانی بین تشکل های تشخیص داده شده، وجود خواهد داشت. این روش برای شبکه هایی که دارای بخش های متصل و فشرده هستند مناسب است. با توجه به نتایج بدست آمده در آزمایش ها، مقادیر کوچک برای پارامتر k (معمولا ۳ یا ۶) مناسب تر هستند.
CFinder یکی از الگوریتم هایی است که بر اساس نفوذ دسته پیاده سازی شده است. پیچیدگی زمانی^[۵۱] این روش در اغلب کاربردهای واقعی، چند جمله ای^[۵۲] است و معمولا در گراف های حاصل از شبکه های اجتماعی بزرگ کارایی ندارد (۱۰).
روش دیگر CPMw است که در آن یک مقدار مرزی به عنوان آستانه^[۵۳] برای شبکه های وزن دار استفاده می‌شود، به این صورت که تنها دسته های k تایی که مجموع درجات آنها از یک مقدار مشخص ثابت بیشتر باشد، می‌توانند در تشکل قرار گیرند (۱۱).
مفهوم روش های مبتنی بر نفوذ دسته، ساده است. این روش ها بیشتر شبیه تطبیق الگو^[۵۴] عمل می‌کنند تا تشخیص تشکل ها. یعنی بیشتر به دنبال یافتن ساختارهای محلی خاص در شبکه هستند.

روش افراز گراف^[۵۵] و دسته بندی یال ها^[۵۶]

ایده دیگری که برای تشخیص تشکل ها مطرح شده است، دسته بندی یال ها بجای گره ها است. در این روش ها، یک گره در گراف اصلی دارای همپوشانی است اگر یال های متصل به آن، این گره را در چندین تشکل مختلف قرار دهند (۱۲).
در این روش، یال ها از طریق خوشه بندی سلسله مراتبی^[۵۷] بر اساس تشابه یال^[۵۸]، افراز می‌شوند. با در نظر گرفتن دو یال e_ik و e_jk متصل به گره k، تشابه بین دو یال به صورت زیر تعریف می‌شود:

که در آن N_i تعداد همسایه های گره i به همراه خود آن است. سپس با بهره گرفتن از خوشه بندی سلسه مراتبی تک اتصالی^[۵۹]، ساختار درختی اتصالات^[۶۰] تشکیل می‌شود. برش این ساختار درختی در سطوح مختلف، تشکل های یال ها را بدست می‌دهد. پیچیدگی زمانی به صورت O(nk_max²) می‌باشد که در آن k_max حداکثر درجه راس در شبکه است.
در روش دیگری، شبکه به یک گراف یال وزن دار تصویر می‌شود، که گره های آن، یال های گراف اصلی هستند. سپس یکی از روش های تشخیص تشکل های غیر همپوشان، بر روی گراف اعمال می‌شود. تشکل های به دست آمده در واقع افراز یال های گراف اصلی هستند (۱۳).
اگرچه دسته بندی یال ها برای یافتن تشکل های همپوشان از لحاظ مفهومی منطقی به نظر می‌رسد، اما تضمینی وجود ندارد که این روش نسبت به روش های مبتنی بر گره، نتایج بهتری ارائه دهد. زیرا این قبیل الگوریتم ها نیز بر پایه تعریف دقیقی از تشکل استوار نیستند.

روش بسط محلی^[۶۱] و بهینه سازی^[۶۲]

الگوریتم هایی که از بسط محلی و بهینه سازی استفاده می‌کنند بر پایه گسترش یک تشکل طبیعی^[۶۳] یا یک تشکل جزیی^[۶۴] عمل می‌کنند. اغلب این روش ها یک تابع محلی سود^[۶۵] دارند که کیفیت تشکل ها را که به صورت گروهی از گره های متصل هستند، اندازه گیری می‌کند (۱۴).
در نمونه ای از این روش ها، ابتدا بر اساس معیارهایی، گره هایی که درجه بالاتری دارند، به عنوان هسته های اولیه ایجاد تشکل ها شناسایی می‌شوند. در قدم بعدی، این هسته ها به صورت تکراری، با افزودن یا حذف گره های دیگر گسترش می‌یابند تا جایی که نتیجه تابع محلی کیفیت، بهبود بیشتری نداشته باشد (۱۵). این تابع می‌تواند به صورت زیر تعریف شود:

در این فرمول، w^c_in و w^c_out مجموع وزن های داخلی و خارجی تشکل c هستند. پیچیدگی زمانی این روش در بدترین حالت به صورت O(n²) می‌باشد. کیفیت تشکل های تعیین شده به مقدار زیادی وابسته به کیفیت گره هایی دارد که در ابتدا به عنوان هسته تشکل ها تعیین شده اند. همچنین به دلیل اینکه در هنگام گسترش هسته های اولیه، امکان حذف گره ها نیز وجود دارد، ممکن است در برخی حالات، تشکل هایی به وجود بیایند که دارای گسستگی هستند. بنابراین در تکمیل این روش، در انتهای هر تکرار، شرط اتصال^[۶۶] هر یک از تشکل ها نیز بررسی می‌شود تا از عدم گسستگی هر تشکل اطمینان حاصل شود.
در روش های مشابه دیگر، ممکن است روش های دیگری از جمله انتخاب تصادفی برای انتخاب گره های اولیه استفاده شده و یا توابع دیگری برای اندازه گیری کیفیت تشکل ها در نظر گرفته شوند. در کل پیچیدگی زمانی این روش ها به صورت O(n_cs²) است که در آن n_c تعداد تشکل ها و s میانگین اندازه تشکل ها را نشان می‌دهد. در بدترین حالت، پیچیدگی زمانی O(n²) می‌باشد.

روش تشخیص فازی^[۶۷]

الگوریتم های تشخیص فازی تشکل ها، قدرت تعامل میان تمام گره ها و تشکل ها را به صورت عددی تعریف می‌کنند (۱۶). در این روش ها، برای هر گره یک بردار عضویت^[۶۸] محاسبه می‌شود که میزان تعلق آن را به هر یک از تشکل ها نشان می‌دهد. مشکلی که در این حالت به وجود می‌آید، تعیین اندازه بردار عضویت است که در واقع تعداد تشکل ها را نشان می‌دهد. این پارامتر معمولا به عنوان ورودی مسئله، از سوی کاربر تعیین شده و یا با انجام برخی پیش پردازش ها، به صورت تخمینی از روی داده ها مشخص می‌گردد. همچنین ممکن است این پارامتر در ابتدا با یک مقدار مشخص آغاز شده و در هر بار اجرا، تا جایی افزایش یابد که باعث بهبود بیشتر نتایج نشود.
در یکی از این روش ها، تشخیص تشکل های همپوشان، به صورت یک مسئله بهینه سازی شرطی غیر خطی^[۶۹] تعریف می‌شود. که با تکنیک های شبیه سازی حرارت^[۷۰] قابل حل است (۱۷). تابع هدفی^[۷۱] که باید کمینه گردد می‌تواند به صورت زیر باشد:

در این تابع، w_ij وزن از پیش تعریف شده و s^-_ij میزان اولیه تشابه بین دو گره i و j است و s_ij به صورت زیر تعریف می‌شود:

در فرمول بالا، a_ic درجه عضویت فازی^[۷۲] گره i در تشکل c را نشان می‌دهد.

روش الگوریتم های پویا^[۷۳] و مبتنی بر عامل^[۷۴]

در روش های انتشار برچسب^[۷۵]، گره هایی که دارای برچسب یکسان هستند، در یک تشکل قرار می‌گیرند (۱۸). از آنجا که این روش ها اجازه می‌دهند که یک گره بتواند بیش از یک برچسب داشته باشد، امکان قرار گیری گره ها در چندین تشکل و ایجاد تشکل های همپوشان وجود خواهد داشت.
در الگوریتم COPRA، در یک فرایند تکراری، هر گره میزان تعلق خود به تشکل ها را با میانگین گیری از اطلاعات همسایه های خود در هر مرحله انجام می‌دهد. همچنین یک میزان حداکثری برای تعداد تشکل هایی که یک گره می‌تواند در آنها عضو باشد در نظر گرفته می‌شود. در هر تکرار، پیچیدگی زمانی به صورت O(vm log(vm/n)) می‌باشد که در آن v حداکثر تعداد تشکل های یک گره، m مجموع تعداد کل یال ها و n تعداد گره ها می‌باشد (۱۹).
در روش SLPA که به معنی فرایند انتشار اطلاعات مبتنی بر گوینده-شنونده^[۷۶] است، برچسب ها در میان گره ها، به صورت جفتی بر مبنای یک سری قوانین تعامل، توزیع می‌شوند (۲۰). همچنین هر گره دارای حافظه ای است که اطلاعات که همان برچسب های دریافت شده هستند را در آن نگهداری می‌کند. میزان احتمال حضور یک برچسب در حافظه یک گره، قدرت آن برچسب و در واقع میزان تعلق گره به آن تشکل را نشان می‌دهد. در این روش نیازی به دانستن تعداد تشکل ها از ابتدای فرایند نیست. پیچیدگی زمانی این روش، خطی و به صورت O™ می‌باشد که در آن m تعداد یال ها و t حداکثر تعداد تکرارها می‌باشد. همچنین امکان تعریف این روش برای استفاده در گراف های وزن دار و جهت دار نیز وجود دارد.
در روش های دیگری نیز که بر اساس تئوری بازی^[۷۷] تعریف می‌شوند، تشکل ها به صورت تعادل های محلی ^[۷۸]Nash شکل می‌گیرند (۲۱). در این حالت، هر گره که به عنوان یک عامل^[۷۹] در نظر گرفته می‌شود، دارای یک تابع سود^[۸۰] و یک تابع ضرر^[۸۱] می‌باشد. همچنین هر عامل رفتاری خودخواهانه^[۸۲] دارد و می‌تواند سه عمل را انجام دهد: ورود به یک تشکل^[۸۳]، خروج از یک تشکل^[۸۴] و یا جابجایی بین دو تشکل^[۸۵]. هر عامل تلاش می‌کند با انجام ترکیبی از این اعمال، میزان سود خود را افزایش دهد. از آنجا که یک عامل اجازه عضویت در چندین تشکل را دارد، امکان همپوشانی تشکل ها نیز وجود خواهد داشت. پیچیدگی زمانی این روش تا زمان رسیدن به تعادل Nash به صورت O(m²) می‌باشد که در آن m تعداد یال های گراف است.

روش‌های دیگر

علاوه بر روش‌های فوق، روش‌های دیگری نیز مطرح شده‌اند که در پنج دسته فوق قرار نمی‌گیرند. به عنوان مثال، استفاده از تعاریف دیگری از جمله قرابت^[۸۶] (۲۲) و یا بکارگیری تصویر سازی^[۸۷] (۲۳) و غیره.
تنوع روش‌های ارائه شده در این حوزه و همچنین پیاده سازی مختلف از آنها بسیار زیاد است و هر کدام با ایده‌ای تلاش در حل مسئله تشخیص تشکل‌های همپوشان دارند. بدیهی است که هر کدام از این روش‌ها دارای نقاط ضعف و قوت می‌باشند. از جمله نقاط ضعف، می‌توان به زمان اجرای زیاد، حساسیت به شرایط اولیه، نیاز به تعیین مقادیر پارامترهای مختلف، عدم کارایی در گراف‌های با اتصال کم و عدم امکان مقیاس‌پذیری اشاره کرد.

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

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

جدول ۱: فهرست الگوریتم های انتخاب شده برای مقایسه در حوزه تشکل های همپوشان در شبکه های ایستا، به همراه مرجع، پیچیدگی زمانی و زبان پیاده سازی

مجموعه داده ها

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

مجموعه داده های مصنوعی^[۸۸]

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