วิธีการลูแวน

Q: ข้อมูลสำคัญเกี่ยวกับ วิธีการลูแวน

วิธีการตรวจจับชุมชนแบบ Louvainเป็น วิธี การเพิ่มประสิทธิภาพแบบโลภ (greedy optimization)ที่มุ่งหมายเพื่อแยกชุมชนที่ไม่ทับซ้อนกันจากเครือข่าย ขนาดใหญ่ ที่สร้างโดยBlondel et al .

Q: ความเป็นโมดูล

ค่าที่ต้องการปรับให้เหมาะสมที่สุดคือ ค่าโมดูลาร์ ซึ่งกำหนดเป็นค่าในช่วง [ − 1 , 1 ] {\displaystyle [-1,1]} ซึ่งวัดความหนาแน่นของลิงก์ภายในชุมชนเมื่อเทียบกับลิงก์ระหว่างชุมชน [ 1 ] สำหรับกราฟแบบถ่วงน้ำหนัก ค่าโมดูลาริตีจะถูกกำหนดดังนี้:

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

การเพิ่มประสิทธิภาพแบบโมดูลาร์

แรงบันดาลใจสำหรับวิธีการตรวจจับชุมชน นี้ มาจากการปรับค่าโมดูลาร์ ให้ เหมาะสมที่สุดในขณะที่อัลกอริทึมดำเนินไป โมดูลาร์ลิตี้เป็นค่ามาตราส่วนระหว่าง -1 (การจัดกลุ่มแบบไม่เป็นโมดูลาร์) และ 1 (การจัดกลุ่มแบบโมดูลาร์อย่างสมบูรณ์) ซึ่งวัดความหนาแน่นสัมพัทธ์ของขอบภายในชุมชนเมื่อเทียบกับขอบภายนอกชุมชน การปรับค่านี้ให้เหมาะสมที่สุดในทางทฤษฎีจะส่งผลให้การจัดกลุ่มโหนดของเครือข่ายที่กำหนดนั้นดีที่สุดเท่าที่จะเป็นไปได้ แต่เนื่องจากการตรวจสอบการจัดเรียงโหนดเป็นกลุ่มที่เป็นไปได้ทั้งหมดนั้นทำได้ยาก จึงมีการใช้อัลกอริทึมแบบฮิวริสติกแทน

ในการตรวจจับชุมชนด้วยวิธี Louvain ขั้นแรกจะค้นหาชุมชนขนาดเล็กโดยการปรับโมดูลาริตี้ให้เหมาะสมในระดับท้องถิ่นบนโหนดทั้งหมด จากนั้นแต่ละชุมชนขนาดเล็กจะถูกจัดกลุ่มเป็นโหนดเดียวและทำซ้ำขั้นตอนแรก วิธีนี้คล้ายกับวิธีของ Clauset, Newman และ Moore ก่อนหน้านี้^{[ 2 ]}ที่เชื่อมต่อชุมชนที่การรวมกันทำให้โมดูลาริตี้เพิ่มขึ้นมากที่สุด แม้ว่าอัลกอริทึม Louvain จะสามารถระบุโครงสร้างชุมชนได้อย่างถูกต้องเมื่อมีหลักฐานที่แข็งแกร่งเพียงพอในเครือข่ายเทียม โดยเฉพาะอย่างยิ่งเครือข่ายที่สุ่มตัวอย่างจากแบบจำลองบล็อกสุ่ม แบบเรียงลำดับ ^{[ 3 ]}แต่ก็มีแนวโน้มที่จะค้นหาชุมชนปลอมในกราฟสุ่ม^{[ 4 ]}และได้รับการพิสูจน์แล้วว่ามีการโอเวอร์ฟิตข้อมูลเชิงประจักษ์ อย่างเป็นระบบ ^{[ 5 ]}^{[ 6 ]}

คำอธิบายอัลกอริธึม

ความเป็นโมดูล

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

$Q={\frac {1}{2m}}\sum _{i=1}^{N}\sum _{j=1}^{N}{\bigg [}A_{ij}-{\frac {k_{i}k_{j}}{2m}}{\bigg ]}\delta (c_{i},c_{j}),$

ที่ไหน:

$A_{ij}$ แสดงถึงค่าน้ำหนักของขอบระหว่างโหนด $i$ และ $j$ ดูที่ เมท ริกซ์ความประชิด
⁠ $k_{i}$ และ $k_{j}$ คือผลรวมของน้ำหนักของขอบที่เชื่อมต่อกับโหนด $i$ และ $j$ ตามลำดับ
$m$ คือผลรวมของน้ำหนักขอบทั้งหมดในกราฟ
$N$ คือจำนวนโหนดทั้งหมดในกราฟ;
⁠ $c_{i}$ และ $c_{j}$ คือชุมชนที่โหนด $i$ และ $j$ เป็นสมาชิกอยู่ และ
$\delta$ คือฟังก์ชันเดลต้าโครเนกเกอร์ :

${\begin{aligned}\delta (c_{i},c_{j})&={\begin{cases}1&{\text{ถ้า }}c_{i}{\text{ และ }}c_{j}{\text{ เป็นกลุ่มเดียวกัน}}\\0&{\text{ในกรณีอื่น ๆ}}\end{cases}}\end{aligned}}$

จากสมการข้างต้น ค่าโมดูลาร์ของชุมชน $c$ สามารถคำนวณได้ดังนี้: ^{[ 7 ]}

${\begin{aligned}Q_{c}&={\dfrac {1}{2m}}\sum _{i}\sum _{j}A_{ij}\mathbf {1} \left\{c_{i}=c_{j}=c\right\}-\left(\sum _{i}{\dfrac {k_{i}}{2m}}\mathbf {1} \left\{c_{i}=c\right\}\right)^{2}\\&={\frac {\Sigma _{in}}{2m}}-\left({\frac {\Sigma _{tot}}{2m}}\right)^{2}\end{aligned}}$

ที่ไหน

$\Sigma _{in}$ คือผลรวมของน้ำหนักขอบระหว่างโหนดภายในชุมชน $c$ (แต่ละขอบจะถูกพิจารณา 2 ครั้ง); และ
$\Sigma _{tot}$ คือผลรวมของน้ำหนักขอบทั้งหมดสำหรับโหนดภายในชุมชน (รวมถึงขอบที่เชื่อมไปยังชุมชนอื่น ๆ)

เนื่องจากโหนดในชุมชนที่แตกต่างกันไม่ได้มีส่วนร่วมในค่าโมดูลาร์ $Q$ ดังนั้นจึงสามารถเขียนได้ดังนี้:

$Q=\sum _{c}Q_{c}$

อัลกอริทึมวิธีลูแวน

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

ระยะที่ 1

แต่ละโหนดในเครือข่ายจะถูกกำหนดให้เป็นส่วนหนึ่งของชุมชนของตนเอง

วิธีการของลูแวนเริ่มต้นด้วยการพิจารณาแต่ละโหนด $v$ ในกราฟว่าเป็นชุมชนของตนเอง ดังแสดงในรูปที่ 1 ซึ่งแต่ละจุด (แทนโหนด) มีสีเฉพาะ (แสดงว่าโหนดนั้นอยู่ในชุมชนใด)

โหนดต่างๆ ถูกจัดกลุ่มเป็นชุมชน

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

ฟังก์ชัน moveNodes(Graph G, Partition P):  ทำ  ค่าโมดูลาร์เก่า <- ค่าโมดูลาร์ปัจจุบันของพาร์ติชั่น  สำหรับ v ใน V(G) ให้ทำ  # ค้นหาชุมชนที่ทำให้เกิดการเพิ่มขึ้นของความเป็นโมดูลมากที่สุดเมื่อย้าย v เข้าไปอยู่ในชุมชนนั้น  C' <- argmax(delta_Q) # delta_Q คือการเปลี่ยนแปลงของค่าโมดูลาร์  ถ้า delta_Q > 0 แล้ว  ย้าย v เข้าไปใน C'  จบถ้า  สิ้นสุดสำหรับ  อัปเดตค่าโมดูลาร์ปัจจุบันของพาร์ติชัน  ในขณะที่ค่าโมดูลาร์ปัจจุบันของพาร์ติชั่นมากกว่าค่าโมดูลาร์เก่า  ส่งคืน P ฟังก์ชันสิ้นสุด

^{[ 8 ]}

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

ระยะที่ 2

ชุมชนต่างๆ ถูกลดเหลือเพียงโหนดเดียว

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

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

ฟังก์ชัน aggregateGraph(Graph G, Partition P):  วี <- พี  E <- [(A,B) | (x,y) อยู่ใน E(G), x อยู่ใน A และ A อยู่ใน P, y อยู่ใน B และ B อยู่ใน P]  ส่งคืนกราฟ(V,E) ฟังก์ชันสิ้นสุด

^{[ 8 ]}

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

รหัสเทียมด้านล่างแสดงให้เห็นว่าฟังก์ชันสองฟังก์ชันก่อนหน้านี้ทำงานร่วมกันอย่างไรเพื่อให้กระบวนการเสร็จสมบูรณ์

ฟังก์ชัน louvain(กราฟ G, พาร์ติชัน P): ทำ P <- moveNodes(G, P) done <- length(P) == length(V(G)) # แต่ละชุมชนเป็นโหนดเดียว แม้ว่าจะรัน moveNodes ก็ตาม หากไม่ดำเนินการดังกล่าว: G <- aggregateGraph(G, P) P <- พาร์ติชั่นเดี่ยว (G) จบถ้า ในขณะที่ยังไม่ได้ดำเนินการ ฟังก์ชันสิ้นสุด ฟังก์ชัน singletonPartition(Graph G): ส่งคืน [{v} | v อยู่ใน V(G)] # แต่ละโหนดถูกวางไว้ในชุมชนของตนเอง ฟังก์ชันสิ้นสุด

^{[ 8 ]}

ความซับซ้อนเชิงเวลา

โดยทั่วไป วิธีการของ Louvain ถือว่ามีความซับซ้อนเชิงเวลาอยู่ที่ $O(n\log {}n)$ ริชาร์ด บลอนเดล ผู้ร่วมเขียนบทความที่ตีพิมพ์วิธีการของลูแวนเป็นครั้งแรก ดูเหมือนจะสนับสนุนแนวคิดนี้^{[ 9 ]}แต่แหล่งข้อมูลอื่นอ้างว่าความซับซ้อนของเวลาเป็น "เชิงเส้นตามจำนวนลิงก์ในกราฟ" ^{[ 10 ]}ซึ่งหมายความว่าความซับซ้อนของเวลาจะเป็น $O(m)$ โดยที่ $m$ คือจำนวนขอบในกราฟ น่าเสียดายที่ไม่มีแหล่งข้อมูลใดเผยแพร่การวิเคราะห์ความซับซ้อนเชิงเวลาของวิธีการ Louvain ดังนั้นจึงได้พยายามทำการวิเคราะห์ในที่นี้

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

ถ้าหากในแต่ละรอบของการทำงานของ $louvain$ $ฟังก์ชัน moveNodes$ สามารถย้ายโหนดเข้าไปในกลุ่มได้เพียงโหนดเดียวเท่านั้น $aggregateGraph$ ก็จะสามารถลดขนาดของกราฟได้เพียงหนึ่งโหนด ซึ่งจะทำให้ $louvain$ ทำงานซ้ำ $v$ ครั้ง เนื่องจาก $moveNodes$ วนซ้ำผ่านทุกโหนดในกราฟ ดังนั้นความซับซ้อนของเวลาจึงเท่ากับ ${\คณิตศาสตร์ {O}}(n^{2})$ โดยที่ $n$ คือจำนวนโหนด

ไม่ชัดเจนว่าสถานการณ์นี้เป็นไปได้หรือไม่ ดังนั้นผลลัพธ์ข้างต้นจึงควรถือเป็นขอบเขตที่ไม่แน่นอน Blondel และคณะระบุในสิ่งพิมพ์ดั้งเดิมของพวกเขาว่าเวลาทำงานส่วนใหญ่ใช้ไปกับการวนซ้ำในช่วงแรกๆ ของอัลกอริทึมเนื่องจาก "จำนวนชุมชนลดลงอย่างมากหลังจากผ่านไปเพียงไม่กี่รอบ" ^{[ 1 ]} สามารถเข้าใจได้โดยพิจารณาสถานการณ์ที่ $moveNodes$ สามารถย้ายแต่ละโหนดเพื่อให้แต่ละชุมชนมีสองโหนด ในกรณีนี้ $aggregateGraph$ จะส่งคืนกราฟที่มีขนาดครึ่งหนึ่งของกราฟเดิม หากเป็นเช่นนี้ต่อไป วิธีการของ Louvain จะมีเวลาทำงานเป็น $n\log _{2}{n}$ อย่างไรก็ตาม ยังไม่ชัดเจนว่านี่จะเป็นกรณีที่แย่ที่สุด กรณีที่ดีที่สุด กรณีเฉลี่ย หรือไม่ใช่กรณีใดเลย นอกจากนี้ ยังไม่มีการรับประกันว่าขนาดของกราฟจะลดลงด้วยปัจจัยเดียวกันในแต่ละรอบการทำซ้ำ ดังนั้นจึงไม่มีฟังก์ชันลอการิทึมใดที่สามารถอธิบายความซับซ้อนของเวลาได้อย่างสมบูรณ์แบบ

การใช้งานก่อนหน้านี้

เครือข่ายสังคม Twitter (2.4 ล้านโหนด 38 ล้านลิงก์) โดย Josep Pujol, Vijay Erramilli และ Pablo Rodriguez: ^{[ 11 ]}ผู้เขียนสำรวจปัญหาการแบ่งเครือข่ายสังคมออนไลน์บนเครื่องต่างๆ
เครือข่ายโทรศัพท์มือถือ (4 ล้านโหนด 100 ล้านลิงก์) โดย Derek Greene, Donal Doyle และ Padraig Cunningham: ^{[ 12 ]}กลยุทธ์การติดตามชุมชนเพื่อระบุชุมชนแบบไดนามิกของเครือข่ายสังคมแบบไดนามิกที่แตกต่างกัน
การตรวจจับชนิดพันธุ์ในแบบจำลองพลวัตตามเครือข่าย^{[ 13 ]}

ข้อเสีย

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

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

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

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

การเปรียบเทียบกับวิธีการตรวจจับชุมชนที่ไม่ทับซ้อนกันแบบอื่น

เมื่อเปรียบเทียบวิธีการเพิ่มประสิทธิภาพโมดูลาร์ การวัดความสำคัญสองประการคือความเร็วและค่าโมดูลาร์ที่ได้ ความเร็วที่สูงขึ้นย่อมดีกว่า เพราะแสดงให้เห็นว่าวิธีการนั้นมีประสิทธิภาพมากกว่าวิธีอื่น และค่าโมดูลาร์ที่สูงขึ้นย่อมเป็นที่ต้องการ เพราะบ่งชี้ว่ามีชุมชนที่กำหนดไว้ได้ดีกว่า วิธีการที่นำมาเปรียบเทียบ ได้แก่ อัลกอริทึมของ Clauset, Newman และ Moore ^{[ 2 ]} Pons และ Latapy ^{[ 14 ]}และ Wakita และ Tsurumi ^{[ 15 ]}

การเปรียบเทียบการเพิ่มประสิทธิภาพโมดูลาร์^{[ 16 ]}
	คาราเต้	อาร์ซิฟ	อินเทอร์เน็ต	เว็บไซต์ nd.edu	โทรศัพท์	เว็บสหราชอาณาจักร-2005	เว็บ WebBase 2001
โหนด/ลิงก์	34/77	9k/24k	70k/351k	325k/1M	2.6ม./6.3ม.	39M/783M	118M/1B
คลอเซ็ต นิวแมน และมัวร์	.38/0s	.772/3.6 วินาที	.692/799s	.927/5034s	-/-	-/-	-/-
พอนส์และลาตาปี	.42/0s	.757/3.3 วินาที	.729/575s	.895/6666s	-/-	-/-	-/-
วาคิตะและสึรุมิ	.42/0s	.761/0.7 วินาที	.667/62s	.898/248s	.56/464s	-/-	-/-
วิธีการลูแวน	.42/0s	.813/0s	.781/1s	.935/3s	.769/134s	.979/738s	.984/152mn

-/- ในตารางหมายถึงวิธีการที่ใช้เวลาดำเนินการมากกว่า 24 ชั่วโมง ตารางนี้ (จาก^{[ 1 ]}^{[ 17 ]} ) แสดงให้เห็นว่าวิธีการ Louvain มีประสิทธิภาพเหนือกว่าวิธีการเพิ่มประสิทธิภาพโมดูลาร์ที่คล้ายคลึงกันหลายวิธี ทั้งในด้านโมดูลาร์และด้านเวลา

ดูเพิ่มเติม

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

วิธีการลูแวน

การเพิ่มประสิทธิภาพแบบโมดูลาร์

คำอธิบายอัลกอริธึม

ความเป็นโมดูล

อัลกอริทึมวิธีลูแวน

ระยะที่ 1

แต่ละโหนดในเครือข่ายจะถูกกำหนดให้เป็นส่วนหนึ่งของชุมชนของตนเอง

โหนดต่างๆ ถูกจัดกลุ่มเป็นชุมชน

ระยะที่ 2

ชุมชนต่างๆ ถูกลดเหลือเพียงโหนดเดียว

ความซับซ้อนเชิงเวลา

การใช้งานก่อนหน้านี้

ข้อเสีย

การเปรียบเทียบกับวิธีการตรวจจับชุมชนที่ไม่ทับซ้อนกันแบบอื่น

ดูเพิ่มเติม

ข้อมูลสำคัญจากบทความ