مسئله بزرگترین خوشه

در حوزهٔ ریاضیاتی نظریه گراف، خوشه (clique) یک زیر مجموعه از راس‌های یک گراف (با یال‌های بی‌جهت) است که هر دو راس مجزا در آن به یکدیگر متصل باشند (بین آن‌ها یال موجود باشد). به عبارتی یک خوشه، یک زیرگراف کامل است. خوشه‌ها یکی از مفاهیم پایه‌ای نظریهٔ گراف‌ها هستند و از آن‌ها در بسیاری از مسائل استفاده می‌شود. گراف‌ها یکی از مهم‌ترین حوزه‌های مطالعاتی و کاربردی در علوم رایانه هم هستند و به دنبال آن، خوشه‌ها هم مورد توجه زیادی قرار می‌گیرند. علی‌رغم این که مطالعهٔ گراف‌های کامل و زیرگراف‌های کامل به دههٔ سوم قرن بیستم میلادی بازمی‌گردد، اما می‌توان گفت مطالعهٔ خوشه‌ها برای اولین بارها در نیمهٔ این قرن توسط دو دانشمند انجام شدند که می‌خواستند با استفاده از نظریهٔ گراف‌ها و مفهوم خوشه، گروه‌های انسانی‌ای که همگی با یکدیگر ارتباط دارند را مدل کنند (در ساده‌ترین صورت، یک گراف می‌تواند مدل‌سازی ای از روابط اجتماعی باشد: هر راس یک شخص است و دو شخص که با یکدیگر ارتباط داشته باشند، بین راس‌های متناظرشان یال وجود دارد. با این تعاریف، یک خوشه نشان‌دهندهٔ زیرمجموعه‌ای از افراد است که همگی با یکدیگر ارتباط دارند). مسئلهٔ چک کردن موجودیت خوشه‌ای با اندازهٔ مشخص در یک گراف، در دستهٔ مسائل ان‌پی کامل (NP-Complete) قرار می‌گیرد، یعنی برای آن هیچ الگوریتم شناخته‌ای که در زمان چندجمله‌ای قابل اجرا باشد وجود ندارد. با این وجود، الگوریتم‌های زیادی برای حل این مسئله و سایر مسائل مربوط به خوشه‌ها مورد مطالعه و بررسی قرار گرفته‌اند. در گسترهٔ وسیعی از مطالعات و پژوهش‌های علمی از نظریهٔ گراف‌ها و به دنبال آن از خوشه‌ها استفاده می‌شود. برای مثال در علوم اجتماعی محاسباتی برای مدل‌سازی گروه‌های دوستی و انسانی کاربرد فراوان دارد. همچنین در بیوانفورماتیک و شیمی محاسباتی نیز توجه زیادی به خوشه‌ها می‌شود.

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

مسئلهٔ پیدا کردن بزرگترین خوشه (خوشه‌ای با اندازهٔ بیشینه) در گراف داده شده،

پیدا کردن خوشه‌ای با بیشترین وزن در گراف وزن دار داده شده،

پیدا کردن همهٔ خوشه‌های ماکسیمال در گراف داده شده،

آیا در گراف داده شده خوشه‌ای با اندازه‌ای بزرگتر از اندازهٔ داده شده وجود دارد؟ (این مسئله از جنس مسئله تصمیم است که پاسخ‌شان بلی یا خیر است).

اکثر مسائل پیدا کردن خوشه راه حل‌های سرراست و آسان ندارند. مسئلهٔ چک کردن موجودیت خوشه‌ای با اندازهٔ مشخص در یک گراف، در دستهٔ مسائل ان‌پی کامل (NP-Complete) قرار می‌گیرد. مسئلهٔ پیدا کردن همهٔ خوشه‌های ماکسیمال در یک گراف هم‌زمانی از مرتبهٔ نمایی دارد. با این وجود، اگر در این مسائل فرض‌هایی در نظر گرفته شود و ورودی مسئله گراف‌هایی با حالاتی خاص باشند، الگوریتم‌های کارایی وجود دارند که این مسائل را حل می‌کنند.

برای پیدا کردن بزرگترین خوشه، یک راه حل استفاده از الگوریتم‌های جستجوی جامع (brute-force algorithms) است. در این الگوریتم‌ها به بررسی تمامی زیرگراف‌های موجود در گراف پرداخته می‌شود و کامل بودن یا نبودن آن‌ها چک می‌شود. الگوریتم‌های جستجوی جامع بسیار زمان‌بر هستند تا حدی که برای حل مسائل در دنیای واقعی کاربردی نیستند.

علی‌رغم این که هیچ الگوریتمی با زمان اجرای چند جمله‌ای برای این مسئله وجود ندارد، اما الگوریتم‌هایی بهتر و کاربردی‌تر از جستوی جامع برای این مسئله معرفی شده‌اند. برای نمونه، الگوریتم Bron–Kerbosch برای پیدا کردن همهٔ خوشه‌های ماکسیمال در گراف داده شده کاربرد دارد.

https://books.google.com/books?id=rwZLAgAAQBAJ&source=gbs_book_similarbooks