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

แบบจำลองการแพร่กระจายในเครือข่าย — SIR, SIS และ Independent Cascade

ผู้เสนอ
Kermack & McKendrick (SIR/SIS, 1927); Kempe, Kleinberg & Tardos (Independent Cascade, 2003)
ปี
1927 (epidemiological compartmental); 2003 (social influence cascade)
ประเภท
Stochastic / deterministic simulation on graphs

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

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

ใช้ทำอะไร?

แบบจำลองการแพร่กระจายในเครือข่ายเป็นกลุ่มของกรอบการทำงานแบบแบ่งส่วนและแบบความน่าจะเป็นที่จำลองว่าข้อมูล โรคระบาด หรือนวัตกรรมแพร่กระจายไปทั่วระบบที่เชื่อมโยงกันอย่างไร แบบจำลอง SIR และ SIS มีรากฐานมาจากการระบาดวิทยาทางคณิตศาสตร์ของ Kermack และ McKendrick (1927) โดยแบ่งโหนดออกเป็นสถานะต่าง ๆ และติดตามการเปลี่ยนแปลงที่ขับเคลื่อนโดยอัตราการสัมผัสและความน่าจะเป็นในการฟื้นตัว แบบจำลอง Independent Cascade และ Linear Threshold ซึ่ง Kempe, Kleinberg และ Tardos (2003) ได้ทำให้เป็นทางการ ได้ขยายตรรกะนี้ไปสู่การมีอิทธิพลทางสังคม โดยจำลองว่าการกระตุ้นแพร่กระจายผ่านเครือข่ายทีละเพื่อนบ้านอย่างไร

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

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

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

รากฐานทางคณิตศาสตร์ของการแพร่กระจายในเครือข่ายถูกวางโดย Kermack และ McKendrick ในบทความสำคัญของพวกเขาในปี 1927 ซึ่งนำเสนอโครงสร้าง SIR เป็นระบบสมการเชิงอนุพันธ์สามัญที่อธิบายการเปลี่ยนแปลงของการระบาด ตัวแปร SIS ได้ขยายแนวคิดนี้ไปสู่โรคประจำถิ่นที่ภูมิคุ้มกันเป็นเพียงชั่วคราว แนวทางค่าเฉลี่ยสนามเหล่านี้ถือว่าประชากรมีการผสมแบบเอกพันธ์ การเปลี่ยนไปใช้โครงสร้างเครือข่ายที่ชัดเจน — ซึ่งอนุญาตให้โหนดต่าง ๆ มีจำนวนการติดต่อที่แตกต่างกัน — กลายเป็นหัวใจสำคัญของการระบาดวิทยาเชิงคำนวณในช่วงปลายทศวรรษ 1990 และต้นทศวรรษ 2000 เมื่อแบบจำลองเครือข่ายแบบไร้มาตราส่วน (Barabási และ Albert, 1999) เปิดเผยว่าศูนย์กลางมีบทบาทที่ไม่สมส่วนในการติดต่อ Kempe, Kleinberg และ Tardos (2003) ได้ทำให้ปัญหาการเพิ่มประสิทธิภาพอิทธิพลเป็นทางการภายใต้แบบจำลอง Independent Cascade และ Linear Threshold โดยเชื่อมโยงทฤษฎีการแพร่กระจายเข้ากับปัญหาอัลกอริทึมในการคำนวณทางสังคมและการตลาด ตั้งแต่นั้นมา สาขาวิชานี้ได้ขยายไปสู่เครือข่ายหลายชั้น ลำดับการติดต่อเชิงเวลา และการประมาณค่าพารามิเตอร์ที่ขับเคลื่อนด้วยข้อมูลโดยใช้ชุดข้อมูลการระบาดจริงหรือโซเชียลมีเดีย

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

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

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

  • ต้องมีโครงสร้างเครือข่ายที่ทราบหรือประมาณค่าได้ การสร้างกราฟที่ถูกต้องจากข้อมูลสำรวจหรือข้อมูลบันทึกนำมาซึ่งความไม่แน่นอนในการวัดผลของตัวเอง
  • สมมติฐานการผสมแบบเอกพันธ์ของแบบจำลองค่าเฉลี่ยสนามอาจไม่เป็นจริงในเครือข่ายจริงที่มีความหลากหลาย การจำลองเครือข่ายเต็มรูปแบบมีความแม่นยำกว่าแต่ใช้การคำนวณที่หนักกว่า
  • การประมาณค่าพารามิเตอร์ (τ, γ) จากข้อมูลการสังเกตการณ์ไม่ใช่เรื่องง่าย และมักต้องมีการปรับเทียบเพิ่มเติมหรือขั้นตอนการอนุมานแบบเบย์เซียน
  • ผลลัพธ์แบบสุ่มจะแตกต่างกันไปในการรันแต่ละครั้ง จำเป็นต้องมีการทำซ้ำแบบ Monte Carlo จำนวนมากพอ ซึ่งจะเพิ่มเวลาการคำนวณสำหรับเครือข่ายขนาดใหญ่

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

จุดแข็ง

  • พิจารณาโครงสร้างเครือข่ายอย่างชัดเจน โดยจับภาพข้อเท็จจริงที่ว่าศูนย์กลางที่มีการเชื่อมต่อสูงเร่งการแพร่กระจายเกินกว่าที่แบบจำลองรวมคาดการณ์ไว้มาก
  • กลุ่มแบบจำลองที่ยืดหยุ่น — SIR, SIS, Independent Cascade, Linear Threshold — ครอบคลุมทั้งกระบวนการติดต่อทางชีวภาพและอิทธิพลทางสังคม
  • การจำลองแบบ Monte Carlo สร้างการกระจายผลลัพธ์ที่สมบูรณ์ ไม่ใช่แค่การประมาณค่าจุดเดียว ทำให้สามารถวัดปริมาณความไม่แน่นอนได้อย่างมีหลักการ
  • กรอบการเพิ่มประสิทธิภาพอิทธิพล (Kempe et al., 2003) เชื่อมโยงโดยตรงกับกลยุทธ์การเริ่มต้นใช้งานจริง — การระบุโหนดที่การกระตุ้นจะแพร่สัญญาณได้กว้างที่สุด

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

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

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

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

1

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

2

นักวิเคราะห์เลือกกลุ่มแบบจำลองการแพร่กระจายที่ตรงกับคำถามวิจัย แบบจำลอง SIR (Susceptible–Infected–Recovered) เหมาะสำหรับกระบวนการที่ย้อนกลับไม่ได้ เช่น การระบาดของโรค หรือการนำเทคโนโลยีใหม่มาใช้ เพราะเมื่อโหนดฟื้นตัวแล้วจะไม่สามารถติดเชื้อซ้ำได้ แบบจำลอง SIS (Susceptible–Infected–Susceptible) เหมาะสำหรับปรากฏการณ์ที่เป็นโรคประจำถิ่นหรือเกิดขึ้นซ้ำ ๆ — เช่น การสัมผัสข่าวลือซ้ำ — ซึ่งโหนดสามารถหมุนเวียนกลับไปสู่สถานะอ่อนแอได้ แบบจำลอง Independent Cascade และ Linear Threshold เหมาะสำหรับปัญหาอิทธิพลทางสังคมที่แต่ละโหนดทำงานได้มากที่สุดหนึ่งครั้ง และมุ่งเน้นไปที่การเข้าถึงขั้นสุดท้ายของชุดเริ่มต้น

3

แต่ละแบบจำลองต้องการพารามิเตอร์จำนวนเล็กน้อยที่อิงตามข้อมูลหรือวรรณกรรม: อัตราการส่งผ่าน τ (ความน่าจะเป็นของการแพร่กระจายต่อการสัมผัสต่อช่วงเวลา), อัตราการฟื้นตัว γ (สำหรับ SIR/SIS) และชุดเริ่มต้นของโหนดที่ติดเชื้อหรือทำงานในตอนแรก อัตราส่วน τ/γ กำหนดจำนวนการแพร่พันธุ์พื้นฐาน R₀; เมื่อ R₀ > 1 การระบาดขนาดใหญ่สามารถเกิดขึ้นได้ สำหรับแบบจำลอง Independent Cascade แต่ละเส้นเชื่อมแบบมีทิศทางจะมีความน่าจะเป็นในการกระตุ้นของตัวเอง สมมติฐานการผสมแบบเอกพันธ์ช่วยให้การวิเคราะห์แบบค่าเฉลี่ยสนามง่ายขึ้น แต่สามารถผ่อนคลายได้โดยการจำลองเครือข่ายเต็มรูปแบบ

4

เนื่องจากผลลัพธ์เป็นแบบสุ่ม แบบจำลองจึงถูกรันหลายครั้ง (การทำซ้ำแบบ Monte Carlo) ด้วยพารามิเตอร์เดียวกันและนำผลลัพธ์มาเฉลี่ย แต่ละการรันจะดำเนินไปตามเวลา: ในแต่ละช่วงเวลา โหนดที่ติดเชื้อแต่ละโหนดจะพยายามส่งผ่านไปยังเพื่อนบ้านที่อ่อนแอแต่ละราย และโหนดที่ติดเชื้อจะฟื้นตัวด้วยความน่าจะเป็น γ ผลลัพธ์หลักคืออนุกรมเวลาของขนาดช่อง (S(t), I(t), R(t)), จำนวนการติดเชื้อสูงสุด, เวลาที่ถึงจุดสูงสุด และ — สำหรับแบบจำลองอิทธิพล — สัดส่วนสุดท้ายของโหนดที่ถูกกระตุ้น สำหรับ SIR แบบค่าเฉลี่ยสนาม พลวัตยังสามารถแก้ไขได้เป็นระบบสมการเชิงอนุพันธ์สามัญ

5

ผลลัพธ์จะถูกอ่านเทียบกับคำถามวิจัย: R₀ สูงกว่าเกณฑ์การระบาดหรือไม่? โหนดใดบ้าง หากเลือกเป็นจุดเริ่มต้น จะเพิ่มการแพร่กระจายทั้งหมดให้สูงสุด? ผลลัพธ์มีความอ่อนไหวต่อการเปลี่ยนแปลงของ τ หรือ γ อย่างไร? การวิเคราะห์ความอ่อนไหวและการเปรียบเทียบระหว่างโครงสร้างเครือข่าย (สุ่ม, ไร้มาตราส่วน, โลกขนาดเล็ก) เผยให้เห็นว่าสมมติฐานเชิงโครงสร้างขับเคลื่อนข้อสรุปอย่างไร นักวิเคราะห์ควรรายงานว่าผลลัพธ์มาจากโซลูชันค่าเฉลี่ยสนามแบบกำหนด หรือจากการเฉลี่ยแบบ Monte Carlo เหนือการจำลองแบบสุ่ม และควรรระบุจำนวนการทำซ้ำที่ใช้

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

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

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

ฉันควรใช้ SIR เทียบกับ SIS เทียบกับ Independent Cascade เมื่อใด?

ใช้ SIR เมื่อการฟื้นตัวให้ภูมิคุ้มกันที่ยั่งยืน — เช่นเดียวกับโรคติดเชื้อหลายชนิดหรือการนำเทคโนโลยีมาใช้เพียงครั้งเดียว — เพื่อให้โหนดไม่สามารถกลับไปสู่สถานะอ่อนแอได้หลังจากฟื้นตัว ใช้ SIS เมื่อเงื่อนไขเกิดขึ้นซ้ำ ๆ หรือภูมิคุ้มกันเป็นเพียงชั่วคราว เช่น โรคตามฤดูกาลหรือการสัมผัสข่าวลือซ้ำ ซึ่งโหนดจะหมุนเวียนระหว่างสถานะอ่อนแอและติดเชื้ออย่างไม่มีกำหนด เลือก Independent Cascade หรือ Linear Threshold เมื่อมุ่งเน้นไปที่อิทธิพลทางสังคมและโหนดสามารถทำงานได้มากที่สุดหนึ่งครั้ง; แบบจำลองเหล่านี้เหมาะสำหรับปัญหาการตลาด การแพร่กระจายข้อมูล หรือการนำพฤติกรรมมาใช้ โดยมีเป้าหมายเพื่อเพิ่มจำนวนโหนดที่ถูกกระตุ้นขั้นสุดท้ายจากชุดเริ่มต้นที่เลือก

การทำซ้ำแบบ Monte Carlo จำนวนเท่าใดจึงจะเพียงพอ?

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

ฉันจะประมาณอัตราการส่งผ่าน τ จากข้อมูลได้อย่างไร?

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

แบบจำลองเหล่านี้สามารถทำงานบนเครือข่ายแบบมีน้ำหนักหรือแบบมีทิศทางได้หรือไม่?

ได้ น้ำหนักของเส้นเชื่อมสามารถเข้ารหัสความน่าจะเป็นในการส่งผ่านที่ไม่เป็นเนื้อเดียวกันได้ — คู่ที่เชื่อมโยงกันอย่างแน่นหนาจะมี τ สูงกว่าคู่ที่เชื่อมโยงกันอย่างหลวม ๆ เส้นเชื่อมแบบมีทิศทางจำลองอิทธิพลแบบไม่สมมาตร โดยที่โหนด A สามารถติดเชื้อ B ได้ แต่ B ไม่สามารถติดเชื้อ A ได้โดยตรง การขยายทั้งสองทำได้ง่ายในการจำลองเครือข่ายเต็มรูปแบบ แม้ว่าการประมาณค่าเฉลี่ยสนามจะมีความแม่นยำน้อยลงและมักจะต้องถูกแทนที่ด้วยวิธีการค่าเฉลี่ยสนามแบบไม่เป็นเนื้อเดียวกันตามระดับหรือวิธีการประมาณค่าคู่

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

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

  1. Kermack, W.O. & McKendrick, A.G. (1927). A Contribution to the Mathematical Theory of Epidemics. Proceedings of the Royal Society of London. Series A, 115(772), 700-721.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Kempe, D., Kleinberg, J., & Tardos, E. (2003). Maximizing the Spread of Influence through a Social Network. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 137-146.

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