افراز گراف: تفاوت میان نسخه‌ها
| خط ۸۹: | خط ۸۹: | ||
گرافی با ماتریس مجاورت A داده شده است، که Aij نشاندهنده یال بین i و j، و ماتریس درجه D، که یک ماتریس قطری است، و در آن هر اندیس قطری در سطر i، نشان دهنده درجه راس iام است. لاپلاس ماتریس L، به صورت L=D-A تعریف می شود. حال، ضریب برش برای گراف (G=(V,E، به معنای تقسیم کردن راس ها به دو زیرگراف U و W می باشد که در آن هزینه برش (U,W)/(|U|/|W|) کمینه باشد. |
گرافی با ماتریس مجاورت 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) منتاظر با مقدار ویژه λ ،گراف را تنها به دو بخش بر اساس اندیس منتاظر در آرایه یالها، دوبخشی می کند. تقسیم به تعداد بخش های بزرگتر با استفاده از تکرار روش دوبخشی به دست می آید، اما همیشه نتایج مورد انتظار و قابل قبولی را نمی دهد. مثال های توضیح داده شده در شکل 1و 2 نحوه انجام روش دوبخشی طیف گونه را توضیح می دهد. |
در این سناریو، دومین مقدار ویژه کوچک(L(λ، یک حد پایین برای هزینه(c) بهینه ضریب برش است که در آن c>λ/n. بردار ویژه (V) منتاظر با مقدار ویژه λ ،گراف را تنها به دو بخش بر اساس اندیس منتاظر در آرایه یالها، دوبخشی می کند. تقسیم به تعداد بخش های بزرگتر با استفاده از تکرار روش دوبخشی به دست می آید، اما همیشه نتایج مورد انتظار و قابل قبولی را نمی دهد. مثال های توضیح داده شده در شکل 1و 2 نحوه انجام روش دوبخشی طیف گونه را توضیح می دهد. |
||
زمانی که تعداد گروه هایی که باید افراز شوند یا اندازه افرازها، معلوم نیست ،افراز با کمترین برش، ناموفق است. برای مثال بهینه سازی اندازه برش برای گروه های آزاد، همه راس ها را در یک گروه قرار میدهد. به علاوه،امکان دارد اندازه برش برای کمینه سازی اشتباه باشد، از آن جهت که برای داشتن یک افراز و تقسیم بندی مطلوب،تنها شرط کمترین یال میان گروه ها کفایت نمیکند. این توضیحات، انگیزه را برای استفاده از پیمانگی (Q) <ref name="npnas"> |
|||
{{cite journal |
|||
| author = Newman, M. E. J. |
|||
| year = 2006 |
|||
| title = Modularity and community structure in networks |
|||
| journal = PNAS |
|||
| volume = 103 |
|||
| issue = 23 |
|||
| pages = 8577–8696 |
|||
| doi = 10.1073/pnas.0601602103 |
|||
| pmid=16723398 |
|||
| pmc=1482622 |
|||
}}</ref> به منزله یک استاندارد برای بهینه سازی افراز متعادل، را ایجاد می کند. مثال های توضیح داده شده در شکل 3، 2 نمونه که یکی از آنها از ضریب برش و دیگری از پیمانگی به عنوان استاندارد استفاده می کنند، را توضیح داده است. به هر حال، اخیرا اثبات شده است که روش پیمانگی مشکل محدودیت تفکیک پذیری دارد که موجب می شود، هنگام استفاده آن در گروه های کوچک، نتایج غیرقابل اعتمادی تولید کند. در این زمینه، روش surprise،<ref name = "Surprise"> |
|||
{{cite journal |
|||
| author = Rodrigo Aldecoa and Ignacio Marín |
|||
| year = 2011 |
|||
| title = Deciphering network community structure by Surprise |
|||
| journal = PLoS ONE |
|||
| volume = 6 |
|||
| issue = 9 |
|||
| pages = e24195 |
|||
| doi = 10.1371/journal.pone.0024195 |
|||
| pmid = 21909420 |
|||
| url = http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0024195 |
|||
}} |
|||
</ref> به عنوان روشی جدید برای ارزیابی کیفیت روش های محاسبه کننده افراز، پیشنهاد شده است. |
|||
==منابع و مآخذ== |
==منابع و مآخذ== |
||
نسخهٔ ۱۱ دسامبر ۲۰۱۳، ساعت ۱۴:۱۲
 | این مقاله به دلیل نیازمند خلاصه نویسی و تمیزکاری نیازمند تمیزکاری است. لطفاً تا جای امکان آنرا از نظر املا، انشا، چیدمان و درستی بهتر کنید، سپس این برچسب را بردارید. محتویات این مقاله ممکن است غیر قابل اعتماد و نادرست یا جانبدارانه باشد یا قوانین حقوق پدیدآورندگان را نقض کرده باشد. |
 | این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. (دسامبر ۲۰۱۳) |
در ریاضیات ، مساله افراز گراف بر روی داده هایی در قالب گراف (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 مولفه که هر کدام حداکثر دارای (1+ԑ)(n/k) راس باشد هستیم.هزینه این الگوریتم تقریبی را با هزینه مساله برش (k,1) مقایسه می کنیم که در آن هر کدام از k مولفه باید دقیقا تعداد راس برابر با (n/k) داشته باشند به عبارتی این مساله ، مساله محدود تری نسبت به مساله قبلی می باشد.بنابر این داریم که ،
در حال حاضر می داینم که برش (2,1) که کوچکترین مساله دوبخشی می باشداز نوع NP-کامل است.[۵] سپس به بررسی مساله 3-افرازی که در آن n=3k است و پیچیدگی زمانی آن چندجمله ای است، می پردازیم.[۱] حال اگر فرض کنیم یک الگوریتم تخمینی متناهی برای مساله افراز (k,1) داریم، یا نمونه 3-بخشی با استفاده از افراز (k,1) بر گراف G قابل حل است یا این مسئله قابل حل نخواهد بود. حال اگر نمونه 3-بخشی قابل حل باشد، مسئله افراز (k,1) نیز در گراف G بدون جدا کردن هیچ یالی، قابل حل است؛ در غیراینصورت اگر نمونه 3-بخشی قابل حل نباشد، بهینه ترین افراز (k,1) بر روی G حداقل یک یال را برش می دهد. یک الگوریتم تخمینی با ضریب تخمین متناهی باید قادر به تشخیص این دو مورد از یکدیگر باشد، به این ترتیب می تواند مسئله 3-بخشی که با فرض P=NP در تناقض است را حل کند. بنابراین مشهود است که مسئله افراز (k,1)، الگوریتم تخمین با زمان چندجمله ای و تخمین متناهی ندارد، مگر اینکه P=NP. [۱]تئوری جداسازی گراف مسطح تاکید می کند که هر گراف مسطح با n راس را می توان با حذف (O(√n راس به بخش های مساوی، تقسیم کرد. این نوع تقسیم بندی، با افرازی که در مورد آن توضیح داده شد، یکی نیستند، زیرا در این نوع تقسیم بندی، افرازها از راسها تشکیل شده اند نه یال ها. به هرحال نتیجه یکسان به دست آمده نشان میدهد هر گراف مسطح با درجه متناهی تعدادی برش متعادل با پیچیدگی (O(√n یال دارد.
روش های افراز گراف
از آنجایی که افراز گراف جزو مسائل سخت است، راه حل های عملی آن از روش های مکاشفه ای به دست آمده اند. دو گروه گسترده از این روش ها وجود دارد: محلی و سراسری. از جمله این روش های شناخته شده محلی الگوریتم کرنیقان-لین و الگوریتم های فیدوسیا-متیوس می باشند که از ابتدایی ترین استراتژی های موثر برای های جستجوی محلی با برش های 2-تایی بودند. عمده ترین مشکل این الگوریتم ها، مقداردهی اولیه دلخواه برای رئوس افرازها بود که بر کیفیت راه حل نهایی تاثیر می گذاشت. روشهای سراسری بر ویژگیهای کل گراف بستگی دارد و به مقداردهی دلخواه اولیه افراز ها بستگی ندارد. رایج ترین نمونه آن، افراز طیفی است که افراز در آن از طیفی از ماتریس های مجاورت به دست می آید.
روش های چندمرحله ای
الگوریتم افراز چندمرحله ای در یک یا چند مرحله انجام می شود. هر مرحله اندازه گراف را با از بین بردن راس ها و یالها کاهش می دهد، گراف های کوچکتر را افراز می کند، نهایتا به عقب برمیگردد و بخش های گراف اصلی را تصحیح و بازسازی می کند.[۶] طیف گسترده ای از روشهای تصحیح و افراز را می توان در شمای کلی روش چند مرحله ای قرار داد. در بسیاری از موارد، این روش می تواند سرعت اجرای بالا و نتایج با کیفیت بالا را همزمان به دست دهد. یکی از مثال هایی که در آن از این روش به صورت گسترده استفاده می شود ، 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) منتاظر با مقدار ویژه λ ،گراف را تنها به دو بخش بر اساس اندیس منتاظر در آرایه یالها، دوبخشی می کند. تقسیم به تعداد بخش های بزرگتر با استفاده از تکرار روش دوبخشی به دست می آید، اما همیشه نتایج مورد انتظار و قابل قبولی را نمی دهد. مثال های توضیح داده شده در شکل 1و 2 نحوه انجام روش دوبخشی طیف گونه را توضیح می دهد. زمانی که تعداد گروه هایی که باید افراز شوند یا اندازه افرازها، معلوم نیست ،افراز با کمترین برش، ناموفق است. برای مثال بهینه سازی اندازه برش برای گروه های آزاد، همه راس ها را در یک گروه قرار میدهد. به علاوه،امکان دارد اندازه برش برای کمینه سازی اشتباه باشد، از آن جهت که برای داشتن یک افراز و تقسیم بندی مطلوب،تنها شرط کمترین یال میان گروه ها کفایت نمیکند. این توضیحات، انگیزه را برای استفاده از پیمانگی (Q) [۹] به منزله یک استاندارد برای بهینه سازی افراز متعادل، را ایجاد می کند. مثال های توضیح داده شده در شکل 3، 2 نمونه که یکی از آنها از ضریب برش و دیگری از پیمانگی به عنوان استاندارد استفاده می کنند، را توضیح داده است. به هر حال، اخیرا اثبات شده است که روش پیمانگی مشکل محدودیت تفکیک پذیری دارد که موجب می شود، هنگام استفاده آن در گروه های کوچک، نتایج غیرقابل اعتمادی تولید کند. در این زمینه، روش surprise،[۱۰] به عنوان روشی جدید برای ارزیابی کیفیت روش های محاسبه کننده افراز، پیشنهاد شده است.
منابع و مآخذ
- ↑ ۱٫۰ ۱٫۱ ۱٫۲ ۱٫۳ ۱٫۴
Andreev, Konstantin and Räcke, Harald, (2004). "Balanced Graph Partitioning". Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. Barcelona, Spain: 120–124. doi:10.1145/1007912.1007931. ISBN 1-58113-840-7.
{{cite journal}}: نگهداری CS1: نقطه‌گذاری اضافه (link) نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link) - ↑ ۲٫۰ ۲٫۱ Sachin B. Patkar and H. Narayanan (2003). "An Efficient Practical Heuristic For Good Ratio-Cut Partitioning". VLSI Design, International Conference on: 64. doi:10.1109/ICVD.2003.1183116.
- ↑
Feldmann, Andreas Emil and Foschini, Luca (2012). "Balanced Partitions of Trees and Applications". Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science. Paris, France: 100–111.
{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link) - ↑ ۴٫۰ ۴٫۱ Feldmann, Andreas Emil (2012). "Fast Balanced Partitioning is Hard, Even on Grids and Trees". Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science. Bratislava, Slovakia.
- ↑
Garey, Michael R. and Johnson, David S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co. ISBN 0-7167-1044-7.
{{cite book}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link) - ↑
Hendrickson, B. and Leland, R. (1995). A multilevel algorithm for partitioning graphs. Proceedings of the 1995 ACM/IEEE conference on Supercomputing. ACM. p. 28.
{{cite conference}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link) - ↑ Karypis, G. and Kumar, V. (1999). "A fast and high quality multilevel scheme for partitioning irregular graphs". SIAM Journal on Scientific Computing. 20 (1): 359. doi:10.1137/S1064827595287997.
{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link) - ↑
Karypis, G. and Aggarwal, R. and Kumar, V. and Shekhar, S. (1997). "Multilevel hypergraph partitioning: application in VLSI domain". Proceedings of the 34th annual Design Automation Conference. pp. 526–529.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help)نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link) - ↑ Newman, M. E. J. (2006). "Modularity and community structure in networks". PNAS. 103 (23): 8577–8696. doi:10.1073/pnas.0601602103. PMC 1482622. PMID 16723398.
- ↑ Rodrigo Aldecoa and Ignacio Marín (2011). "Deciphering network community structure by Surprise". PLoS ONE. 6 (9): e24195. doi:10.1371/journal.pone.0024195. PMID 21909420.