อัลกอริทึม Leidenเป็นอัลกอริทึมการตรวจจับชุมชนที่พัฒนาโดย Traag et al ^{[ 1 ]}ที่มหาวิทยาลัย Leidenได้รับการพัฒนาโดยเป็นการดัดแปลง วิธีการ Louvainเช่นเดียวกับวิธีการ Louvain อัลกอริทึม Leiden พยายามเพิ่มประสิทธิภาพโมดูลาริตีในการแยกชุมชนจากเครือข่าย อย่างไรก็ตาม อัลกอริทึมนี้ได้แก้ไขปัญหาสำคัญที่มีอยู่ในวิธีการ Louvain ซึ่งได้แก่ ชุมชนที่เชื่อมต่อกันไม่ดี และข้อจำกัดด้านความละเอียดของโมดูลาริตี

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

ตัวอย่างเช่น ลองพิจารณากราฟต่อไปนี้:

ในกราฟนี้มีชุมชนอยู่สามแห่ง (แต่ละสีแทนชุมชนหนึ่งๆ) นอกจากนี้ โหนด "สะพาน" ตรงกลาง (แสดงด้วยวงกลมเพิ่มเติม) เป็นสมาชิกของชุมชนที่แสดงด้วยโหนดสีน้ำเงิน ทีนี้ลองพิจารณาผลลัพธ์ของขั้นตอนการย้ายโหนด ซึ่งจะรวมชุมชนที่แสดงด้วยโหนดสีแดงและสีเขียวเข้าเป็นชุมชนเดียว (เนื่องจากทั้งสองชุมชนมีการเชื่อมต่อกันอย่างมาก):

ที่น่าสังเกตคือ โหนด "สะพาน" ตรงกลางกลายเป็นสมาชิกของชุมชนสีแดงขนาดใหญ่ขึ้นหลังจากมีการย้ายโหนด (เนื่องจากลักษณะโลภของอัลกอริทึมการย้ายโหนดในพื้นที่) ในวิธีการของ Louvain การรวมดังกล่าวจะตามมาด้วยขั้นตอนการรวมกราฟทันที อย่างไรก็ตาม สิ่งนี้ทำให้เกิดการตัดขาดระหว่างสองส่วนที่แตกต่างกันของชุมชนที่แสดงโดยโหนดสีน้ำเงิน ในอัลกอริทึมของ Leiden กราฟจะได้รับการปรับปรุงให้ดียิ่งขึ้นแทน:

ขั้นตอนการปรับปรุงของอัลกอริทึมไลเดนทำให้มั่นใจได้ว่าโหนด "สะพาน" ตรงกลางจะยังคงอยู่ในกลุ่มสีน้ำเงิน เพื่อให้มั่นใจว่าโหนดนั้นยังคงสภาพสมบูรณ์และเชื่อมต่ออยู่ แม้ว่าการเพิ่มโหนด "สะพาน" ตรงกลางเข้าไปในกลุ่มสีแดงอาจช่วยเพิ่มความเป็นโมดูลาร์ได้ก็ตาม

ก่อนที่จะนิยามอัลกอริทึมไลเดนเราควรทำความเข้าใจส่วนประกอบบางอย่างของกราฟเสีย ก่อน

วิธีการแบ่งกลุ่มชุมชนเป็นส่วนสำคัญของอัลกอริทึมไลเดน การตัดสินใจแบ่งกลุ่มอาจขึ้นอยู่กับวิธีการวัดคุณภาพของกลุ่มเหล่านั้น นอกจากนี้ ตัวชี้วัดหลายตัวยังมีพารามิเตอร์ของตัวเองที่สามารถเปลี่ยนแปลงผลลัพธ์ของกลุ่มได้

ทำความเข้าใจพารามิเตอร์ความละเอียด/ขีดจำกัดความละเอียดของแบบจำลอง Potts

โดยทั่วไปแล้วโมเดล Potts เช่น RB หรือ CPM จะมีพารามิเตอร์ความละเอียดในการคำนวณ^{[ 3 ] [ 6 ]}โมเดล Potts ถูกนำมาใช้เพื่อแก้ปัญหาข้อจำกัดด้านความละเอียดที่มีอยู่ในการตรวจจับชุมชนโดยอาศัยการเพิ่มค่าโมดูลาริตีสูงสุด ปัญหาข้อจำกัดด้านความละเอียดคือ สำหรับกราฟบางกราฟ การเพิ่มค่าโมดูลาริตีสูงสุดอาจทำให้โครงสร้างย่อยของกราฟรวมกันและกลายเป็นชุมชนเดียว ส่งผลให้โครงสร้างขนาดเล็กสูญหายไป^{[ 7 ]}พารามิเตอร์ความละเอียดเหล่านี้ช่วยให้สามารถปรับเปลี่ยนวิธีการโมดูลาริตีที่อยู่ติดกันให้เหมาะสมกับความต้องการของผู้ใช้ที่ใช้อัลกอริธึม Leiden เพื่อพิจารณาโครงสร้างย่อยขนาดเล็กที่ระดับความละเอียดที่กำหนด

ภาพทางด้านขวามือแสดงให้เห็นว่าเหตุใดความละเอียดจึงเป็นพารามิเตอร์ที่มีประโยชน์เมื่อใช้ตัวชี้วัดคุณภาพตามโมดูลาร์ ในกราฟแรก โมดูลาร์จะจับเฉพาะโครงสร้างขนาดใหญ่ของกราฟเท่านั้น แต่ในตัวอย่างที่สอง ตัวชี้วัดคุณภาพที่มีรายละเอียดมากกว่าอาจตรวจจับโครงสร้างย่อยทั้งหมดในกราฟได้

อัลกอริทึม Leiden เริ่มต้นด้วยกราฟของโหนดที่ไม่เป็นระเบียบ(a)และจัดเรียงโดยการแบ่งส่วนเพื่อเพิ่มค่าโมดูลาริตี ให้สูงสุด (ความแตกต่างของคุณภาพระหว่างส่วนที่สร้างขึ้นกับส่วนแบบสุ่มสมมุติของชุมชน) วิธีการที่ใช้คล้ายกับอัลกอริทึม Louvain ยกเว้นว่าหลังจากย้ายแต่ละโหนดแล้ว มันยังพิจารณาถึงเพื่อนบ้านของโหนดนั้นที่ยังไม่ได้อยู่ในชุมชนที่มันถูกวางไว้ด้วย กระบวนการนี้ส่งผลให้เกิดการแบ่งส่วนแรกของเรา(b)ซึ่งเรียกอีกอย่างว่า${\displaystyle {\mathcal {P}}}$จากนั้นอัลกอริทึมจะปรับปรุงพาร์ติชันนี้โดยการวางแต่ละโหนดลงในชุมชนของตนเองก่อน แล้วจึงย้ายโหนดเหล่านั้นจากชุมชนหนึ่งไปยังอีกชุมชนหนึ่งเพื่อเพิ่มค่าโมดูลาริตี้ให้สูงสุด อัลกอริทึมจะทำซ้ำเช่นนี้ไปเรื่อยๆ จนกว่าแต่ละโหนดจะได้รับการเยี่ยมชมและย้าย และแต่ละชุมชนได้รับการปรับปรุงแล้ว ซึ่งจะสร้างพาร์ติชัน(c)ซึ่งเป็นพาร์ติชันเริ่มต้นของ${\displaystyle {\mathcal {P}}_{\text{ปรับปรุงแล้ว}}}$จากนั้นจึงสร้างเครือข่ายรวม(d)โดยเปลี่ยนแต่ละชุมชนให้เป็นโหนด${\displaystyle {\mathcal {P}}_{\text{ปรับปรุงแล้ว}}}$ใช้เป็นพื้นฐานสำหรับเครือข่ายรวมในขณะที่${\displaystyle {\mathcal {P}}}$ใช้ในการสร้างพาร์ติชันเริ่มต้น เนื่องจากเราใช้พาร์ติชันดั้งเดิม${\displaystyle {\mathcal {P}}}$ในขั้นตอนนี้ เราต้องเก็บรักษาข้อมูลนี้ไว้เพื่อให้สามารถนำไปใช้ในการทำซ้ำครั้งต่อไปได้ ขั้นตอนเหล่านี้รวมกันเป็นการทำซ้ำครั้งแรกของอัลกอริธึม

ในการทำซ้ำครั้งต่อๆ ไป โหนดของเครือข่ายโดยรวม (ซึ่งแต่ละโหนดแทนชุมชน) จะถูกนำไปวางไว้ในชุมชนของตนเองอีกครั้ง จากนั้นจึงจัดเรียงตามค่าโมดูลาร์เพื่อสร้างเครือข่ายใหม่${\displaystyle {\mathcal {P}}_{\text{ปรับปรุงแล้ว}}}$ก่อให้เกิด(e)ในกราฟด้านบน ในกรณีที่แสดงโดยกราฟ โหนดต่างๆ ได้ถูกจัดเรียงอย่างเหมาะสมแล้ว ดังนั้นจึงไม่มีการเปลี่ยนแปลงใดๆ เกิดขึ้น ส่งผลให้เกิดการแบ่งกลุ่ม(f)จากนั้นโหนดของการแบ่งกลุ่ม(f)จะถูกรวมเข้าด้วยกันอีกครั้งโดยใช้วิธีเดียวกันกับก่อนหน้านี้ โดยใช้การแบ่งกลุ่มเดิม${\displaystyle {\mathcal {P}}}$ยังคงถูกเก็บรักษาไว้ ส่วนนี้ของอัลกอริธึมจะทำงานซ้ำไปเรื่อยๆ จนกว่าแต่ละโหนดรวมจะอยู่ในเครือข่ายของตนเอง ซึ่งหมายความว่าจะไม่สามารถปรับปรุงเพิ่มเติมได้อีกต่อไป

อัลกอริทึม Leiden ประกอบด้วยสามขั้นตอนหลัก ได้แก่ การย้ายโหนดในพื้นที่ การปรับปรุงพาร์ติชัน และการรวมเครือข่ายตามพาร์ติชันที่ปรับปรุงแล้ว ฟังก์ชันทั้งหมดในขั้นตอนต่อไปนี้จะถูกเรียกใช้โดยใช้ฟังก์ชันหลัก Leiden ของเรา ซึ่งแสดงไว้ด้านล่าง วิธี Fast Louvain ได้รับการยืมโดยผู้เขียน Leiden จาก "A Simple Acceleration Method for the Louvain Algorithm" ^{[ 8 ]}

ฟังก์ชันการตรวจจับชุมชน Leiden (กราฟ G, พาร์ติชัน P) ทำ P = fast_louvain_move_nodes(G, P) /* เรียกใช้ฟังก์ชันเพื่อย้ายโหนดไปยังกลุ่มชุมชน (รายละเอียดเพิ่มเติมอยู่ในฟังก์ชันด้านล่าง) */ เสร็จสิ้น = (|P| == |V(G)|) /* หากจำนวนพาร์ติชันใน P เท่ากับจำนวนโหนดใน G ให้ตั้งค่าแฟล็ก done เป็น True เพื่อสิ้นสุดลูป do-while เนื่องจากนั่นหมายความว่าแต่ละโหนดได้ถูกรวมเข้าเป็นกลุ่มของตนเองแล้ว */ หากไม่ดำเนินการ P_refined = get_p_refined(G, P) /* นี่คือส่วนสำคัญที่ทำให้ไลเดนแตกต่างจากลูแวน เนื่องจากความละเอียดของการแบ่งส่วนนี้บังคับให้เฉพาะโหนดที่มีการเชื่อมต่อที่ดีภายในชุมชนเท่านั้นที่จะถูกพิจารณาว่าถูกย้ายออกจากชุมชน (รายละเอียดเพิ่มเติมในฟังก์ชัน refine_partition_subset ด้านล่าง) */ G = aggregate_graph(G, P_refined) /* รวบรวมกลุ่มชุมชนเข้าเป็นโหนดเดียวสำหรับการวนซ้ำครั้งต่อไป (รายละเอียดอยู่ในฟังก์ชันด้านล่าง) */ P = {{v | v ⊆ C, v ∈ V (G)} | C ∈ P} /* บรรทัดนี้จะนำโหนดจากกลุ่มต่างๆ ใน ​​P มาแยกย่อย โดยแต่ละโหนดจะถูกมองว่าเป็นกลุ่มที่มีสมาชิกเพียงตัวเดียว (กลุ่มที่ประกอบด้วยโหนดเดียว) */ จบถ้า ในขณะที่ยังไม่ได้ดำเนินการ return flattened(P) /* คืนค่าพาร์ติชันสุดท้ายที่โหนดทั้งหมดของ G ถูกจัดอยู่ในชุมชนเดียว */ สิ้นสุดฟังก์ชัน

ขั้นตอนที่ 1: การย้ายโหนดในพื้นที่

ขั้นแรก เราจะย้ายโหนดจาก${\displaystyle {\mathcal {P}}}$แบ่งกลุ่มไปยังชุมชนใกล้เคียงเพื่อเพิ่มความเป็นโมดูลาร์ ให้สูงสุด (ความแตกต่างของคุณภาพระหว่างกลุ่มที่สร้างขึ้นกับกลุ่มชุมชนที่สุ่มขึ้นมาตามสมมติฐาน) ในภาพด้านบน กลุ่มโหนดเริ่มต้นที่ยังไม่ได้เรียงลำดับแสดงด้วยกราฟทางด้านซ้าย โดยสีเฉพาะของแต่ละโหนดแสดงว่าโหนดนั้นยังไม่ได้เป็นส่วนหนึ่งของชุมชนใด ๆ กราฟทางด้านขวาแสดงผลลัพธ์ของขั้นตอนนี้ ซึ่งก็คือกราฟที่เรียงลำดับแล้ว${\displaystyle {\mathcal {P}}}$โปรดสังเกตว่าโหนดทั้งหมดได้ถูกย้ายไปยังหนึ่งในสามชุมชน ซึ่งแสดงโดยสีของโหนด (สีแดง สีน้ำเงิน และสีเขียว)

ฟังก์ชัน fast_louvain_move_nodes(Graph G, Partition P) Q = queue(V(G)) /* นำโหนดทั้งหมดของ G ไปใส่ในคิวเพื่อให้แน่ใจว่าทุกโหนดได้รับการเยี่ยมชมแล้ว */ ในขณะที่ Q ยังไม่ว่างเปล่า v = Q.pop_front() /* เลือกโหนดแรกจากคิวเพื่อเยี่ยมชม */ C_prime = arg maxC∈P∪∅ ∆HP(v → C) /* กำหนดให้ C_prime เป็นชุมชนใน P หรือเซตว่าง (ไม่มีชุมชน) ที่ให้ค่าเพิ่มขึ้นสูงสุดในฟังก์ชันคุณภาพ H เมื่อย้ายโหนด v เข้าไปในชุมชนนั้น */ ถ้า ∆HP(v → C_prime) > 0 /* พิจารณาเฉพาะโหนดที่เคลื่อนย้ายซึ่งจะส่งผลให้ฟังก์ชันคุณภาพเปลี่ยนแปลงไปในทางบวกเท่านั้น */ v → C_prime /* ย้ายโหนด v ไปยังชุมชน C_prime */ N = {u | (u, v) ∈ E(G), u !∈ C_prime} /* สร้างเซต N ของโหนดที่เป็นเพื่อนบ้านโดยตรงของ v แต่ไม่ได้อยู่ในชุมชน C_prime */ Q.add(N - Q) /* เพิ่มโหนดทั้งหมดจาก N ไปยังคิว ยกเว้นโหนดที่อยู่ใน Q อยู่แล้ว */ จบถ้า return P /* ส่งคืนพาร์ติชันที่อัปเดตแล้ว */ สิ้นสุดฟังก์ชัน 

ขั้นตอนที่ 2: การปรับปรุงพาร์ติชั่นให้ดียิ่งขึ้น

ถัดไป โหนดแต่ละโหนดในเครือข่ายจะถูกกำหนดให้กับชุมชนของตนเอง จากนั้นจึงย้ายโหนดเหล่านั้นจากชุมชนหนึ่งไปยังอีกชุมชนหนึ่งเพื่อเพิ่มความเป็นโมดูลาร์ให้สูงสุด กระบวนการนี้เกิดขึ้นซ้ำๆ จนกว่าทุกโหนดจะได้รับการเยี่ยมชมและย้าย ซึ่งคล้ายคลึงกับการสร้าง...${\displaystyle {\mathcal {P}}}$ยกเว้นว่าแต่ละชุมชนจะได้รับการปรับปรุงหลังจากมีการย้ายโหนด ผลลัพธ์ที่ได้คือการแบ่งกลุ่มเริ่มต้นของเราสำหรับ${\displaystyle {\mathcal {P}}_{\text{ปรับปรุงแล้ว}}}$ดังแสดงในภาพด้านขวา โปรดทราบว่าเรากำลังติดตามชุมชนต่างๆ จากด้วยเช่นกัน${\displaystyle {\mathcal {P}}}$ซึ่งแสดงโดยพื้นหลังสีต่างๆ ที่อยู่ด้านหลังโหนดเหล่านั้น

ฟังก์ชัน get_p_refined(กราฟ G, พาร์ติชัน P) P_refined = get_singleton_partition(G) /* กำหนดให้แต่ละโหนดใน G อยู่ในชุมชนเดี่ยว (ชุมชนที่ประกอบด้วยโหนดเพียงโหนดเดียว) */ สำหรับ C ∈ P P_refined = refine_partition_subset(G, P_refined, C) /* ปรับปรุงการแบ่งกลุ่มย่อยสำหรับแต่ละชุมชนใน P_refined */ สิ้นสุดสำหรับ return P_refined /* คืนค่าพาร์ติชันที่ได้รับการปรับปรุงใหม่ */ ฟังก์ชัน refine_partition_subset(Graph G, Partition P, Subset S) R = {v | v ∈ S, E(v, S − v) ≥ γ * degree(v) * (degree(S) − degree(v))} /* สำหรับโหนด v ซึ่งเป็นสมาชิกของเซตย่อย S ให้ตรวจสอบว่า E(v, Sv) (ขอบของ v ที่เชื่อมต่อกับสมาชิกอื่นๆ ของกลุ่ม S โดยไม่รวม v เอง) มีค่ามากกว่าปัจจัยการปรับขนาดที่กำหนดหรือไม่ degree(v) คือดีกรีของโหนด v และ degree(S) คือดีกรีรวมของโหนดในเซตย่อย S ข้อความนี้โดยพื้นฐานแล้วต้องการว่าหากลบ v ออกจากเซตย่อย กลุ่มจะยังคงอยู่เหมือนเดิม */ สำหรับ v ∈ R ถ้า v อยู่ใน singleton_community /* ถ้าโหนด v อยู่ใน singleton community หมายความว่าเป็นโหนดเดียว */ T = {C | C ∈ P, C ⊆ S, E(C, S − C) ≥ γ * degree(C) · (degree(S) − degree(C)} /* สร้างเซต T ของกลุ่มชุมชน โดยที่ E(C, S - C) (จำนวนขอบระหว่างชุมชน C และเซตย่อย S โดยไม่รวมขอบระหว่างชุมชน C กับตัวมันเอง) มีค่ามากกว่าเกณฑ์ เกณฑ์ในที่นี้คือ γ * degree(C) · (degree(S) − degree(C)) */ Pr(C_prime = C) ~ exp(1/θ ∆HP(v → C) ถ้า ∆HP(v → C) ≥ 0 0 ในกรณีอื่น ๆ สำหรับ C ∈ T /* หากการย้ายโหนด v ไปยัง C_prime เปลี่ยนแปลงฟังก์ชันคุณภาพไปในทิศทางบวก ให้กำหนดความน่าจะเป็นที่ชุมชนของ v เป็น exp(1/θ * ∆HP(v → C)) มิฉะนั้นให้กำหนดเป็น 0 สำหรับทุกชุมชนใน T */ v → C_prime /* ย้ายโหนด v ไปยังกลุ่ม C_prime แบบสุ่มด้วยความน่าจะเป็นที่เป็นบวก */ จบถ้า สิ้นสุดสำหรับ ส่งคืน P /* ส่งคืนพาร์ติชันที่ปรับปรุงแล้ว */ สิ้นสุดฟังก์ชัน 

ขั้นตอนที่ 3: การรวมเครือข่าย

จากนั้นเราจะแปลงชุมชนแต่ละแห่งเป็น${\displaystyle {\mathcal {P}}_{\text{ปรับปรุงแล้ว}}}$รวมเป็นโหนดเดียว สังเกตว่า ดังที่แสดงในภาพด้านบน ชุมชนของ${\displaystyle {\mathcal {P}}}$ใช้สำหรับจัดเรียงโหนดรวมเหล่านี้หลังจากสร้างเสร็จแล้ว

ฟังก์ชัน aggregate_graph(Graph G, Partition P) V = P /* กำหนดกลุ่มชุมชนของ P เป็นโหนดแต่ละโหนดของกราฟ */ E = {(C, D) | (u, v) ∈ E(G), u ∈ C ∈ P, v ∈ D ∈ P} /* ถ้า u เป็นสมาชิกของเซตย่อย C ของ P และ v เป็นสมาชิกของเซตย่อย D ของ P และ u กับ v มีเส้นเชื่อมร่วมกันใน E(G) เราจะเพิ่มเส้นเชื่อมระหว่าง C กับ D ในกราฟใหม่ */ return Graph(V, E) /* คืนค่าโหนดและขอบของกราฟใหม่ */ สิ้นสุดฟังก์ชัน ฟังก์ชัน get_singleton_partition(Graph G) return {{v} | v ∈ V (G)} /* นี่คือฟังก์ชันที่เรากำหนดแต่ละโหนดใน G ให้กับชุมชนเดี่ยว (ชุมชนที่อยู่โดดเดี่ยว) */ สิ้นสุดฟังก์ชัน 

เราทำซ้ำขั้นตอนเหล่านี้จนกระทั่งแต่ละชุมชนมีโหนดเพียงโหนดเดียว โดยแต่ละโหนดเหล่านี้จะแสดงถึงกลุ่มของโหนดจากเครือข่ายดั้งเดิมที่เชื่อมต่อกันอย่างแน่นหนา

อัลกอริทึม Leiden ทำงานได้ดีเยี่ยมในการสร้างการแบ่งกลุ่มที่มีคุณภาพ ซึ่งจัดวางโหนดต่างๆ ไว้ในกลุ่มที่แตกต่างกัน อย่างไรก็ตาม Leiden สร้างการแบ่งกลุ่มแบบตายตัว หมายความว่าโหนดสามารถอยู่ในกลุ่มใดกลุ่มหนึ่งได้เท่านั้น ในเครือข่ายหลายประเภท เช่น เครือข่ายสังคม โหนดอาจอยู่ในหลายกลุ่ม และในกรณีเช่นนี้ อาจควรใช้วิธีการอื่นแทน

Leiden มีประสิทธิภาพมากกว่า Louvain แต่ในกรณีของกราฟขนาดใหญ่อาจส่งผลให้เวลาในการประมวลผลนานขึ้น ความก้าวหน้าล่าสุดได้เพิ่มความเร็วโดยใช้ "การใช้งานแบบมัลติคอร์แบบขนานของอัลกอริทึม Leiden" ^{[ 9 ]}

อัลกอริทึมของไลเดนช่วยแก้ปัญหาข้อจำกัดด้านความละเอียดได้มาก อย่างไรก็ตาม ยังคงมีความเป็นไปได้ที่โครงสร้างย่อยขนาดเล็กอาจถูกมองข้ามไปในบางกรณี การเลือกค่าพารามิเตอร์แกมมามีความสำคัญอย่างยิ่งเพื่อให้แน่ใจว่าโครงสร้างเหล่านี้จะไม่ถูกมองข้าม เนื่องจากค่านี้อาจแตกต่างกันอย่างมากในแต่ละกราฟ