การกำหนดเส้นทางโลกขนาดเล็ก

Q: ข้อมูลสำคัญเกี่ยวกับ การกำหนดเส้นทางโลกขนาดเล็ก

ในทฤษฎีเครือข่าย การกำหนดเส้นทางแบบโลกเล็ก ( small-world routing)หมายถึงวิธีการกำหนดเส้นทางสำหรับเครือข่ายแบบโลกเล็กเครือข่ายประเภทนี้มีความพิเศษตรงที่เส้นทางระหว่างโหนดสองโหนดใดๆ.

ในทฤษฎีเครือข่าย การกำหนดเส้นทางแบบโลกเล็ก ( small-world routing)หมายถึงวิธีการกำหนดเส้นทางสำหรับเครือข่ายแบบโลกเล็กเครือข่ายประเภทนี้มีความพิเศษตรงที่เส้นทางระหว่างโหนดสองโหนดใดๆ นั้นค่อนข้างสั้น อย่างไรก็ตาม การกำหนดเส้นทางเหล่านี้อาจเป็นปัญหาที่ยากสำหรับโหนดกำหนดเส้นทางแต่ละโหนดในเครือข่าย หากไม่มีข้อมูลเพิ่มเติมเกี่ยวกับเครือข่ายโดยรวม

การกำหนดเส้นทางแบบโลภ

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

การสร้างฐานข้อมูลอ้างอิง

การกำหนดเส้นทางแบบโลภ (Greedy routing) จะใช้ไม่ได้ผลหากไม่มีฐานอ้างอิงที่ชัดเจน ตัวอย่างเช่น อาจเกิดขึ้นในเครือข่ายแบบโอเวอร์เลย์ (Overlay network)ที่ไม่มีข้อมูลเกี่ยวกับตำแหน่งของปลายทางในเครือข่ายพื้นฐาน เครือข่าย แบบเพื่อนต่อเพื่อน (Friend-to-friend network) เป็นตัวอย่างหนึ่งของปัญหานี้ ในเครือข่ายดังกล่าว ความน่าเชื่อถือเกิดจากข้อเท็จจริงที่ว่าคุณรู้เฉพาะข้อมูลพื้นฐานเกี่ยวกับโหนดที่คุณเป็นเพื่อนบ้านอยู่แล้วเท่านั้น

วิธีแก้ปัญหาอย่างหนึ่งในกรณีนี้คือ การกำหนดแอดเดรสเทียมให้กับโหนดต่างๆ ในลักษณะที่แอดเดรสนี้สามารถนำไปใช้ได้อย่างมีประสิทธิภาพโดยวิธีการกำหนดเส้นทางแบบโลภ (greedy routing methods) บทความปี 2005โดยผู้พัฒนาโครงการ Freenetได้กล่าวถึงวิธีการนี้ใน เครือข่าย แบบเพื่อนต่อเพื่อน (friend to friend networks) โดยสมมติว่าเครือข่ายเหล่านี้มีคุณสมบัติแบบโลกขนาดเล็ก (small world properties) ซึ่งมักเป็นผลมาจากความสัมพันธ์ในโลกแห่งความเป็นจริงหรือความสัมพันธ์แบบคนรู้จัก ดังนั้นจึงควรสามารถกู้คืน กราฟแบบโลกขนาดเล็ก ของ Kleinberg ที่ฝังอยู่ได้ ซึ่งทำได้โดยการเลือกคู่โหนดแบบสุ่มและอาจสลับโหนดเหล่านั้นโดยอิงจากฟังก์ชันเป้าหมายที่ลดผลคูณของระยะทางทั้งหมดระหว่างโหนดใดๆ กับโหนดเพื่อนบ้านให้เหลือน้อยที่สุด

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

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

แบบจำลองไคลน์เบิร์ก

แบบจำลองเครือข่ายของไคลน์เบิร์กมีประสิทธิภาพในการแสดงให้เห็นถึงประสิทธิผลของการกำหนดเส้นทางแบบโลภในโลกขนาดเล็ก (greedy small world routing) แบบจำลองนี้ใช้ตารางขนาด nxn ของโหนดเพื่อแสดงเครือข่าย โดยแต่ละโหนดเชื่อมต่อกับโหนดข้างเคียงด้วยเส้นขอบที่ไม่กำหนดทิศทาง เพื่อให้ได้ผลลัพธ์แบบ "โลกขนาดเล็ก" จึงมีการเพิ่มเส้นขอบระยะไกลจำนวนหนึ่งเข้าไปในเครือข่าย ซึ่งมีแนวโน้มที่จะเลือกโหนดที่อยู่ใกล้กว่ามากกว่าโหนดที่อยู่ไกลออกไป เมื่อเพิ่มเส้นขอบ ความน่าจะเป็นของการเชื่อมต่อจุดยอดแบบสุ่มบางจุดจะถูกคำนวณ $v$ ไปยังจุดยอดสุ่มอื่น w นั้นเป็นสัดส่วนกับ $1/d(v,w)^{q}$ , ที่ไหน $q$ คือเลขชี้กำลังการจัดกลุ่ม^{[ 1 ]}

การกำหนดเส้นทางโลภในโมเดลไคลน์เบิร์ก

เห็นได้ชัดว่าอัลกอริทึมแบบโลภ (greedy algorithm)โดยไม่ต้องใช้ขอบระยะไกล สามารถนำทางจากจุดยอดแบบสุ่มได้ $v\ลูกศรขวา w$ บนตารางใน $O(n)$ เวลา โดยการติดตามการเชื่อมต่อที่รับประกันกับเพื่อนบ้านของเรา เราสามารถเคลื่อนที่ทีละหน่วยไปในทิศทางของจุดหมายปลายทางของเราได้ กรณีนี้ก็เช่นเดียวกันเมื่อใช้ส่วนประกอบการจัดกลุ่ม $q$ มีขนาดใหญ่ และขอบเขต "ระยะไกล" ก็มักจะอยู่ใกล้กันมาก เราไม่ได้ใช้ประโยชน์จากความสัมพันธ์ที่อ่อนแอกว่าในแบบจำลองนี้เลย เมื่อ $q=0$ ขอบระยะไกลเชื่อมต่อกันแบบสุ่มอย่างสม่ำเสมอ ซึ่งหมายความว่าขอบระยะไกลนั้น "สุ่มเกินไป" ที่จะนำมาใช้ได้อย่างมีประสิทธิภาพสำหรับการค้นหาแบบกระจายศูนย์ ไคลน์เบิร์กได้แสดงให้เห็นว่าค่าสัมประสิทธิ์การจัดกลุ่ม ที่เหมาะสมที่สุด สำหรับแบบจำลองนี้คือ $q=2$ หรือการกระจายกำลังสองผกผัน^{[ 2 ]}

เพื่ออธิบายว่าทำไมจึงเป็นเช่นนั้น หากลากวงกลมที่มีรัศมี r รอบโหนดเริ่มต้น วงกลมนั้นจะมีความหนาแน่นของโหนดเท่ากับ r $n/(\pi r^{2})$ โดยที่ n คือจำนวนจุดในพื้นที่วงกลม เมื่อวงกลมนี้ขยายออกไป จำนวนจุดในพื้นที่ที่กำหนดจะเพิ่มขึ้นตามสัดส่วนของ $r^{2}$ เนื่องจากความน่าจะเป็นที่จะมีลิงก์แบบสุ่มกับโหนดใดๆ ยังคงเป็นสัดส่วนกัน $1/r^{2}$ หมายความว่า ความน่าจะเป็นที่โหนดเดิมจะมีสายสัมพันธ์ที่อ่อนแอต่อโหนดใดๆ ที่อยู่ห่างออกไปในระยะทางที่กำหนดนั้น แทบจะไม่ขึ้นอยู่กับระยะทางเลย ดังนั้นจึงสรุปได้ว่า ด้วย $q=2$ ขอบเขตระยะไกลจะกระจายตัวอย่างสม่ำเสมอในทุกระยะทาง ซึ่งมีประสิทธิภาพในการช่วยให้เราเดินทางไปยังจุดหมายปลายทางสุดท้ายได้อย่างราบรื่น

ระบบ Peer-to-peer ที่มีโครงสร้างบางระบบที่ใช้ DHT มักจะนำรูปแบบต่างๆ ของโทโพโลยี Small-World ของ Kleinberg มาใช้เพื่อให้สามารถกำหนดเส้นทางได้อย่างมีประสิทธิภาพภายในเครือข่าย Peer-to-peer ที่มีระดับโหนดจำกัด^{[ 3 ]}

ดูเพิ่มเติม

เครือข่ายสังคม– โครงสร้างทางสังคมที่ประกอบด้วยกลุ่มผู้มีบทบาททางสังคม
เครือข่ายโลกขนาดเล็ก– กราฟที่โหนดส่วนใหญ่สามารถเข้าถึงได้ด้วยจำนวนขั้นตอนเพียงเล็กน้อย
แบบจำลอง Watts-Strogatz – วิธีการสร้างกราฟแบบ Small-world แบบสุ่ม หน้าเว็บที่แสดงคำอธิบายสั้น ๆ ของเป้าหมายการเปลี่ยนเส้นทาง

[ 1 ]

[ 2 ]

[ 3 ]