الگوریتم درشت‌سازی گراف

**الگوریتم درشت‌سازی گراف** (به انگلیسی: Graph Coarsening Algorithm) خانواده‌ای از الگوریتم‌های فراابتکاری است که برای کاهش اندازه و پیچیدگی یک گراف بزرگ، ضمن حفظ ویژگی‌های ساختاری کلیدی آن، به کار می‌رود. این الگوریتم‌ها هسته اصلی **چارچوب‌های چندسطحی** (Multilevel Frameworks) را تشکیل می‌دهند که مسائل بهینه‌سازی پیچیده بر روی گراف‌های عظیم را به مسائلی کوچک‌تر و قابل حل تبدیل می‌کنند.

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

## مفاهیم اصلی
هدف اصلی درشت‌سازی، ساخت دنباله‌ای از گراف‌ها G_0, G_1, \dots, G_k است که در آن G_0 گراف ورودی است و هر گراف G_{i+1} نسخه کوچک‌تری از G_i می‌باشد، به طوری که تعداد گره‌ها به شدت کاهش می‌یابد: |V_0| > |V_1| > \dots > |V_k|.

این فرایند بر دو عملیات اصلی استوار است:
# **تشکیل ابرگره‌ها:** در هر مرحله، گره‌های گراف G_i بر اساس یک استراتژی مشخص، به چند گروه افراز می‌شوند. هر گروه از گره‌ها در گراف بعدی G_{i+1} به یک ابرگره واحد تبدیل می‌شود.
# **تعیین ابریال‌ها:** یال‌های بین ابرگره‌ها (ابریال‌ها) در G_{i+1} بر اساس یال‌های بین گره‌های متناظر در G_i ایجاد می‌شوند. وزن یک ابریال معمولاً برابر با مجموع وزن یال‌هایی است که بین دو گروه از گره‌های متناظر وجود داشته است.

کیفیت درشت‌سازی به این بستگی دارد که گراف کوچک‌شده چقدر بتواند ویژگی‌های مهم گراف اصلی (مانند ساختار برش‌ها) را حفظ کند.

## استراتژی‌های درشت‌سازی
انتخاب گره‌ها برای ادغام، مهم‌ترین بخش الگوریتم است و تأثیر مستقیمی بر کیفیت راه‌حل نهایی دارد. این انتخاب معمولاً از طریق الگوریتم‌های **تطبیق** (Matching) در گراف انجام می‌شود.

### تطبیق یال سنگین (Heavy Edge Matching - HEM)
این روش یکی از مؤثرترین و پرکاربردترین استراتژی‌هاست که در بسته‌های نرم‌افزاری معروفی مانند **Metis** و **Scotch** استفاده می‌شود. در HEM، گره‌هایی که با یال‌های پروزن (سنگین) به هم متصل‌اند، برای ادغام اولویت دارند. منطق این استراتژی آن است که گره‌های با ارتباط قوی، به احتمال زیاد باید در یک بخش (Partition) یا خوشه باقی بمانند.

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

### تطبیق تصادفی (Random Matching - RM)
در این استراتژی، گره‌ها به صورت تصادفی با یکی از همسایگان خود جفت می‌شوند. این روش بسیار سریع است اما ممکن است ویژگی‌های ساختاری مهم گراف را نادیده بگیرد، زیرا یال‌های سنگین و سبک را به یک چشم می‌بیند. RM معمولاً در مواردی که سرعت بر کیفیت اولویت دارد یا گراف بدون وزن است، استفاده می‌شود.

## نقش در چارچوب افراز چندسطحی
درشت‌سازی به ندرت به تنهایی استفاده می‌شود و معمولاً فاز اول از یک چارچوب سه‌مرحله‌ای به نام **افراز چندسطحی** (Multilevel Partitioning) است. این چارچوب برای حل مسائل NP-سخت مانند افراز گراف بسیار مؤثر است.

# **فاز ۱: درشت‌سازی (Coarsening):** گراف اصلی به صورت تکراری درشت می‌شود تا به یک گراف کوچک و قابل مدیریت (معمولاً با چند صد گره) تبدیل شود.
# **فاز ۲: افراز اولیه (Initial Partitioning):** گراف کوچک نهایی با استفاده از یک الگوریتم دقیق افراز می‌شود. از آنجا که این گراف کوچک است، این مرحله به سرعت انجام می‌شود.
# **فاز ۳: پالایش و بازگشت (Uncoarsening and Refinement):** افراز به دست آمده به تدریج به گراف‌های بزرگ‌تر و اصلی‌تر برگردانده می‌شود. در هر مرحله بازگشت، مرزهای افراز با استفاده از الگوریتم‌های بهینه‌سازی محلی مانند الگوریتم کرنیگان-لین (Kernighan-Lin) پالایش می‌شود تا کیفیت برش بهبود یابد.

این رویکرد ترکیبی، به الگوریتم امکان می‌دهد هم دیدگاه کلی (Global) از ساختار گراف (در فاز درشت‌سازی) و هم دیدگاه محلی (Local) برای بهینه‌سازی دقیق (در فاز پالایش) داشته باشد.

## تکنیک‌های پیشرفته درشت‌سازی
با ظهور کاربردهای جدید در یادگیری ماشین و تحلیل داده‌های پیچیده، روش‌های درشت‌سازی سنتی با رویکردهای نوین تکمیل شده‌اند:

* **درشت‌سازی آگاه از ویژگی (Feature-Aware Coarsening):** در شبکه عصبی گرافی (GNN)، گره‌ها دارای بردار ویژگی هستند. این روش‌ها گره‌هایی را ادغام می‌کنند که نه تنها از نظر ساختاری نزدیک، بلکه از نظر ویژگی‌ها نیز مشابه باشند.
* **درشت‌سازی طیفی (Spectral Coarsening):** این روش‌ها تلاش می‌کنند ویژگی‌های طیفی گراف (مانند مقادیر ویژه و بردارهای ویژه ماتریس لاپلاسین) را در گراف درشت‌شده حفظ کنند. این ویژگی‌ها برای خوشه‌بندی و برش گراف اهمیت زیادی دارند.
* **درشت‌سازی مبتنی بر یادگیری ماشین:** در این رویکرد، از مدل‌های یادگیری، به‌ویژه شبکه‌های عصبی گرافی، برای یادگیری بهترین استراتژی ادغام گره‌ها استفاده می‌شود. مدل یاد می‌گیرد کدام گره‌ها باید ادغام شوند تا اطلاعات مفید برای یک وظیفه خاص (مانند طبقه‌بندی گره) حفظ شود.

## کاربردها
الگوریتم‌های درشت‌سازی در زمینه‌های مختلفی کاربرد دارند:

* **طراحی VLSI:** در طراحی مدارهای مجتمع بزرگ، یک مدار به صورت یک هایپرگراف مدل‌سازی می‌شود. افراز این هایپرگراف برای تخصیص بهینه منابع و کاهش سیم‌کشی ضروری است. درشت‌سازی هایپرگراف‌ها به حل این مسئله در مقیاس بزرگ کمک می‌کند.
* **[[پردازش تصویر]]:** تصاویر را می‌توان به صورت گراف مدل‌سازی کرد که در آن پیکسل‌ها گره و شباهت بین پیکسل‌ها وزن یال‌هاست. درشت‌سازی برای قطعه‌بندی تصویر (Image Segmentation) در مقیاس‌های مختلف به کار می‌رود تا نواحی معنادار در تصویر شناسایی شوند.
* **[[تحلیل شبکه‌های اجتماعی]]:** در شبکه‌های اجتماعی با میلیون‌ها کاربر، درشت‌سازی برای شناسایی جوامع (Community Detection)، یافتن کاربران تأثیرگذار و ساده‌سازی تحلیل شبکه استفاده می‌شود.
* **محاسبات علمی:** در شبیه‌سازی‌های علمی (مانند دینامیک سیالات)، مسائل روی یک مش بزرگ تعریف می‌شوند. برای حل این مسائل روی کامپیوترهای موازی، مش باید بین پردازنده‌ها تقسیم شود. درشت‌سازی گراف متناظر با مش، این فرآیند را به شکل مؤثری مدیریت می‌کند.
* **یادگیری ماشین روی گراف‌ها:** در شبکه‌های عصبی گرافی، عملیات درشت‌سازی (که در این زمینه به آن **Pooling** گفته می‌شود) برای کاهش ابعاد داده‌ها و یادگیری نمایش‌های سلسله‌مراتبی از گراف به کار می‌رود.

## مزایا و معایب
### مزایا
* **سرعت و کارایی:** درشت‌سازی اندازه مسئله را به شدت کاهش داده و الگوریتم‌های پیچیده را برای گراف‌های عظیم قابل اجرا می‌کند.
* **کیفیت بالا:** رویکرد چندسطحی با ترکیب دیدگاه سراسری و محلی، معمولاً راه‌حل‌های با کیفیت‌تری نسبت به الگوریتم‌های تک‌سطحی تولید می‌کند.
* **مقیاس‌پذیری:** این الگوریتم‌ها برای گراف‌هایی با میلیاردها یال نیز مقیاس‌پذیر هستند.

### معایب
* **از دست رفتن اطلاعات:** در فرایند ادغام گره‌ها، بخشی از جزئیات ساختاری گراف از بین می‌رود که ممکن است بر بهینگی راه‌حل نهایی تأثیر منفی بگذارد.
* **وابستگی به هیوریستیک:** کیفیت گراف درشت‌شده به شدت به استراتژی درشت‌سازی (مانند HEM) وابسته است و تضمینی برای بهینه بودن آن وجود ندارد.
* **پیچیدگی پیاده‌سازی:** پیاده‌سازی یک چارچوب کامل چندسطحی نسبت به الگوریتم‌های ساده‌تر، پیچیده‌تر است.

## جستارهای وابسته
* نظریه گراف
* افراز گراف
* شبکه عصبی گراف
* خوشه‌بندی
* الگوریتم کرنیگان-لین

## منابع

رده:الگوریتم‌های گراف
رده:الگوریتم‌های فراابتکاری
رده:رایانش موازی
رده:روش‌های بهینه‌سازی