ในทางคณิตศาสตร์การแบ่งกราฟคือการลดกราฟให้เหลือกราฟที่เล็กลงโดยการแบ่งเซตของโหนดออกเป็นกลุ่มที่ไม่ซ้ำกัน ขอบของกราฟเดิมที่ตัดผ่านระหว่างกลุ่มจะสร้างขอบในกราฟที่แบ่งแล้ว หากจำนวนขอบที่ได้มีน้อยเมื่อเทียบกับกราฟเดิม กราฟที่แบ่งแล้วอาจเหมาะสมกว่าสำหรับการวิเคราะห์และการแก้ปัญหามากกว่ากราฟเดิม การค้นหาการแบ่งที่ทำให้การวิเคราะห์กราฟง่ายขึ้นเป็นปัญหาที่ยาก แต่เป็นปัญหาที่มีการประยุกต์ใช้ในการคำนวณทางวิทยาศาสตร์ การออกแบบวงจร VLSIและการจัดตารางงานในคอมพิวเตอร์มัลติโปรเซสเซอร์ เป็นต้น^{[ 1 ]} เมื่อเร็วๆ นี้ ปัญหาการแบ่งกราฟได้รับความสำคัญมากขึ้นเนื่องจากการประยุกต์ใช้สำหรับการจัดกลุ่มและการตรวจจับคลิกในเครือข่ายสังคม พยาธิวิทยา และชีววิทยา สำหรับการสำรวจแนวโน้มล่าสุดในวิธีการคำนวณและการประยุกต์ใช้ โปรดดู Buluc et al . (2013) ^{[ 2 ]} ตัวอย่างทั่วไปสองตัวอย่างของการแบ่งกราฟคือ ปัญหา การตัดขั้นต่ำและปัญหา การตัดสูงสุด

โดยทั่วไป ปัญหาการแบ่งกราฟจัดอยู่ในประเภทของปัญหาNP-hard วิธีแก้ปัญหาเหล่านี้โดยทั่วไปได้มาจากการใช้ฮิวริสติกและอัลกอริธึมการประมาณค่า ^{[ 3 ]}อย่างไรก็ตาม การแบ่งกราฟแบบสม่ำเสมอหรือปัญหาการแบ่งกราฟแบบสมดุลสามารถแสดงให้เห็นว่าเป็นNP-completeที่สามารถประมาณค่าได้ภายในปัจจัยจำกัดใดๆ^{[ 1 ]}แม้แต่สำหรับกราฟประเภทพิเศษ เช่น ต้นไม้และกริด ก็ไม่มีอัลกอริธึมการประมาณค่าที่เหมาะสม^{[ 4 ]}เว้นแต่ว่าP=NPกริดเป็นกรณีที่น่าสนใจเป็นพิเศษ เนื่องจากกริดจำลองกราฟที่ได้จาก การจำลอง แบบจำลององค์ประกอบจำกัด (FEM)เมื่อไม่เพียงแต่ประมาณจำนวนขอบระหว่างส่วนประกอบเท่านั้น แต่ยังรวมถึงขนาดของส่วนประกอบด้วย ก็สามารถแสดงให้เห็นได้ว่าไม่มีอัลกอริธึมพหุนามที่สมบูรณ์แบบที่เหมาะสมสำหรับกราฟเหล่านี้^{[ 4 ]}

พิจารณากราฟG = ( V , E ) โดยที่Vแทนเซตของ จุดยอด nจุด และEแทนเซตของขอบ สำหรับปัญหาการแบ่งส่วนที่สมดุล ( k , v ) วัตถุประสงค์คือการแบ่งG ออก เป็นkส่วนประกอบที่มีขนาดไม่เกินv · ( n / k ) ในขณะที่ลดความจุของขอบระหว่างส่วนประกอบที่แยกจากกันให้ น้อยที่สุด ^{[ 1 ]}นอกจากนี้ เมื่อกำหนดGและจำนวนเต็มk > 1 ให้แบ่งVออกเป็นkส่วน (เซตย่อย) V ₁ , V ₂ , ..., V _kโดยที่ส่วนต่างๆ ไม่ทับซ้อนกันและมีขนาดเท่ากัน และจำนวนขอบที่มีจุดปลายอยู่ในส่วนต่างๆ จะถูกลดให้น้อยที่สุด ปัญหาการแบ่งส่วนดังกล่าวได้รับการกล่าวถึงในวรรณกรรมว่าเป็นแนวทางการประมาณค่าแบบสองเกณฑ์หรือการเพิ่มทรัพยากร การขยายทั่วไปคือไปยังไฮเปอร์กราฟซึ่งขอบสามารถเชื่อมต่อจุดยอดได้มากกว่าสองจุด ไฮเปอร์เอดจ์จะไม่ถูกตัดหากจุดยอดทั้งหมดอยู่ในส่วนเดียว และจะถูกตัดเพียงครั้งเดียวเท่านั้น ไม่ว่าจะมีจุดยอดกี่จุดในแต่ละด้านก็ตาม การใช้งานลักษณะนี้พบได้ทั่วไปในการออกแบบระบบอัตโนมัติทางอิเล็กทรอนิกส์

สำหรับปัญหาการแบ่งพาร์ติชันสมดุลเฉพาะ ( k , 1 +  ε ) เราต้องการหาการแบ่งพาร์ติชันที่มีต้นทุนต่ำที่สุดของGออกเป็นkส่วนประกอบ โดยแต่ละส่วนประกอบมีโหนดสูงสุด (1 +  ε )·( n / k ) โหนด เราเปรียบเทียบต้นทุนของอัลกอริทึมการประมาณนี้กับต้นทุนของการตัด ( k , 1) ซึ่งแต่ละส่วนประกอบทั้งkจะต้องมีขนาดเท่ากันคือ ( n / k ) โหนด ทำให้เป็นปัญหาที่มีข้อจำกัดมากกว่า ดังนั้น

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

เราทราบอยู่แล้วว่าการตัด (2,1) เป็นปัญหาการแบ่งครึ่งขั้นต่ำและเป็นปัญหา NP-complete ^{[ 5 ]}ต่อไป เราจะประเมินปัญหาการแบ่ง 3 ส่วน โดยที่n  = 3 kซึ่งมีขอบเขตในเวลาพหุนามเช่นกัน^{[ 1 ]}ตอนนี้ ถ้าเราสมมติว่าเรามีอัลกอริทึมการประมาณค่าแบบจำกัดสำหรับการแบ่งส่วนที่สมดุล ( k , 1) แล้ว ปัญหาการแบ่ง 3 ส่วนนั้นสามารถแก้ไขได้โดยใช้การแบ่งส่วนที่สมดุล ( k ,1) ในGหรือไม่สามารถแก้ไขได้เลย ถ้าปัญหาการแบ่ง 3 ส่วนสามารถแก้ไขได้ ปัญหาการแบ่งส่วนที่สมดุล ( k , 1) ในGก็สามารถแก้ไขได้โดยไม่ต้องตัดขอบใดๆ มิฉะนั้น ถ้าปัญหาการแบ่ง 3 ส่วนไม่สามารถแก้ไขได้ การแบ่งส่วนที่สมดุล ( k , 1) ที่เหมาะสมที่สุดในGจะตัดขอบอย่างน้อยหนึ่งขอบ อัลกอริทึมการประมาณค่าที่มีปัจจัยการประมาณค่าแบบจำกัดจะต้องแยกแยะระหว่างสองกรณีนี้ ดังนั้น จึงสามารถแก้ปัญหาการแบ่ง 3 ส่วน ซึ่งเป็นข้อขัดแย้งภายใต้สมมติฐานที่ว่าP  =  NPได้ ดังนั้นจึงเห็นได้ชัดว่าปัญหาการแบ่งส่วนที่สมดุล ( k ,1) ไม่มีอัลกอริทึมการประมาณค่าแบบพหุนามที่มีปัจจัยการประมาณค่าจำกัด เว้นแต่^ว่า P  =  NP [ ^{1 ]}

ทฤษฎีบทตัวแบ่งระนาบกล่าวว่ากราฟระนาบที่ มี nจุดยอด ใดๆ สามารถแบ่งออกเป็นส่วนๆ ที่เท่าๆ กันโดยประมาณได้โดยการลบจุดยอดจำนวน O( √n )จุด นี่ไม่ใช่การแบ่งส่วนในความหมายที่อธิบายไว้ข้างต้น เพราะเซตของการแบ่งส่วนประกอบด้วยจุดยอด ไม่ใช่ขอบ อย่างไรก็ตาม ผลลัพธ์เดียวกันนี้ยังบ่งชี้ว่ากราฟระนาบทุกกราฟที่มีดีกรีจำกัดจะมีส่วนตัดสมดุลที่มีขอบจำนวน O( √n )จุด

เนื่องจากการแบ่งกราฟเป็นปัญหาที่ยาก วิธีแก้ปัญหาในทางปฏิบัติจึงอาศัยหลักการเชิงฮิวริสติก โดยแบ่งวิธีการออกเป็นสองประเภทใหญ่ๆ คือ วิธีการแบบโลคอลและวิธีการแบบโกลบอล วิธีการแบบโลคอลที่เป็นที่รู้จักกันดี ได้แก่อัลกอริทึม Kernighan–Linและอัลกอริทึม Fiduccia-Mattheysesซึ่งเป็นวิธีการตัดแบบ 2 ทางที่มีประสิทธิภาพเป็นครั้งแรกโดยใช้กลยุทธ์การค้นหาแบบโลคอล ข้อเสียเปรียบที่สำคัญของวิธีการเหล่านี้คือการแบ่งกลุ่มจุดยอดเริ่มต้นแบบสุ่ม ซึ่งอาจส่งผลต่อคุณภาพของคำตอบสุดท้าย ส่วนวิธีการแบบโกลบอลนั้นอาศัยคุณสมบัติของกราฟทั้งหมดและไม่ขึ้นอยู่กับการแบ่งกลุ่มเริ่มต้นแบบสุ่ม ตัวอย่างที่พบได้บ่อยที่สุดคือการแบ่งกลุ่มแบบสเปกตรัม ซึ่งการแบ่งกลุ่มได้มาจากเวกเตอร์ลักษณะเฉพาะโดยประมาณของเมทริกซ์ความประชิด หรือการจัดกลุ่มแบบสเปกตรัมที่จัดกลุ่มจุดยอดของกราฟโดยใช้การแยกส่วนลักษณะเฉพาะของเมทริกซ์ ลาปลาเซียนของกราฟ

อัลกอริทึมการแบ่งกราฟแบบหลายระดับทำงานโดยการใช้ขั้นตอนหนึ่งขั้นตอนหรือมากกว่านั้น แต่ละขั้นตอนจะลดขนาดของกราฟโดยการยุบจุดยอดและขอบ แบ่งกราฟที่เล็กลง จากนั้นแมปกลับและปรับปรุงการแบ่งกราฟดั้งเดิมนี้^{[ 6 ]}สามารถใช้วิธีการแบ่งและการปรับปรุงที่หลากหลายภายในโครงร่างหลายระดับโดยรวม ในหลายกรณี วิธีการนี้สามารถให้ทั้งเวลาการทำงานที่รวดเร็วและผลลัพธ์ที่มีคุณภาพสูงมาก ตัวอย่างหนึ่งที่ใช้กันอย่างแพร่หลายของวิธีการดังกล่าวคือ^{METIS [} 7 ] ^{ซึ่งเป็น}ตัวแบ่งกราฟ และ hMETIS ซึ่งเป็นตัวแบ่งที่สอดคล้องกันสำหรับไฮเปอร์กราฟ^{[ 8 ]} วิธีการทางเลือกที่มาจาก^{[ 9 ]} และนำไปใช้ เช่น ในscikit-learnคือการจัดกลุ่มสเปกตรัมโดยกำหนดการแบ่งจากเวกเตอร์ลักษณะเฉพาะของ เมทริกซ์ Laplacian ของกราฟสำหรับกราฟดั้งเดิมที่คำนวณโดย ตัวแก้ LOBPCGด้วยการปรับสภาพล่วงหน้าแบบมัลติกริด

กำหนดให้กราฟมีเมทริกซ์ประชิดโดยที่ค่าใน เมทริกซ์ หมายถึงขอบระหว่างโหนดและและเมทริกซ์ดีกรีซึ่งเป็นเมทริกซ์แนวทแยง โดยที่ค่าในแนวทแยง ของแต่ละแถวแทนดีกรีของโหนดเมทริกซ์ลาปลาเซียนถูกกำหนดให้เป็นตอนนี้ การแบ่งพาร์ติชันแบบอัตราส่วนสำหรับกราฟถูกกำหนดให้เป็นการแบ่งพาร์ติชันของออกเป็นและ ที่ไม่ซ้ำกัน โดยลดอัตราส่วนให้เหลือน้อยที่สุด ${\displaystyle G=(V,E)}$${\displaystyle A}$${\displaystyle A_{ij}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle D}$${\displaystyle i}$${\displaystyle d_{ii}}$${\displaystyle i}$${\displaystyle L}$${\displaystyle L=DA}$${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle U}$${\displaystyle W}$

${\displaystyle {\frac {|E(G)\cap (U\times W)|}{|U|\cdot |W|}}}$

จากจำนวนขอบที่ตัดผ่านส่วนนี้จริง ๆ ไปจนถึงจำนวนคู่ของจุดยอดที่สามารถรองรับขอบดังกล่าวได้ การแบ่งกราฟสเปกตรัมสามารถอธิบายได้^{[ 10 ]}โดยเปรียบเทียบกับการแบ่งส่วนของสายสั่นหรือระบบมวล-สปริง และขยายไปยังกรณีของน้ำหนักลบของกราฟในทำนองเดียวกัน^{[ 11 ]}

ในสถานการณ์เช่นนี้ค่าไอเกนที่เล็กที่สุดอันดับสอง ( ) ของจะให้ขอบเขตล่างของต้นทุนที่เหมาะสมที่สุด ( ) ของการแบ่งพาร์ติชันแบบตัดอัตราส่วนด้วย เวกเตอร์ ไอเกน ( ) ที่สอดคล้องกับเรียกว่าเวกเตอร์ Fiedlerจะแบ่งกราฟออกเป็นสองชุมชนเท่านั้นโดยพิจารณาจากเครื่องหมายของรายการเวกเตอร์ที่สอดคล้องกันการแบ่งออกเป็นชุมชนจำนวนมากขึ้นสามารถทำได้โดยการแบ่ง ครึ่งซ้ำๆ หรือโดยการใช้เวกเตอร์ไอเกนหลายตัวที่สอดคล้องกับค่าไอเกนที่เล็กที่สุด^{[ 12 ]}ตัวอย่างในรูปที่ 1,2 แสดงให้เห็นถึงวิธีการแบ่งครึ่งสเปกตรัม ${\displaystyle \lambda _{2}}$${\displaystyle L}$${\displaystyle c}$${\displaystyle c\geq {\frac {\lambda _{2}}{n}}}$${\displaystyle V_{2}}$${\displaystyle \lambda _{2}}$

อย่างไรก็ตาม การแบ่งพาร์ติชันด้วยการตัดขั้นต่ำจะล้มเหลวเมื่อจำนวนชุมชนที่จะแบ่งหรือขนาดของพาร์ติชันไม่เป็นที่ทราบ ตัวอย่างเช่น การเพิ่มประสิทธิภาพขนาดการตัดสำหรับขนาดกลุ่มอิสระจะทำให้จุดยอดทั้งหมดอยู่ในชุมชนเดียวกัน นอกจากนี้ ขนาดการตัดอาจไม่ใช่สิ่งที่ควรลดให้เหลือน้อยที่สุด เนื่องจากการแบ่งที่ดีไม่ได้หมายถึงการแบ่งที่มีจำนวนขอบระหว่างชุมชนน้อยเท่านั้น ด้วยเหตุนี้จึงมีการใช้Modularity (Q) ^{[ 13 ]}เป็นตัวชี้วัดเพื่อเพิ่มประสิทธิภาพการแบ่งพาร์ติชันกราฟที่สมดุล ตัวอย่างในรูปที่ 3 แสดงให้เห็น 2 กรณีของกราฟเดียวกัน โดยใน(a) modularity (Q) เป็นตัวชี้วัดการแบ่งพาร์ติชัน และใน(b) ratio-cut เป็นตัวชี้วัดการแบ่งพาร์ติชัน

ฟังก์ชันวัตถุประสงค์อีกอย่างหนึ่งที่ใช้ในการแบ่งกราฟคือ ค่าการนำไฟฟ้า (Conductance)ซึ่งเป็นอัตราส่วนระหว่างจำนวนขอบที่ถูกตัดกับปริมาตรของส่วนที่เล็กที่สุด ค่าการนำไฟฟ้ามีความเกี่ยวข้องกับการไหลของกระแสไฟฟ้าและการเดินแบบสุ่มขอบเขตของ Cheeger รับประกันว่าการแบ่งครึ่งสเปกตรัมจะให้การ แบ่ง ส่วนที่มีค่าการนำไฟฟ้าใกล้เคียงกับค่าที่เหมาะสมที่สุด คุณภาพของการประมาณนี้ขึ้นอยู่กับค่าลักษณะเฉพาะที่เล็กที่สุดอันดับสองของ Laplacian λ ₂

การแบ่งกราฟสามารถเป็นประโยชน์ในการระบุชุดโหนดหรือลิงก์ขั้นต่ำที่ควรได้รับการสร้างภูมิคุ้มกันเพื่อหยุดการระบาด^{[ 14 ]}

แบบจำลองสปินถูกใช้สำหรับการจัดกลุ่มข้อมูลหลายตัวแปร โดยที่ความคล้ายคลึงกันจะถูกแปลงเป็นความแข็งแกร่งของการเชื่อมต่อ^{[ 15 ]}คุณสมบัติของการกำหนดค่าสปินสถานะพื้นฐานสามารถตีความได้โดยตรงว่าเป็นชุมชน ดังนั้น กราฟจึงถูกแบ่งส่วนเพื่อลดแฮมิลโทเนียนของกราฟที่แบ่งส่วนแฮมิลโทเนียน (H) ได้มาจากการกำหนดรางวัลและบทลงโทษการแบ่งส่วนดังต่อไปนี้

• ให้รางวัลแก่เส้นเชื่อมภายในระหว่างโหนดในกลุ่มเดียวกัน (สปินเดียวกัน)
• ลงโทษขอบที่ขาดหายไปในกลุ่มเดียวกัน
• ลงโทษเส้นเชื่อมที่มีอยู่ระหว่างกลุ่มต่างๆ
• ให้รางวัลแก่กลุ่มที่ไม่เชื่อมโยงกัน

นอกจากนี้ การจัดกลุ่มสเปกตรัมตาม Kernel-PCA ใช้รูปแบบของกรอบงาน Support Vector Machine แบบกำลังสองน้อยที่สุด ดังนั้นจึงเป็นไปได้ที่จะฉายรายการข้อมูลไปยังพื้นที่คุณลักษณะที่เหนี่ยวนำโดยเคอร์เนลซึ่งมีความแปรปรวนสูงสุด ซึ่งหมายถึงการแยกที่สูงระหว่างชุมชนที่ฉายภาพ^{[ 16 ]}

บางวิธีแสดงการแบ่งกราฟเป็นปัญหาการเพิ่มประสิทธิภาพหลายเกณฑ์ซึ่งสามารถแก้ไขได้โดยใช้วิธีท้องถิ่นที่แสดงในกรอบทฤษฎีเกม โดยที่แต่ละโหนดจะตัดสินใจเลือกการแบ่ง^{[ 17 ]}

สำหรับกราฟแบบกระจายขนาดใหญ่มาก วิธีการแบ่งพาร์ติชันแบบคลาสสิกอาจใช้ไม่ได้ (เช่นการแบ่งพาร์ติชันแบบสเปกตรัม , Metis ^{[ 7 ]} ) เนื่องจากต้องเข้าถึงข้อมูลกราฟทั้งหมดเพื่อดำเนินการในระดับสากล สำหรับสถานการณ์ขนาดใหญ่เช่นนี้ จะใช้การแบ่งพาร์ติชันกราฟแบบกระจายเพื่อดำเนินการแบ่งพาร์ติชันผ่านการดำเนินการในพื้นที่แบบอะซิงโครนัสเท่านั้น

scikit-learnใช้ การจัด กลุ่มสเปกตรัมโดยกำหนดการแบ่งส่วนจากเวกเตอร์ลักษณะเฉพาะของ เมทริกซ์ ลาปลาเซียนของกราฟสำหรับกราฟดั้งเดิมที่คำนวณโดยARPACKหรือโดย ตัวแก้ LOBPCGพร้อมการปรับสภาพล่วงหน้าแบบมัลติ กริด^{[ 9 ]}

METIS ^{[ 7 ]}เป็นตระกูลการแบ่งพาร์ติชันกราฟโดย Karypis และ Kumar ในบรรดาตระกูลนี้ kMetis มีเป้าหมายเพื่อเพิ่มความเร็วในการแบ่งพาร์ติชัน hMetis ^{[ 8 ]}ใช้กับไฮเปอร์กราฟและมีเป้าหมายที่คุณภาพของพาร์ติชัน และ ParMetis ^{[ 7 ]}เป็นการใช้งานแบบขนานของอัลกอริทึมการแบ่งพาร์ติชันกราฟ Metis

KaHyPar ^{[ 18 ] [ 19 ] [ 20 ]}เป็นเฟรมเวิร์กการแบ่งพาร์ติชันไฮเปอร์กราฟหลายระดับที่ให้ขั้นตอนวิธีแบ่งพาร์ติชันแบบ k ทางโดยตรงและการแบ่งครึ่งแบบเรียกซ้ำ โดยจะนำแนวทางหลายระดับมาใช้ในเวอร์ชันที่รุนแรงที่สุด โดยการลบจุดยอดเพียงจุดเดียวในแต่ละระดับของลำดับชั้น การใช้ แนวทาง nระดับที่ละเอียดมากนี้ร่วมกับฮิวริสติกการค้นหาแบบโลคอลที่แข็งแกร่ง ทำให้สามารถคำนวณโซลูชันที่มีคุณภาพสูงมากได้

Scotch ^{[ 21 ]}เป็นเฟรมเวิร์กการแบ่งกราฟโดย Pellegrini โดยใช้การแบ่งครึ่งหลายระดับแบบเรียกซ้ำและรวมถึงเทคนิคการแบ่งแบบลำดับและแบบขนาน

Jostle ^{[ 22 ]}เป็นตัวแก้ปัญหาการแบ่งพาร์ติชันกราฟแบบลำดับและขนานที่พัฒนาโดย Chris Walshaw เวอร์ชันเชิงพาณิชย์ของตัวแบ่งพาร์ติชันนี้เรียกว่า NetWorks

ปาร์ตี้^{[ 23 ]}ดำเนินการเฟรมเวิร์ก Bubble/shape-optimized และอัลกอริธึม Helpful Sets

แพ็คเกจซอฟต์แวร์ DibaP ^{[ 24 ] และ PDibaP [ 25 ]}ซึ่งเป็นเวอร์ชันขนาน MPI ของ Meyerhenke ใช้เฟรมเวิร์ก Bubble โดยใช้การแพร่กระจาย นอกจากนี้ DibaP ยังใช้เทคนิคที่ใช้ AMG สำหรับการลดขนาดและการแก้ปัญหาระบบเชิงเส้นที่เกิดขึ้นในแนวทางการแพร่กระจาย

Sanders และ Schulz ได้เผยแพร่แพ็กเกจการแบ่งพาร์ติชันกราฟ KaHIP ^{[ 26 ]} (Karlsruhe High Quality Partitioning) ซึ่งใช้ตัวอย่างเช่น วิธีการตามการไหล การค้นหาแบบโลคัลที่เน้นเฉพาะที่มากขึ้น และเมตาฮิวริสติกแบบขนานและแบบลำดับหลายรายการ

เครื่องมือ Parkway ^{[ 27 ]}โดย Trifunovic และ Knottenbelt รวมถึง Zoltan ^{[ 28 ]}โดย Devine et al. มุ่งเน้นไปที่การแบ่งพาร์ติชันไฮเปอร์กราฟ

• Bichot, Charles-Edmond; Siarry, Patrick (2011). การแบ่งพาร์ติชันกราฟ: การเพิ่มประสิทธิภาพและการประยุกต์ใช้ ISTE – Wiley. ISBN 978-1-84821-233-6.