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

แบบจำลองบล็อกสุ่ม — การตรวจจับชุมชนเชิงความน่าจะเป็นในเครือข่าย

ปี
1983
ประเภท
Probabilistic generative graph model

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

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

ใช้ทำอะไร?

แบบจำลองบล็อกสุ่ม (SBM) ซึ่งนำเสนอโดย Holland, Laskey และ Leinhardt (1983) เป็นแบบจำลองการสร้างเชิงความน่าจะเป็นสำหรับกราฟที่กำหนดโหนดไปยังบล็อกแฝงและประมาณค่าความน่าจะเป็นของการเชื่อมต่อระหว่างบล็อกเชิงพารามิเตอร์ เป็นแนวทางพื้นฐานสำหรับการตรวจจับชุมชน การระบุแกนกลาง-ส่วนปลาย และการค้นพบโครงสร้างตามลำดับชั้นในการวิเคราะห์เครือข่าย

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

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

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

แบบจำลองบล็อกสุ่มถูกนำเสนอโดย Holland, Laskey และ Leinhardt ในบทความ Social Networks ปี 1983 ของพวกเขาในฐานะการขยายเชิงความน่าจะเป็นของงานบล็อกโมเดลลิ่งก่อนหน้านี้ในการวิเคราะห์เครือข่ายสังคม เป็นเวลาสองทศวรรษที่ยังคงเป็นเครื่องมือทางทฤษฎีเป็นหลัก มันได้รับความนิยมในทางปฏิบัติด้วยการพัฒนาอัลกอริทึมการอนุมานที่ปรับขนาดได้ — variational EM และ MCMC — ในช่วงปี 2010 แบบจำลองบล็อกสุ่มที่ปรับแก้ดีกรีถูกนำเสนอโดย Karrer และ Newman (2011) เพื่อแก้ไขปัญหาความไม่สม่ำเสมอของดีกรี การทบทวนของ Lee และ Wilkinson ในปี 2019 ใน Applied Network Science ได้รวบรวมตระกูลส่วนขยาย ครอบคลุมแบบจำลองพาร์ติชันที่ปลูกฝัง SBM สมาชิกภาพผสม และรูปแบบตามลำดับชั้น ปัจจุบัน SBM และลูกหลานของมันเป็นกรอบการทำงานเชิงความน่าจะเป็นอ้างอิงสำหรับการตรวจจับชุมชนและการจัดกลุ่มกราฟ

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

ใช้แบบจำลองบล็อกสุ่มเมื่อคุณมีเครือข่ายที่มีโหนดอย่างน้อย 50 โหนด และคุณต้องการค้นพบโครงสร้างกลุ่มแฝงโดยไม่ต้องสมมติว่ากลุ่มต้องเป็นกลุ่มก้อนที่หนาแน่น เหมาะสำหรับกราฟที่มีทิศทางหรือไม่ระบุทิศทาง ถ่วงน้ำหนักหรือไม่ถ่วงน้ำหนัก และเหมาะสำหรับทั้งงานสำรวจและงานจำแนกประเภท รูปแบบ DCSBM เป็นที่ต้องการเมื่อดีกรีของโหนดแตกต่างกันอย่างมาก หากกราฟมีโหนดน้อยกว่า 20 โหนด โครงสร้างชุมชนจะไม่สามารถประมาณค่าได้อย่างน่าเชื่อถือ และควรใช้เมตริกคำอธิบายที่ง่ายกว่าแทน ข้อสมมติฐาน: สมาชิกภาพบล็อกเป็นแฝงและไม่ได้สังเกต; เมทริกซ์การเชื่อมต่อบล็อกถูกสมมติว่ามีความสม่ำเสมอภายในคู่บล็อกแต่ละคู่; และ K ต้องถูกเลือกโดย BIC หรือปัจจัยเบย์เซียน แทนที่จะกำหนดโดยพลการ

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

  • ต้องการโหนดอย่างน้อยประมาณ 50 โหนดสำหรับการประมาณค่าบล็อกที่น่าเชื่อถือ กราฟขนาดเล็กมากให้ผลลัพธ์ที่ไม่เสถียร — ควรใช้สถิติเครือข่ายคำอธิบายหรือการตรวจจับชุมชนที่ง่ายกว่าแทน
  • การอนุมานมีค่าใช้จ่ายในการคำนวณสูงสำหรับกราฟขนาดใหญ่: จำเป็นต้องใช้ variational EM หรือ MCMC และไม่รับประกันการลู่เข้า
  • ข้อสมมติฐานความสม่ำเสมอของ SBM พื้นฐานภายในคู่บล็อกจะพังเมื่ออัตราการเชื่อมต่อภายในบล็อกแตกต่างกัน — DCSBM ช่วยลดแต่ไม่กำจัดปัญหานี้
  • การเลือกบล็อกผ่าน BIC หรือปัจจัยเบย์เซียนยังคงสามารถแบ่งน้อยเกินไปหรือมากเกินไปได้หากกราฟมีชุมชนที่แยกจากกันอย่างอ่อน

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

จุดแข็ง

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

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

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

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

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

1

นักวิเคราะห์ระบุช่วงที่คาดเดาได้สำหรับจำนวนบล็อก K และเลือกรูปแบบ: SBM พื้นฐานสมมติว่าการกระจายตัวของดีกรีภายในบล็อกมีความสม่ำเสมอ ในขณะที่ SBM ที่ปรับแก้ดีกรี (DCSBM) จะเพิ่มพารามิเตอร์ดีกรีระดับโหนดเพื่อจัดการกับฮับและลำดับดีกรีที่ไม่สม่ำเสมอ การเลือกลักษณะเฉพาะได้รับแจ้งจากการกระจายตัวของดีกรีของกราฟที่สังเกตได้

2

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

3

จำนวนบล็อก K ไม่ทราบล่วงหน้าและต้องเลือกจากข้อมูล เกณฑ์การเลือกที่ต้องการคือเกณฑ์ข้อมูลเบย์เซียน (BIC) และปัจจัยเบย์เซียน ซึ่งทั้งสองอย่างนี้จะลงโทษความซับซ้อนของแบบจำลองและเลือก K ที่สมดุลระหว่างความเหมาะสมกับความรัดกุมได้ดีที่สุด หลักการความยาวคำอธิบายขั้นต่ำ (MDL) เป็นพื้นฐานของการใช้งาน graph-tool

4

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

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

  • การกำหนด K โดยพลการแทนที่จะเลือกโดย BIC หรือปัจจัยเบย์เซียน ทำให้เกิดการแบ่งที่ไม่น่าเชื่อถือ — ควรใช้เกณฑ์การเลือกแบบจำลองที่มีหลักการเสมอ
  • การใช้ SBM พื้นฐานกับกราฟที่มีลำดับดีกรีที่ไม่สม่ำเสมอ (ฮับ การกระจายตัวของดีกรีแบบพาวเวอร์ลอว์) จะทำให้การประมาณค่าจำนวนบล็อกสูงเกินไป — ควรใช้ DCSBM แทน
  • การปฏิบัติต่อสมาชิกภาพบล็อกว่าแน่นอนเมื่อความน่าจะเป็นภายหลังกระจายไปทั่วจะกล่าวเกินจริงถึงความมั่นใจ — ควรรายงานความไม่แน่นอนเมื่อมีอยู่
  • การสับสนผลลัพธ์ SBM กับชุมชนที่เป็นความจริง: แบบจำลองค้นพบโครงสร้างแฝงที่สมเหตุสมผลทางสถิติ ไม่จำเป็นต้องเป็นกลุ่มที่มีความหมายทางสังคม ตรวจสอบกับความรู้เฉพาะทาง
  • การรัน SBM บนโหนดน้อยกว่า 20 โหนดให้ผลลัพธ์ที่เสื่อมโทรม — กลับไปใช้เมตริกเครือข่ายคำอธิบายหรือการตรวจจับชุมชนอย่างง่ายสำหรับกราฟขนาดเล็ก

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

แบบจำลองบล็อกสุ่มแตกต่างจากการตรวจจับชุมชนที่ใช้โมดูลาริตี้อย่างไร

การหาค่าสูงสุดของโมดูลาริตี้ (เช่น Louvain, Leiden) ปรับวัตถุประสงค์เชิงฮิวริสติกให้เหมาะสม ซึ่งโดยปริยายสมมติว่าชุมชนที่สอดคล้องกันและมีขนาดใกล้เคียงกัน และมีขีดจำกัดความละเอียดที่ทราบซึ่งป้องกันการตรวจจับชุมชนขนาดเล็ก SBM เป็นแบบจำลองการสร้างเชิงความน่าจะเป็นที่มีข้อสมมติฐานที่ชัดเจน จำนวนบล็อกถูกเลือกโดยการเลือกแบบจำลอง (BIC หรือปัจจัยเบย์เซียน) แทนที่จะเป็นการหาค่าสูงสุดเชิงฮิวริสติก และสามารถตรวจจับโครงสร้างที่ไม่สอดคล้องกันและแกนกลาง-ส่วนปลายที่วิธีการที่ใช้โมดูลาริตี้พลาดไป

เมื่อใดที่ฉันควรใช้ DCSBM แทน SBM พื้นฐาน

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

ฉันจะเลือกจำนวนบล็อก K ได้อย่างไร

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

ขนาดเครือข่ายขั้นต่ำที่ SBM จะเชื่อถือได้คือเท่าใด

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

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

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

  1. Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.

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