افراز گراف

در ریاضیات، مسئله افراز گراف بر روی داده‌هایی در قالب گراف (G=(V,E با V راس و E یال تعریف می‌شود به‌طوری‌که افراز گراف به مؤلفه‌های کوچکتری با ویژگی‌های خاص ممکن باشد. برای مثال، یک تقسیم‌بندی k-بخشی مجموعه رئوس را به k مؤلفه کوچکتر تقسیم می‌کند. افراز خوب به افرازی گفته می‌شود که تعداد یال‌های بین مؤلفه‌های مجزا از هم کم باشد. افراز یکریخت به نوعی از مسئله افراز گراف گفته می‌شود که تقسیم گراف به به مؤلفه‌ها به صورتی است که مؤلفه‌ها تقریباً هم اندازه باشند و اتصالات کمی بین مؤلفه‌های متفاوت وجود داشته باشد. مهم‌ترین کاربردهای افراز گراف در محاسبات علمی، تقسیم‌بندی قسمت‌های مختلف طراحی مدارهای VLSI و مدیریت زمانبندی کارها در سیستم‌های چندپردازنده‌ای، می‌باشد. اخیراً، استفاده از افراز یکریخت، به دلیل کاربردهای آن در خوشه بندی و یافتن گروه‌ها در شبکه‌های اجتماعی، شبکه‌های زیستی و شبکه‌های بیماری شناختی افزایش یافته‌است.

پیچیدگی مسئله

معمولاً مسئله افراز گراف در رده مسائل NP-سخت قرار می‌گیرد. راه حل این مسائل به صورت کلی از طریق روش‌های مکاشفه‌ای و تقریبی‌حاصل می‌شود. اما نشان داده می‌شود که افراز یک ریخت گراف یا افراز متعادل گراف به صورت NP-کامل می‌باشد که در ضریب متناهی از زمان قابل محاسبه است. حتی برای گراف‌هایی که نظیر درخت‌ها و شبکه‌ها که در رده خاصی قرار می‌گیرند هیچ الگوریتم تقریبی مستدلی وجود ندارد، مگر آن که P=NP باشد. شبکه‌ها از آنجهت که گراف‌هایی که از شبیه‌سازی روش اجزا محدود به دست می‌آیند را مدل می‌کند، می‌تواند یک مورد جالب در این زمینه باشد. زمانی که علاوه بر آنکه تعداد یال‌های بین مؤلفه‌ها تقریب زده شده‌است بلکه اندازه مؤلفه‌ها نیز تقریبی است، می‌توان نشان داد که هیچ الگوریتم کاملاً چندجمله‌ای مستدلی برای این گراف‌ها وجود ندارد.

مسئله

فرض کنید گرافی به صورت (G=(V,E دارید که V، مجموعه‌ای با n راس و E مجموعه یال هاست. برای یک مسئله افراز متعادل با زوج مرتب (k,V)، هدف افراز G به k مؤلفه با حداکثر سایز (v)(n/k) با مینیمم تعداد یال‌های مشترک بین این مؤلفه هاست. یا این که برای G و K>1 داده شده V را به K بخش …,K1,k2 تقسیم کنید به‌طوری‌که بخش‌ها از هم مجزا باشند و دارای اندازه‌های مساوی بوده به علاوه این که تعداد یال‌هایی که نقاط انتهایی آن‌ها در دو بخش متفاوت قرار دارد کمینه شود. در مورد این مسائل به شکلی مشابه مسئله شیوه افزایش منابع بحث می‌شود. توسعه‌ای از این مسئله در مسئله ابرگراف‌ها مطرح می‌شود که در آن یک یال می‌تواند به بیش از دو راس متصل باشد. یک ابریال قابل برش نیست، اگر همه رأس‌ها در یک افراز باشند، در مقابل دقیقاً یک بار بریده می‌شود، اگر یکی از این رأس‌ها در یک افراز دیگر قرار بگیرد، مستقل از تعداد راس‌هایی که در افراز دیگر قرار گرفته‌اند. از ابراگراف‌ها در خودکارسازی طراحی‌های الکترونیکی استفاده می‌شود.

تحلیل

برای یک مسئله افراز متعادل (k,1+ԑ)، به دنبال یافتن یک افراز با کمترین هزینه هستیم که گراف G را به k مؤلفه که هر کدام حداکثر دارای ((۱+ԑ)(n/(k) راس باشد هستیم. هزینه این الگوریتم تقریبی را با هزینه مسئله برش (k,1) مقایسه می‌کنیم که در آن هر کدام از k مؤلفه باید دقیقاً تعداد راس برابر با (n/k) داشته باشند به عبارتی این مسئله، مسئله محدود تری نسبت به مسئله قبلی می‌باشد. بنابراین داریم که،

$\max _{i}|V_{i}|\leq (1+\varepsilon )\left\lceil {\frac {|V|}{k}}\right\rceil .$

در حال حاضر می داینم که برش (۲٬۱) که کوچکترین مسئله دوبخشی می‌باشداز نوع NP-کامل است. سپس به بررسی مسئله ۳-افرازی که در آن n=3k است و پیچیدگی زمانی آن چندجمله‌ای است، می‌پردازیم. حال اگر فرض کنیم یک الگوریتم تخمینی متناهی برای مسئله افراز (k,1) داریم، یا نمونه ۳-بخشی با استفاده از افراز (k,1) بر گراف G قابل حل است یا این مسئله قابل حل نخواهد بود. حال اگر نمونه ۳-بخشی قابل حل باشد، مسئله افراز (k,1) نیز در گراف G بدون جدا کردن هیچ یالی، قابل حل است؛ در غیراینصورت اگر نمونه ۳-بخشی قابل حل نباشد، بهینه‌ترین افراز (k,1) بر روی G حداقل یک یال را برش می‌دهد. یک الگوریتم تخمینی با ضریب تخمین متناهی باید قادر به تشخیص این دو مورد از یکدیگر باشد، به این ترتیب می‌تواند مسئله ۳-بخشی که با فرض P=NP در تناقض است را حل کند؛ بنابراین مشهود است که مسئله افراز (k,1)، الگوریتم تخمین با زمان چندجمله‌ای و تخمین متناهی ندارد، مگر اینکه P=NP. تئوری جداسازی گراف مسطح تأکید می‌کند که هر گراف مسطح با n راس را می‌توان با حذف (O(√n راس به بخش‌های مساوی، تقسیم کرد. این نوع تقسیم‌بندی، با افرازی که در مورد آن توضیح داده شد، یکی نیستند، زیرا در این نوع تقسیم‌بندی، افرازها از راسها تشکیل شده‌اند نه یال‌ها. به هرحال نتیجه یکسان به دست آمده نشان می‌دهد هر گراف مسطح با درجه متناهی تعدادی برش متعادل با پیچیدگی (O(√n یال دارد.

روش‌های افراز گراف

از آنجایی که افراز گراف جزو مسائل سخت است، راه حل‌های عملی آن از روش‌های مکاشفه‌ای به دست آمده‌اند. دو گروه گسترده از این روش‌ها وجود دارد: محلی و سراسری. از جمله این روش‌های شناخته شده محلی الگوریتم Kernighan–Lin و الگوریتم‌های Fiduccia-Mattheyses می‌باشند که از ابتدایی‌ترین استراتژی‌های مؤثر برای‌های جستجوی محلی با برش‌های ۲-تایی بودند. عمده‌ترین مشکل این الگوریتم‌ها، مقداردهی اولیه دلخواه برای رئوس افرازها بود که بر کیفیت راه حل نهایی تأثیر می‌گذاشت. روش‌های سراسری بر ویژگی‌های کل گراف بستگی دارد و به مقداردهی دلخواه اولیه افرازها بستگی ندارد. رایج‌ترین نمونه آن، افراز طیفی است که افراز در آن از طیفی از ماتریس‌های مجاورت به دست می‌آید.

روش‌های چندمرحله‌ای

الگوریتم افراز چندمرحله‌ای در یک یا چند مرحله انجام می‌شود. هر مرحله اندازه گراف را با از بین بردن رأس‌ها و یالها کاهش می‌دهد، گراف‌های کوچکتر را افراز می‌کند، نهایتاً به عقب برمیگردد و بخش‌های گراف اصلی را تصحیح و بازسازی می‌کند. طیف گسترده‌ای از روش‌های تصحیح و افراز را می‌توان در شمای کلی روش چند مرحله‌ای قرار داد. در بسیاری از موارد، این روش می‌تواند سرعت اجرای بالا و نتایج با کیفیت بالا را هم‌زمان به دست دهد. یکی از مثال‌هایی که در آن از این روش به صورت گسترده استفاده می‌شود، METIS که یک افرازکننده گرافاست و hMETIS معادل آن برای ابرگراف هاست.

افراز طیفی و دو بخشی کردن طیف گونه

گرافی با ماتریس مجاورت A داده شده‌است، که Aij نشاندهنده یال بین i و j، و ماتریس درجه D، که یک ماتریس قطری است، و در آن هر اندیس قطری در سطر i، نشان دهنده درجه راس iام است. لاپلاس ماتریس L، به صورت L=D-A تعریف می‌شود. حال، ضریب برش برای گراف (G=(V,E، به معنای تقسیم کردن رأس‌ها به دو زیرگراف U و W می‌باشد که در آن هزینه برش (U,W)/(|U|/|W|) کمینه باشد. در این سناریو، دومین مقدار ویژه کوچک(L(λ، یک حد پایین برای هزینه(c) بهینه ضریب برش است که در آن c>λ/n. بردار ویژه (V) منتاظر با مقدار ویژه λ، گراف را تنها به دو بخش بر اساس اندیس منتاظر در آرایه یالها، دوبخشی می‌کند. تقسیم به تعداد بخش‌های بزرگتر با استفاده از تکرار روش دوبخشی به دست می‌آید، اما همیشه نتایج مورد انتظار و قابل قبولی را نمی‌دهد. مثال‌های توضیح داده شده در شکل ۱و ۲ نحوه انجام روش دوبخشی طیف گونه را توضیح می‌دهد.

شکل ۱. گراف)G(5,4 از منظر دو بخشی شدن طیفی مورد تحلیل قرار گرفته‌است. ترکیب خطی دو کمترین بردار ویژه به این انجامید که بردار ترانهاده [۱ ۱ ۱ ۱] دارای مقدار ویژه ۰ شود که بردار Fiedler که با قرمز نشان داده شده‌است گراف را به دو قسمت تقسیم کرده‌است.

شکل ۲. گراف (G=(۵٬۵ نشان داده شده‌است که بردار Fiedler که به صورت قرمز نشان داده شده‌است گراف را به دو قسمت تقسیم می‌کند مجموعه یال {۱٬۲,۳} که در فضای برداری مثبت و مجموعه یال {۴٬۵} در فضای برداری منفی

زمانی که تعداد گروه‌هایی که باید افراز شوند یا اندازه افرازها، معلوم نیست، افراز با کمترین برش، ناموفق است. برای مثال بهینه‌سازی اندازه برش برای گروه‌های آزاد، همه رأس‌ها را در یک گروه قرار می‌دهد. به علاوه، امکان دارد اندازه برش برای کمینه‌سازی اشتباه باشد، از آن جهت که برای داشتن یک افراز و تقسیم‌بندی مطلوب، تنها شرط کمترین یال میان گروه‌ها کفایت نمی‌کند. این توضیحات، انگیزه را برای استفاده از پیمانگی (Q) به منزله یک استاندارد برای بهینه‌سازی افراز متعادل، را ایجاد می‌کند. مثال‌های توضیح داده شده در شکل ۳، ۲ نمونه که یکی از آن‌ها از ضریب برش و دیگری از پیمانگی به عنوان استاندارد استفاده می‌کنند، را توضیح داده است. به هر حال، اخیراً اثبات شده‌است که روش پیمانگی مشکل محدودیت تفکیک‌پذیری دارد که موجب می‌شود، هنگام استفاده آن در گروه‌های کوچک، نتایج غیرقابل اعتمادی تولید کند. در این زمینه، روش surprise، به عنوان روشی جدید برای ارزیابی کیفیت روش‌های محاسبه‌کننده افراز، پیشنهاد شده‌است.

شکل ۳. گراف وزن دار G الف) می‌تواند طوری افزار شود تا Q را بیشینه شود. ب) تا نرخ برش کمینه شود. در این تصویر می‌بینیم که الف افراز متعادل بهتری است که اهمیت پیمانگی در مسائل افراز گراف را روشن می‌کند

سایر روش‌های افراز گراف

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

- به یالهای بین رأس‌های یک گروه جایزه می‌دهد.

- نبود یال بین رأس‌ها را در یک گروه را مجازت می‌کند.

- یالهای بین رأس‌های گروه‌های متفاوت را مجازات می‌کند.

- نبود یال بین رأس‌ها در گروه‌های متفاوت را جایزه می‌دهد.

به علاوه، خوشه بندی طیفی مبتنی بر PCA هسته‌ای، از یک چارچوب مبتنی بر کمترین مربعات بردار، بهره می‌برد و به این ترتیب امکان تصویر مدخل‌های داده را به هسته PCA، که ویژگی‌هایی همچون واریانس بالا را داراست، فراهم می‌کند؛ بنابراین یک جداسازی در سطح بالا را بین گروه‌های تصویر شده پیاده می‌کند. برخی دیگر از روش‌ها، افراز گراف‌ها را به مانند یک بهینه‌سازی چندضابطه‌ای بیان می‌کنند. این دسته از مسائل بهینه‌سازی را می‌توان با استفاده از روش‌های محلی که در چارچوب علمی بیان می‌شوند، حل کرد. در این مسائل هر راس می‌تواند افراز خود را خود انتخاب کند.

ابرازهای نرم‌افزاری

بسته‌های نرم‌افزاری متنوعی وجود دارند که الگوریتم‌های شرح داده شده را پیاده‌سازی کرده اندیکی از اولین بسته‌های نرم‌افزاری در دسترس قرار داده شده Chaco نامیده می‌شود. می‌باشد که متعلق به Hendrickson و Leland می‌باشد. همانند بیشتر بسته‌های نرم‌افزاری در دسترس عموم، Chaco تکنیک‌های چند متغیره که در بالا ذکر شده‌است الگوریتم‌های جستجوی محلی پایه را پیاده‌سازی کرده‌است. علاوه بر آن این بسته‌ها تکنیک‌های افراز طیفی را نیز پیاده‌سازی کرده‌اند.Metris، نیز از خانواده ابزارهای افراز گراف می‌باشد که توسط Karypis و Kumar توسعه داده شده‌است. kMetis بر روی سرعت افزار متمرکز شده‌است و hMetis که یک افراز گر ابرگراف می‌باشد بر روی تساوی افرازها تمرکز دارد. PaToH نیز در افراز ابر گراف‌ها به صورت گسترده کاربرد دارد که افرازهایی با کیفیت بالا تولید می‌کند. ParMetis یک پیاده‌سازی موازی از الگوریتم‌های افراز گراف مربوط به Metis است. Scotch نیز یک چارچوب برای افراز گراف است که توسط Pellegrini توسعه داده شده‌است. این بسته از روش‌های دو بخشی‌سازی بازگشتی چند متغیره از هر دو نوع تکنیک‌های موازی و پشت سر هم حمایت می‌کند. Jostle نیز یک افراز گر موازی یا پشت سر هم برای گراف فراهم می‌کند که توسط Chris Walshaw توسعه داده شده‌است. نسخه تجاری این افراز گر با نام NetWorks شناخته شده‌است. اگر مدلی از شبکه ارتباطی به در دسترس باشد آنگاه Jostle و Scotch می‌توانند از این مدل را به عنوان ورودی فرایند افراز گراف مورد استفاده قرار دهند. Party از نیز مجموعه مفیدی از الگوریتم‌ها به همراه الگوریتم‌های Bubble/shape-optimized را پیاده‌سازی می‌کند. بسته نرم‌افزاری DibaP نیز and its MPI-parallel variant PDibaP توسط Meyerhenke چارچوب Bubble را به کمک انتشار پیاده‌سازی کرده‌است.DibaP همچنین از تکنیک‌های مبتنی بر AMGen حل مسائل سیستم‌های خطی استفاده می‌کند. Sanders و Schulz نیز یک بسته نرم‌افزاری افراز گراف به نام KaHIP را پیاده‌سازی کرده‌اند.

لیست چارچوب‌های رایگان متن باز:

نام	گواهی	توضیحات مختصر
Chaco	GPL	بسته نرم‌افزاری که تکنیک‌های طیفی و چند متغیره را پیاده‌سازی کرده‌است.
DiBaP	*	افراز گراف بر پایه تکنیک‌های چند متغیرهُ جبر چند شبکه‌ای و انتشار مبتنی بر گراف
Jostle	*	تکنیک‌های افراز چند سطحی و انتشار مبتنی بر گراف
KaHIP	GPL	تکنیک‌های موازی و مرحله به مرجحله فرا-اکتشافی که محدودیت‌های متعادل بودن را تضمین می‌کند.
kMetis	Apache ۲٫۰	بسته افراز گراف مبتنی بر تکنیک‌های چند متغیره و جستجوهای k تایی محلی
Mondriaan	LGPL	افرازکننده ماتریس برای افراز ماتریس‌های تنک مستطیلی
PaToH	BSD	افراز چند مرحله‌ای ابر گراف
Parkway	*	افراز چند مرحله‌ای ابرگراف به صورت موازی
Scotch	CeCILL-C	پیده‌سازی دو بخشی‌سازی بازگشتی چند متغیره به همراه روش‌های انتشاری، روش‌های موازی و روش‌های پشت سر هم
Zoltan	BSD	افراز ابرگراف

پیوند به بیرون

• Chamberlain, Bradford L. (1998). "Graph Partitioning Algorithms for Distributing Workloads of Parallel Computations"

کتاب‌شناسی

• Charles-Edmond Bichot, Patrick Siarry (2011). Graph Partitioning: Optimisation and Applications. ISTE – Wiley. p. 384. ISBN 978-1-84821-233-6.
• Feldmann, Andreas Emil (2012). Balanced Partitioning of Grids and Related Graphs: A Theoretical Study of Data Distribution in Parallel Finite Element Model Simulations (PDF). Goettingen, Germany: Cuvillier Verlag. p. 218. ISBN 978-3-95404-125-1. An exhaustive analysis of the problem from a theoretical point of view.
• BW Kernighan, S Lin (1970). "An efficient heuristic procedure for partitioning graphs" (PDF). Bell System Technical Journal. Archived from the original (PDF) on 2 March 2012. Retrieved 11 December 2013. One of the early fundamental works in the field. However, performance is O(n²), so it is no longer commonly used.
• CM Fiduccia, RM Mattheyses (1982). "A Linear-Time Heuristic for Improving Network Partitions". Design Automation Conference. A later variant that is linear time, very commonly used, both by itself and as part of multilevel partitioning, see below.
• G Karypis, V Kumar (1999). "A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs". Siam Journal on Scientific Computing. Multi-level partitioning is the current state of the art. This paper also has good explanations of many other methods, and comparisons of the various methods on a wide variety of problems.
• Karypis, G. , Aggarwal, R. , Kumar, V. , and Shekhar, S. (March 1999). "Multilevel hypergraph partitioning: applications in VLSI domain". IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 7 (1): pp. 69–79. doi:10.1109/92.748202. {{cite journal}}: |pages= has extra text (help)نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link) Graph partitioning (and in particular, hypergraph partitioning) has many applications to IC design.
• S. Kirkpatrick, C. D. Gelatt Jr. , and M. P. Vecchi (13 May 1983). "Optimization by Simulated Annealing". Science. 220 (4598): 671–680. doi:10.1126/science.220.4598.671. PMID 17813860.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link) Simulated annealing can be used as well.
• Hagen, L. and Kahng, A.B. (September 1992). "New spectral methods for ratio cut partitioning and clustering". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 11, (9): 1074–1085. doi:10.1109/43.159993.{{cite journal}}: نگهداری CS1: نقطه‌گذاری اضافه (link) نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link). There is a whole class of spectral partitioning methods, which use the Eigenvectors of the Laplacian of the connectivity graph. You can see a demo of this بایگانی‌شده در ۲۰۰۸-۱۰-۰۳ توسط Wayback Machine, using Matlab.