การสร้างเครือข่าย
การก่อตัวของเครือข่ายเป็นสาขาหนึ่งของวิทยาศาสตร์เครือข่ายที่มุ่งสร้างแบบจำลองวิวัฒนาการของเครือข่ายโดยการระบุปัจจัยที่มีผลต่อโครงสร้างของเครือข่ายและวิธีการทำงานของกลไกเหล่านั้น สมมติฐานเกี่ยวกับการก่อตัวของ เครือข่าย จะได้รับการทดสอบโดยใช้แบบจำลองพลวัตที่มีขนาดเครือข่ายเพิ่มขึ้น หรือโดยการสร้างแบบจำลองที่ใช้ตัวแทนเพื่อกำหนดว่าโครงสร้างเครือข่ายใดเป็นสมดุลในเครือข่ายที่มีขนาดคงที่
แบบจำลองไดนามิก
แบบจำลองพลวัต ซึ่งมักใช้โดยนักฟิสิกส์และนักชีววิทยาเริ่มต้นจากเครือข่ายขนาดเล็กหรือแม้แต่โหนดเดียว จากนั้นผู้สร้างแบบจำลองจะใช้กฎ (โดยปกติจะเป็นแบบสุ่ม) ในการกำหนดวิธีการที่โหนด ใหม่ที่เข้ามา จะสร้างการเชื่อมโยงเพื่อเพิ่มขนาดของเครือข่าย จุดมุ่งหมายคือการกำหนดคุณสมบัติของเครือข่ายเมื่อมันเติบโตขึ้น ในวิธีนี้ นักวิจัยพยายามจำลองคุณสมบัติที่พบได้ทั่วไปในเครือข่ายจริงส่วนใหญ่ เช่น คุณสมบัติ ของเครือข่ายโลกขนาดเล็กหรือ คุณสมบัติ ของเครือข่ายไร้มาตราส่วนคุณสมบัติเหล่านี้พบได้ทั่วไปในเครือข่ายจริงเกือบทุกเครือข่าย รวมถึงเวิลด์ไวด์เว็บเครือข่ายเมตาบอลิซึมหรือเครือข่ายเส้นทางบินระหว่างประเทศ
แบบจำลองที่เก่าแก่ที่สุดในประเภทนี้คือแบบจำลอง Erdős-Rényiซึ่งโหนดใหม่จะเลือกโหนดอื่นที่จะเชื่อมต่อแบบสุ่ม แบบจำลองที่รู้จักกันดีอีกแบบหนึ่งคือแบบจำลอง Watts และ Strogatz ซึ่งเริ่มต้นจาก โครงข่ายสองมิติมาตรฐานและพัฒนาโดยการแทนที่ลิงก์แบบสุ่ม แบบจำลองเหล่านี้แสดงคุณสมบัติของเครือข่ายที่สมจริงบางประการ แต่ไม่สามารถอธิบายคุณสมบัติอื่นๆ ได้
หนึ่งในแบบจำลองการก่อตัวของเครือข่ายที่มีอิทธิพลมากที่สุดคือแบบจำลอง Barabási-Albertในแบบจำลองนี้ เครือข่ายเริ่มต้นจากระบบขนาดเล็กเช่นกัน และโหนดขาเข้าจะเลือกการเชื่อมต่อแบบสุ่ม แต่การสุ่มนั้นไม่สม่ำเสมอ โหนดที่มีการเชื่อมต่ออยู่แล้วจำนวนมากจะมีโอกาสเชื่อมต่อกับโหนดขาเข้าได้มากกว่า กลไกนี้เรียกว่าการเชื่อมต่อแบบเลือกปฏิบัติ (preferential attachment ) เมื่อเปรียบเทียบกับแบบจำลองก่อนหน้านี้ แบบจำลอง Barabási-Albert ดูเหมือนจะสะท้อนปรากฏการณ์ที่สังเกตได้ในเครือข่ายในโลกแห่งความเป็นจริงได้แม่นยำกว่า
แบบจำลองตามตัวแทน
แนวทางที่สองในการจำลองการก่อตัวของเครือข่ายคือการสร้างแบบจำลองโดยใช้ทฤษฎีตัวแทนหรือทฤษฎีเกมในแบบจำลองเหล่านี้ จะสร้างเครือข่ายที่มีจำนวนโหนดหรือตัวแทนคงที่ ตัวแทนแต่ละตัวจะได้รับฟังก์ชันอรรถประโยชน์ซึ่งเป็นตัวแทนของความชอบในการเชื่อมโยง และได้รับคำสั่งให้สร้างการเชื่อมโยงกับโหนดอื่น ๆ โดยอิงจากฟังก์ชันนั้น โดยปกติแล้ว การสร้างหรือการรักษาการเชื่อมโยงจะมีต้นทุน แต่การมี1การเชื่อมต่อกับโหนดอื่น ๆ จะมีผลประโยชน์ วิธีนี้จะทดสอบสมมติฐานที่ว่า เมื่อกำหนดค่าเริ่มต้นและค่าพารามิเตอร์บางอย่างแล้ว โครงสร้างเครือข่ายบางอย่างจะเกิดขึ้นเป็นสมดุลของเกมนี้ เนื่องจากจำนวนโหนดมักจะคงที่ จึงแทบจะไม่สามารถอธิบายคุณสมบัติของเครือข่ายขนาดใหญ่ในโลกแห่งความเป็นจริงได้เลย อย่างไรก็ตาม แบบจำลองเหล่านี้มีประโยชน์มากในการตรวจสอบการก่อตัวของเครือข่ายในกลุ่มเล็ก ๆ
แจ็กสันและโวลินสกีเป็นผู้บุกเบิกแบบจำลองประเภทนี้ในบทความปี 1996 ซึ่งต่อมาได้เป็นแรงบันดาลใจให้กับแบบจำลองทฤษฎีเกมหลายแบบ[ 1 ]แบบจำลองเหล่านี้ได้รับการพัฒนาเพิ่มเติมโดยแจ็กสันและวัตต์ ซึ่งนำแนวทางนี้ไปใช้ในบริบทแบบไดนามิกเพื่อดูว่าโครงสร้างเครือข่ายมีการเปลี่ยนแปลงอย่างไรเมื่อเวลาผ่านไป[ 2 ]
โดยทั่วไป เกมที่มีโครงสร้างเครือข่ายที่ทราบแล้วนั้นสามารถนำไปประยุกต์ใช้ได้อย่างกว้างขวาง อย่างไรก็ตาม มีหลายสถานการณ์ที่ผู้เล่นมีปฏิสัมพันธ์กันโดยไม่รู้ว่าเพื่อนบ้านของตนคือใครและโครงสร้างเครือข่ายเป็นอย่างไร เกมเหล่านี้สามารถจำลองได้โดยใช้เกมเครือข่ายที่มีข้อมูลไม่สมบูรณ์
การขยายเครือข่ายในสภาพแวดล้อมแบบเอเจนต์
มีแบบจำลองน้อยมากที่พยายามผสมผสานทั้งสองแนวทางเข้าด้วยกัน อย่างไรก็ตาม ในปี 2550 แจ็กสันและโรเจอร์สได้สร้างแบบจำลองเครือข่ายที่กำลังเติบโต โดยที่โหนดใหม่เลือกการเชื่อมต่อโดยอาศัยการเลือกแบบสุ่มบางส่วน และอาศัยการเพิ่มฟังก์ชันอรรถประโยชน์สูงสุดบางส่วน[ 3 ]ด้วยกรอบการทำงานทั่วไปนี้ นักสร้างแบบจำลองสามารถจำลองลักษณะเฉพาะของเครือข่ายในชีวิตจริงได้เกือบทุกอย่าง