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

การวิเคราะห์มอดูลาริตี

ผู้เสนอ
Newman, M. E. J. & Girvan, M.
ปี
2004
ประเภท
Community detection / graph partitioning
กลุ่มวิธี
Network science

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

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

ใช้ทำอะไร?

การวิเคราะห์มอดูลาริตีเป็นระเบียบวิธีทางวิทยาศาสตร์เครือข่าย ซึ่ง Newman และ Girvan ได้วางกรอบไว้อย่างเป็นทางการในปี 2004 โดยใช้ตรวจจับโครงสร้างชุมชนในกราฟด้วยการวัดว่าขอบ (edge) มีความหนาแน่นภายในกลุ่มมากกว่าที่คาดการณ์โดยบังเอิญหรือไม่ ดัชนีคุณภาพสเกลาร์ Q ของระเบียบวิธีนี้จะนำทางอัลกอริทึมที่แบ่งโหนดออกเป็นกลุ่มที่เหนียวแน่น ทำให้เป็นกรอบการทำงานที่ได้รับการยอมรับอย่างกว้างขวางที่สุดสำหรับการตรวจจับชุมชนในเครือข่ายทางสังคม ชีวภาพ และเทคโนโลยี

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

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

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

ฟังก์ชันมอดูลาริตี Q ถูกนำเสนอโดย Newman และ Girvan ในปี 2004 ซึ่งเป็นส่วนหนึ่งของชุดเทคนิคการตรวจจับชุมชน บทความ PNAS ของ Newman ในปี 2006 ได้วางกรอบแนวทางเชิงสเปกตรัมสำหรับการปรับให้เหมาะสมของมอดูลาริตีอย่างเป็นทางการ และระเบียบวิธี Louvain (Blondel et al., 2008) ทำให้การปรับให้เหมาะสมขนาดใหญ่เป็นไปได้ในทางปฏิบัติ ซึ่งทำให้การวิเคราะห์มอดูลาริตีเป็นที่นิยมในสาขาสังคมวิทยา ชีววิทยา และวิทยาการคอมพิวเตอร์ ปัญหาข้อจำกัดด้านความละเอียดถูกระบุโดย Fortunato และ Barthélemy ในปี 2007 ซึ่งกระตุ้นให้เกิดอัลกอริทึมที่ได้รับการปรับปรุง เช่น Leiden (Traag et al., 2019) ซึ่งยังแก้ไขปัญหาชุมชนที่เชื่อมต่อกันไม่ดีอีกด้วย

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

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

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

  • ข้อจำกัดด้านความละเอียด: การปรับให้เหมาะสมของมอดูลาริตีมักจะล้มเหลวในการตรวจจับชุมชนที่มีขนาดเล็กกว่ามาตราส่วนที่กำหนดโดยขนาดเครือข่าย โดยจะรวมโมดูลขนาดเล็กที่แตกต่างกันอย่างแท้จริงเข้าด้วยกัน
  • การปรับให้เหมาะสมที่แม่นยำแบบ NP-hard หมายความว่าในทางปฏิบัติจะใช้เพียงการประมาณค่าเท่านั้น และการรันอัลกอริทึมแบบสุ่มที่แตกต่างกันอาจให้พาร์ติชันที่แตกต่างกัน
  • แบบจำลองว่างเปล่าสมมติว่าเป็นแบบจำลอง configuration model (ลำดับระดับขั้นคล้าย Erdos-Renyi) ซึ่งอาจไม่เหมาะสมสำหรับเครือข่ายที่มีการกระจายระดับขั้นแบบ heavy-tailed หรือโครงสร้างแบบลำดับชั้น
  • ขอบเขตชุมชนที่แข็งกระด้างไม่สามารถแสดงการเป็นสมาชิกที่ทับซ้อนกันในโลกแห่งความเป็นจริงได้

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

จุดแข็ง

  • ไม่จำเป็นต้องระบุจำนวนชุมชนล่วงหน้า; การแบ่งพาร์ติชันจะเกิดขึ้นจากข้อมูล
  • ให้ค่า Q สเกลาร์เดียวที่ช่วยให้เปรียบเทียบพาร์ติชันหรือเครือข่ายต่างๆ ได้อย่างตรงไปตรงมา
  • อัลกอริทึมประมาณค่าอย่างรวดเร็ว (Louvain, Leiden) สามารถปรับขนาดได้ถึงหลายล้านโหนด
  • สามารถใช้ได้กับเครือข่ายที่ไม่มีทิศทาง มีทิศทาง และมีน้ำหนัก โดยมีการขยายที่เหมาะสม
  • มีการนำไปใช้อย่างแพร่หลายในไลบรารีมาตรฐาน (NetworkX, igraph, Gephi) ซึ่งช่วยลดอุปสรรคในการใช้งาน

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

  • การตรวจจับกลุ่มทางสังคม ห้องสะท้อนเสียง หรือกลุ่มความร่วมมือในเครือข่ายสังคมออนไลน์และออฟไลน์
  • การระบุโมดูลการทำงานในเครือข่ายชีวภาพ เช่น เครือข่ายปฏิสัมพันธ์ของโปรตีนและกราฟควบคุมยีน
  • การเปิดเผยกลุ่มหัวข้อหรือสาขาวิชาในเครือข่ายการอ้างอิงและการเขียนร่วม
  • การแบ่งส่วนเครือข่ายลูกค้าหรือผลิตภัณฑ์ในระบบการตลาดและระบบแนะนำ
  • การแบ่งพาร์ติชันเครือข่ายโครงสร้างพื้นฐาน (โครงข่ายไฟฟ้า การขนส่ง) สำหรับการวิเคราะห์ความยืดหยุ่น
  • การค้นพบชุมชนหัวข้อในกราฟไฮเปอร์ลิงก์หรือ co-occurrence ในภาษาศาสตร์เชิงคำนวณ

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

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

1

เครือข่ายจะถูกแสดงเป็นเมทริกซ์ประชิด A (หรือรายการขอบที่เทียบเท่ากัน) โดยที่รายการ A_ij เท่ากับ 1 หากโหนด i และ j เชื่อมต่อกัน และ 0 หากไม่เชื่อมต่อ ระดับขั้นของโหนด (k_i, k_j) และจำนวนขอบทั้งหมด m จะถูกคำนวณเป็นอินพุตสำหรับสูตรมอดูลาริตี

2

คะแนนมอดูลาริตี Q ถูกกำหนดให้เป็นสัดส่วนของขอบที่อยู่ภายในชุมชน ลบด้วยสัดส่วนที่คาดการณ์ภายใต้แบบจำลองว่างเปล่าแบบ configuration-model (การสุ่มจัดเรียงใหม่ที่รักษาระดับขั้น) ค่า Q มีช่วงตั้งแต่ประมาณ -0.5 ถึง 1; ค่าที่สูงกว่าประมาณ 0.3 บ่งชี้ถึงโครงสร้างชุมชนที่มีความหมาย

สูตร
Q = \frac{1}{2m}\sum_{ij}\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)
3

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

4

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

5

พาร์ติชันที่ได้จะถูกประเมินโดยค่า Q สุดท้าย การตรวจสอบความเสถียรในการรันอัลกอริทึมหลายครั้ง และในกรณีที่มี ground truth จะใช้เมตริกภายนอก เช่น normalized mutual information ค่า Q ต่ำหรือไม่เสถียรในการรันหลายครั้งบ่งชี้ถึงโครงสร้างชุมชนที่อ่อนแอหรือไม่ปรากฏ

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

  • การยอมรับการรันเพียงครั้งเดียวของตัวปรับให้เหมาะสมแบบสุ่มโดยไม่ตรวจสอบความเสถียรในการรันหลายครั้งหรือ random seeds
  • การละเลยข้อจำกัดด้านความละเอียดและสรุปว่าชุมชนขนาดใหญ่ที่รวมกันเป็นเนื้อเดียวกันอย่างแท้จริง
  • การใช้มอดูลาริตีแบบไบนารีกับเครือข่ายที่มีน้ำหนักโดยไม่ปรับแบบจำลองว่างเปล่าเพื่อรวมน้ำหนักขอบ
  • การถือว่า Q ที่สูงกว่า 0.3 เป็นเกณฑ์สากลสำหรับโครงสร้าง 'ที่ดี' โดยไม่พิจารณาประเภทและขนาดของเครือข่าย
  • การรวมคุณภาพการปรับให้เหมาะสม (Q สูง) เข้ากับความถูกต้องของการตีความ — ชุมชนยังคงต้องได้รับการตรวจสอบอย่างมีนัยสำคัญ

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

ค่า Q ที่ดีคือเท่าใด?

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

ฉันควรใช้อัลกอริทึมใดเพื่อเพิ่มค่า Q ให้สูงสุด?

อัลกอริทึม Leiden (Traag et al., 2019) เป็นค่าเริ่มต้นที่แนะนำในปัจจุบัน: เร็วกว่าระเบียบวิธี Louvain ดั้งเดิม และแก้ไขแนวโน้มที่จะสร้างชุมชนที่เชื่อมต่อกันไม่ดี สำหรับกราฟขนาดใหญ่มาก Louvain ยังคงเป็นทางเลือกที่ใช้งานได้จริง วิธีการเชิงสเปกตรัมเป็นที่ต้องการเมื่อคุณต้องการผลลัพธ์ที่ทำซ้ำได้และกำหนดได้สำหรับเครือข่ายขนาดเล็ก

การวิเคราะห์มอดูลาริตีสามารถตรวจจับชุมชนที่ทับซ้อนกันได้หรือไม่?

การปรับให้เหมาะสมของมอดูลาริตีมาตรฐานจะกำหนดแต่ละโหนดให้กับชุมชนเพียงชุมชนเดียวและไม่สามารถตรวจจับการทับซ้อนได้ หากคุณคาดว่าโหนดจะอยู่ในหลายกลุ่มพร้อมกัน ให้ใช้วิธีการชุมชนที่ทับซ้อนกัน เช่น วิธี clique-percolation หรือแนวทาง non-negative matrix factorization แทน

ข้อจำกัดด้านความละเอียดส่งผลต่อการวิเคราะห์ของฉันอย่างไร?

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

ฉันควรใช้การวิเคราะห์มอดูลาริตีกับเครือข่ายที่มีทิศทางหรือไม่?

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

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

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

  1. Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว