Skip to content
กลับไปยังผลการค้นหา

การตรวจจับชุมชน — การจัดกลุ่มกราฟในเครือข่าย

ผู้เสนอ
Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
ปี
2002–2019 (algorithm family)
ประเภท
Graph-partitioning / clustering algorithm family

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การตรวจจับชุมชน (Community detection) เป็นกลุ่มของอัลกอริทึมการแบ่งพาร์ติชันกราฟที่ค้นหากลุ่มย่อยที่มีการเชื่อมต่อกันอย่างหนาแน่น — ชุมชน — ภายในเครือข่าย การกำหนดรูปแบบอย่างเป็นทางการครั้งแรกผ่านการวัดค่ามอดูลาลิตี (modularity) โดย Girvan และ Newman (2002) สาขานี้ได้พัฒนาอย่างรวดเร็วด้วยวิธี Louvain (Blondel et al., 2008), การปรับปรุง Leiden (Traag et al., 2019) และแนวทาง Infomap ที่ใช้ทฤษฎีสารสนเทศ อัลกอริทึมทุกรูปแบบตอบคำถามเดียวกัน: โหนดใดบ้างที่รวมกลุ่มกันอย่างใกล้ชิดมากกว่าที่จะเชื่อมต่อกับส่วนที่เหลือของเครือข่าย?

แนวคิดเบื้องหลังวิธีการ

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

ประวัติศาสตร์

การศึกษาโครงสร้างชุมชนในเครือข่ายได้รับการวางรากฐานเชิงปริมาณโดย Girvan และ Newman (2002) ซึ่งได้นำเสนอแนวคิดเรื่องค่าระหว่างกลางของเส้นเชื่อม (edge betweenness) เป็นเครื่องมือสำหรับการแบ่งเครือข่ายแบบลำดับชั้น จากนั้น Newman และ Girvan (2004) ได้กำหนดรูปแบบของมาตรวัดมอดูลาลิตี Q ซึ่งกลายเป็นเกณฑ์คุณภาพมาตรฐาน Blondel et al. (2008) ได้เผยแพร่วิธี Louvain — การเพิ่มค่าให้เหมาะสมอย่างละโมบแบบสองขั้นตอนที่ทำให้การตรวจจับชุมชนคุณภาพสูงใช้งานได้จริงกับเครือข่ายที่มีโหนดหลายล้านโหนด Traag, Waltman และ van Eck (2019) ได้ระบุข้อบกพร่องเชิงโครงสร้างใน Louvain — คือสามารถสร้างชุมชนที่ไม่เชื่อมต่อภายในได้ — และได้พัฒนาอัลกอริทึม Leiden เพื่อแก้ไขปัญหานี้ โดยรับประกันพาร์ติชันที่เชื่อมต่อกันดี ในขณะเดียวกัน Rosvall และ Bergstrom (2008) ได้พัฒนา Infomap ซึ่งปรับกรอบการตรวจจับชุมชนให้เป็นปัญหาการบีบอัด: ค้นหาพาร์ติชันที่ลดความยาวในการอธิบายการสุ่มเดินบนเครือข่ายให้เหลือน้อยที่สุด

ควรใช้เมื่อใด

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

ข้อจำกัดและข้อควรพิจารณา

  • การเพิ่มค่ามอดูลาลิตีให้สูงสุดมีความอ่อนไหวต่อค่าที่เหมาะสมที่สุดเฉพาะที่ (local optima); ผลลัพธ์อาจแตกต่างกันไปในแต่ละการรัน และควรรายงานเป็นผลลัพธ์ที่ดีที่สุดจากการรันหลายครั้ง
  • ข้อจำกัดด้านความละเอียด (resolution limit) หมายความว่าชุมชนขนาดเล็กมากในเครือข่ายขนาดใหญ่อาจถูกรวมเข้าด้วยกัน ทำให้โครงสร้างที่ละเอียดอ่อนถูกบดบัง
  • ผลลัพธ์มีความอ่อนไหวต่อวิธีการกำหนดน้ำหนักเส้นเชื่อม; รูปแบบการให้น้ำหนักที่แตกต่างกันสามารถให้พาร์ติชันที่แตกต่างกันอย่างมีความหมาย
  • Girvan-Newman มีความซับซ้อน O(m²n) และไม่สามารถใช้งานได้จริงกับเครือข่ายขนาดใหญ่; ควรเลือก Louvain หรือ Leiden สำหรับเครือข่ายขนาดใหญ่

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ไม่จำเป็นต้องระบุจำนวนชุมชนล่วงหน้า — ขนาดของพาร์ติชันถูกกำหนดโดยข้อมูล
  • ปรับขนาดได้กับเครือข่ายขนาดใหญ่: Louvain และ Leiden ทำงานในเวลาเกือบเป็นเชิงเส้น ทำให้ใช้งานได้จริงกับเครือข่ายที่มีโหนดหลายล้านโหนด
  • Leiden รับประกันชุมชนที่มีการเชื่อมต่อกันดีและเหนียวแน่นภายใน แก้ไขข้อบกพร่องของชุมชนที่ไม่เชื่อมต่อกันของ Louvain
  • ใช้ได้กับทั้งเครือข่ายที่ไม่มีน้ำหนักและมีน้ำหนักโดยไม่มีข้อสมมติฐานการแจกแจงบนข้อมูล

การประยุกต์ใช้

  • การระบุกลุ่มงานวิจัยในเครือข่ายการอ้างอิงและการเขียนร่วมเพื่อทำแผนที่สาขาวิทยาศาสตร์
  • การตรวจจับโมดูลการทำงานในเครือข่ายปฏิสัมพันธ์ระหว่างโปรตีนในชีววิทยา
  • การค้นหาชุมชนผู้ใช้ในเครือข่ายสังคมและเครือข่ายการสื่อสารเพื่อวิเคราะห์พฤติกรรม
  • การแบ่งส่วนเครือข่ายลูกค้าในธุรกิจและการตลาดเพื่อเปิดเผยกลุ่มลูกค้าที่เหนียวแน่น
  • การค้นหาบล็อกโครงสร้างในเครือข่ายโครงสร้างพื้นฐาน การขนส่ง หรือห่วงโซ่อุปทาน

วิธีการทำงาน

วิธีการทำงาน

1

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

2

อัลกอริทึมแต่ละตัวเริ่มต้นด้วยการกำหนดโหนดให้กับชุมชนเบื้องต้น ใน Louvain และ Leiden โหนดแต่ละโหนดเริ่มต้นเป็นชุมชนเดี่ยวของตัวเอง Girvan-Newman เริ่มต้นด้วยเครือข่ายทั้งหมดและค่อยๆ ลบเส้นเชื่อมที่มีค่าระหว่างกลางศูนย์กลาง (betweenness centrality) สูงสุดออกไป เผยโครงสร้างชุมชนอย่างต่อเนื่อง Infomap เริ่มต้นจากคำอธิบายการสุ่มเดินของเครือข่ายและเข้ารหัสโดยใช้แผนที่สองระดับเพื่อลดความยาวของรหัสให้เหลือน้อยที่สุด

3

ขั้นตอนหลักคือการค้นหาพาร์ติชันที่เพิ่มค่ามอดูลาลิตี Q ให้สูงสุด (Louvain, Leiden) หรือลดความยาวรหัสของสมการแผนที่ (Infomap) ให้เหลือน้อยที่สุด Louvain ย้ายโหนดเดี่ยวระหว่างชุมชนอย่างละโมบเพื่อปรับปรุง Q จากนั้นรวมชุมชนเข้าเป็นโหนดซูเปอร์และทำซ้ำ — กระบวนการสองขั้นตอนที่ปรับขนาดได้ดี แต่สามารถสร้างชุมชนที่ไม่เชื่อมต่อกันได้ Leiden ปรับปรุง Louvain โดยรับประกันว่าทุกชุมชนมีการเชื่อมต่อภายใน โดยใช้ขั้นตอนการย้ายและการปรับปรุงเฉพาะที่ก่อนการรวมกลุ่ม Girvan-Newman ลบเส้นเชื่อมออกไปเรื่อยๆ และบันทึกเดนโดรแกรมของการแบ่งแยก; พาร์ติชันที่เพิ่มค่า Q ให้สูงสุด ณ จุดตัดใดๆ ของเดนโดรแกรมจะถูกเลือก จำนวนชุมชนจะปรากฏขึ้นจากอัลกอริทึมเอง ไม่จำเป็นต้องระบุล่วงหน้า

4

คุณภาพของพาร์ติชันสุดท้ายจะสรุปด้วยคะแนนมอดูลาลิตี Q ซึ่งมีค่าตั้งแต่ −0.5 ถึง 1 ค่าที่สูงกว่าประมาณ 0.3–0.5 โดยทั่วไปถือว่าบ่งชี้ถึงโครงสร้างชุมชนที่มีความหมาย เนื่องจาก การเพิ่มค่ามอดูลาลิตีให้สูงสุดอาจติดอยู่ในค่าที่เหมาะสมที่สุดเฉพาะที่ (local optima) การรันอัลกอริทึมหลายครั้งและเลือกผลลัพธ์ที่ดีที่สุดเป็นแนวปฏิบัติมาตรฐาน พาร์ติชันจะถูกตรวจสอบด้วยสายตาและตรวจสอบข้ามกับคุณลักษณะโหนดที่มีอยู่หรือป้ายกำกับจริง (ground-truth labels) เพื่อยืนยันว่ามีความหมายในทางเนื้อหา

ข้อผิดพลาดที่พบบ่อย

  • การรันอัลกอริทึมเพียงครั้งเดียวและถือว่าผลลัพธ์เดียวเป็นจริง — ควรทำการรันหลายครั้งเสมอและรายงานค่ามอดูลาลิตีที่ดีที่สุด หรือใช้วิธีการแบบกลุ่ม (ensemble methods)
  • การละเลยข้อจำกัดด้านความละเอียด: ในเครือข่ายเบาบางขนาดใหญ่ ชุมชนขนาดเล็กแต่มีอยู่จริงสามารถถูกรวมเข้ากับชุมชนที่ใหญ่กว่าได้โดยไม่แจ้งให้ทราบ
  • การใช้อัลกอริทึมที่ใช้มอดูลาลิตีกับเครือข่ายที่มีโหนดน้อยกว่า 20 โหนด — โครงสร้างชุมชนไม่สามารถระบุได้อย่างน่าเชื่อถือในระดับนั้น
  • การสับสนระหว่างคะแนนมอดูลาลิตีสูงกับการยืนยันโครงสร้างชุมชนในโลกแห่งความเป็นจริง; มอดูลาลิตีเป็นตัววัดคุณภาพของพาร์ติชัน ไม่ใช่การทดสอบเชิงอนุมานว่าชุมชนมีความสำคัญทางสถิติหรือไม่

คำถามที่พบบ่อย

ควรเลือกอัลกอริทึมใด — Louvain, Leiden, Girvan-Newman หรือ Infomap?

Louvain เป็นเกณฑ์มาตรฐานที่รวดเร็วและใช้กันอย่างแพร่หลายสำหรับเครือข่ายขนาดใหญ่ Leiden เป็นตัวเลือกที่ต้องการเมื่อความถูกต้องมีความสำคัญ เนื่องจากรับประกันชุมชนที่เชื่อมต่อภายในและโดยทั่วไปให้ค่ามอดูลาลิตีที่สูงกว่า Girvan-Newman สร้างเดนโดรแกรมที่มีประโยชน์สำหรับการสำรวจแบบลำดับชั้น แต่ช้าเกินไปสำหรับเครือข่ายขนาดใหญ่ Infomap เหมาะสำหรับเครือข่ายที่มีทิศทางหรืออิงตามการไหล ซึ่งเส้นทางที่นักสุ่มเดินใช้มีความหมาย

ฉันจำเป็นต้องระบุจำนวนชุมชนล่วงหน้าหรือไม่?

ไม่ Louvain, Leiden และ Infomap จะกำหนดจำนวนชุมชนโดยอัตโนมัติจากโครงสร้างเครือข่าย Girvan-Newman สร้างเดนโดรแกรมเต็มรูปแบบที่สามารถอ่านจำนวนชุมชนใดๆ ได้; พาร์ติชันที่เพิ่มค่า Q ให้สูงสุดมักจะถูกเลือก

ฉันจะทราบได้อย่างไรว่าชุมชนที่พบมีความหมายหรือไม่?

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

จะเกิดอะไรขึ้นหากผลลัพธ์แตกต่างกันไปในแต่ละการรัน?

การเพิ่มค่ามอดูลาลิตีให้สูงสุดเป็นวิธีการเชิงฮิวริสติก และการรันที่แตกต่างกันอาจให้พาร์ติชันที่แตกต่างกันเล็กน้อย โดยเฉพาะใน Louvain ให้รันอัลกอริทึมหลายครั้ง (อย่างน้อย 10–100 ครั้งสำหรับเครือข่ายขนาดใหญ่) และรายงานพาร์ติชันที่มีค่า Q สูงสุด Leiden มีความเสถียรกว่า Louvain เนื่องจากขั้นตอนการปรับปรุงมีความละเอียดถี่ถ้วนกว่า แต่การรันซ้ำยังคงเป็นแนวปฏิบัติที่ดี

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว