مسئله بزرگترین خوشه
مسئلهٔ بزرگترین خوشه
در حوزهٔ ریاضیاتی نظریه گراف، خوشه (clique) یک زیر مجموعه از راس‌های یک گراف (با یال‌های بی‌جهت) است که هر دو راس مجزا در آن به یکدیگر متصل باشند (بین آن‌ها یال موجود باشد). به عبارتی یک خوشه، یک زیرگراف کامل است. خوشه‌ها یکی از مفاهیم پایه‌ای نظریهٔ گراف‌ها هستند و از آن‌ها در بسیاری از مسائل استفاده می‌شود. گراف‌ها یکی از مهم‌ترین حوزه‌های مطالعاتی و کاربردی در علوم رایانه هم هستند و به دنبال آن، خوشه‌ها هم مورد توجه زیادی قرار می‌گیرند. علی‌رغم این که مطالعهٔ گراف‌های کامل و زیرگراف‌های کامل به دههٔ سوم قرن بیستم میلادی بازمی‌گردد، اما می‌توان گفت مطالعهٔ خوشه‌ها برای اولین بارها در نیمهٔ این قرن توسط دو دانشمند انجام شدند که می‌خواستند با استفاده از نظریهٔ گراف‌ها و مفهوم خوشه، گروه‌های انسانی‌ای که همگی با یکدیگر ارتباط دارند را مدل کنند (در ساده‌ترین صورت، یک گراف می‌تواند مدل‌سازی ای از روابط اجتماعی باشد: هر راس یک شخص است و دو شخص که با یکدیگر ارتباط داشته باشند، بین راس‌های متناظرشان یال وجود دارد. با این تعاریف، یک خوشه نشان‌دهندهٔ زیرمجموعه‌ای از افراد است که همگی با یکدیگر ارتباط دارند). مسئلهٔ چک کردن موجودیت خوشه‌ای با اندازهٔ مشخص در یک گراف، در دستهٔ مسائل ان‌پی کامل (NP-Complete) قرار می‌گیرد، یعنی برای آن هیچ الگوریتم شناخته‌ای که در زمان چندجمله‌ای قابل اجرا باشد وجود ندارد. با این وجود، الگوریتم‌های زیادی برای حل این مسئله و سایر مسائل مربوط به خوشه‌ها مورد مطالعه و بررسی قرار گرفته‌اند. در گسترهٔ وسیعی از مطالعات و پژوهش‌های علمی از نظریهٔ گراف‌ها و به دنبال آن از خوشه‌ها استفاده می‌شود. برای مثال در علوم اجتماعی محاسباتی برای مدل‌سازی گروه‌های دوستی و انسانی کاربرد فراوان دارد. همچنین در بیوانفورماتیک و شیمی محاسباتی نیز توجه زیادی به خوشه‌ها می‌شود.
خوشه چیست
در حوزهٔ ریاضیاتی نظریهٔ گراف‌ها، خوشه یک زیر مجموعه از راس‌های یک گراف (با یال‌های بی‌جهت) است که هر دو راس مجزا در آن به یکدیگر متصل باشند (بین آن‌ها یال موجود باشد). به عبارتی یک خوشه، یک زیرگراف کامل است. زیرگراف، گرافی است که مجموعهٔ راس‌هایش زیر مجموعهٔ راس‌های گراف مادر باشد و مجموعهٔ یال‌هایش هم زیرمجموعهٔ یال‌های گراف مادر باشد. گراف کامل گرافی است که بین هر دو راس مجزای آن، یال موجود باشد.
در ادامه، سه تعریف کلیدی و مهم را یادآوری می‌کنیم:
در منابع مختلف، ممکن است از نام‌گذاری‌ها و اصطلاحات متفاوتی استفاده کنند (سعی شده‌است در این صفحه از نام‌گذاری‌ها و اصطلاحاتی استفاده شود که رایج‌تر و تأیید شده‌تر هستند).
اندازهٔ یک خوشه: به تعداد راس‌های حاضر در یک خوشه گفته می‌شود.
خوشهٔ ماکسیمال: خوشه‌ای است که نمی‌توان با افزودن یک راس دیگر به راس‌های حاضر در خوشه، آن را بزرگتر کرد (اندازه‌اش را بیشتر کرد). به عبارتی، راس دیگری وجود ندارد که به همهٔ راس‌های حاضر در خوشه یال داشته باشد. در یک گراف ممکن است چندین خوشهٔ ماکسیمال داشته باشیم.
بزرگترین خوشه: در یک گراف، بزرگترین خوشه به معنای خوشه‌ای است که بیشترین اندازه را دارد.
درجهٔ یک راس: تعداد یال‌هایی که به یک راس متصل هستند.
از آنجایی که در یک خوشه همهٔ راس‌ها باید به یکدیگر متصل باشند، اگر مجوعه‌ای از راس‌ها به اندازهٔ n موجود باشد، می‌توان گفت در صورتی که درجهٔ همهٔ راس‌های موجود، بزرگتر مساوی با n-1 نباشد، این مجموعه از راس‌ها قطعاً تشکیل یک خوشه نمی‌دهند.
با توجه به این که یک خوشه، یک گراف کامل است، تعداد یال‌های موجود در این گراف باید n(n-1)/2 باشد.
اگر یک خوشه موجود باشد، این خوشه می‌تواند ماکسیمال نباشد، اگر درجهٔ تمام راس‌های آن از n-1 بزرگتر باشد.
مسائل پیدا کردن خوشه
در علوم کامپیوتر، مسائل پیدا کردن خوشه، مسائلی محاسباتی و الگوریتمی هستند که هدف آن‌ها، پیدا کردن خوشه‌های موجود در گراف داده شده بر اساس پارامترهای خواسته شدهٔ متفاوت است. این مسائل صورت‌های متفاوتی دارند، چندتا از رایج‌ترین‌هایشان در ادامه آمده‌اند:
مسئلهٔ پیدا کردن بزرگترین خوشه (خوشه‌ای با اندازهٔ بیشینه) در گراف داده شده،
پیدا کردن خوشه‌ای با بیشترین وزن در گراف وزن دار داده شده،
پیدا کردن همهٔ خوشه‌های ماکسیمال در گراف داده شده،
آیا در گراف داده شده خوشه‌ای با اندازه‌ای بزرگتر از اندازهٔ داده شده وجود دارد؟ (این مسئله از جنس مسئله تصمیم است که پاسخ‌شان بلی یا خیر است).
اکثر مسائل پیدا کردن خوشه راه حل‌های سرراست و آسان ندارند. مسئلهٔ چک کردن موجودیت خوشه‌ای با اندازهٔ مشخص در یک گراف، در دستهٔ مسائل ان‌پی کامل (NP-Complete) قرار می‌گیرد. مسئلهٔ پیدا کردن همهٔ خوشه‌های ماکسیمال در یک گراف هم‌زمانی از مرتبهٔ نمایی دارد. با این وجود، اگر در این مسائل فرض‌هایی در نظر گرفته شود و ورودی مسئله گراف‌هایی با حالاتی خاص باشند، الگوریتم‌های کارایی وجود دارند که این مسائل را حل می‌کنند.
برای پیدا کردن بزرگترین خوشه، یک راه حل استفاده از الگوریتم‌های جستجوی جامع (brute-force algorithms) است. در این الگوریتم‌ها به بررسی تمامی زیرگراف‌های موجود در گراف پرداخته می‌شود و کامل بودن یا نبودن آن‌ها چک می‌شود. الگوریتم‌های جستجوی جامع بسیار زمان‌بر هستند تا حدی که برای حل مسائل در دنیای واقعی کاربردی نیستند.
علی‌رغم این که هیچ الگوریتمی با زمان اجرای چند جمله‌ای برای این مسئله وجود ندارد، اما الگوریتم‌هایی بهتر و کاربردی‌تر از جستوی جامع برای این مسئله معرفی شده‌اند. برای نمونه، الگوریتم Bron–Kerbosch برای پیدا کردن همهٔ خوشه‌های ماکسیمال در گراف داده شده کاربرد دارد.