توجيه العالم الصغير

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 10 صور
الموسوعة الحرة

في نظرية الشبكات ، يشير توجيه العالم الصغير إلى أساليب التوجيه الخاصة بشبكات العالم الصغير . تتميز هذه الشبكات بوجود مسارات قصيرة نسبيًا بين أي عقدتين. مع ذلك، قد يمثل تحديد هذه المسارات مشكلة معقدة من منظور عقدة توجيه فردية في الشبكة إذا لم تتوفر معلومات إضافية عن الشبكة ككل.

التوجيه الجشع

تعتمد جميع حلول مشكلة التوجيه في الشبكات الصغيرة تقريبًا على التوجيه الجشع . يعتمد هذا النوع من التوجيه على نقطة مرجعية نسبية، حيث يمكن لأي عقدة في المسار اختيار العقدة التالية الأقرب إلى الوجهة. أي أنه يجب أن يكون هناك معيارٌ للجشع، كالموقع الجغرافي أو عنوان IP ، على سبيل المثال. في تجربة ميلغرام الأصلية للشبكات الصغيرة ، كان المشاركون على دراية بموقع المستلم النهائي ووظيفته، وبالتالي تمكنوا من إعادة توجيه الرسائل بناءً على هذه المعايير.

إنشاء قاعدة مرجعية

لن ينجح التوجيه الجشع بسهولة عند غياب قاعدة مرجعية واضحة. قد يحدث هذا، على سبيل المثال، في الشبكات المتراكبة حيث لا تتوفر معلومات حول موقع الوجهة في الشبكة الأساسية. تُعد شبكات الأصدقاء مثالًا خاصًا على هذه المشكلة. في مثل هذه الشبكات، يُضمن عنصر الثقة من خلال معرفة المعلومات الأساسية فقط عن العقد التي تربطك بها علاقة جارة.

يتمثل أحد الحلول في هذه الحالة في فرض نوع من العنونة الاصطناعية على العقد بطريقة تسمح باستخدام هذه العنونة بفعالية بواسطة طرق التوجيه الجشعة. تناقش ورقة بحثية نُشرت عام ٢٠٠٥ لأحد مطوري مشروع فري نت كيفية تحقيق ذلك في شبكات الأصدقاء . وبافتراض أن هذه الشبكات تُظهر خصائص العالم الصغير، غالبًا نتيجةً لعلاقات العالم الحقيقي أو علاقات التعارف، فمن الممكن استعادة رسم بياني مضمن لشبكة كلاينبرغ للعالم الصغير. ويتحقق ذلك عن طريق اختيار أزواج عشوائية من العقد، وربما تبديلها بناءً على دالة هدف تُقلل حاصل ضرب جميع المسافات بين أي عقدة معينة وجيرانها.

تتمثل إحدى المشكلات المهمة في هذا الحل في إمكانية الوصول إلى الحد الأدنى المحلي . قد يحدث هذا إذا كانت العقد في وضع مثالي بالنظر فقط إلى الجوار المحلي، مع تجاهل إمكانية الوصول إلى وضع أمثل أعلى نتيجةً لعمليات التبادل مع عقد بعيدة. في الورقة البحثية المذكورة أعلاه، اقترح المؤلفون طريقة التلدين المحاكي حيث تُجرى عمليات التبادل الأقل مثالية باحتمالية ضئيلة. تتناسب هذه الاحتمالية مع قيمة إجراء عمليات التبادل. هناك طريقة أخرى ممكنة للتحسين الميتاهوريستي وهي البحث المحظور ، الذي يُضيف ذاكرة إلى قرار التبادل. في أبسط صوره، يتم تذكر سجل محدود لعمليات التبادل السابقة بحيث يتم استبعادها من قائمة العقد التي يُحتمل تبادلها.

يمكن تكييف هذه الطريقة لإنشاء قاعدة مرجعية مع البيئات الموزعة، حيث تُتخذ القرارات على مستوى العقد الفردية فقط، دون معرفة مسبقة بالشبكة ككل. ويتضح أن التعديل الوحيد المطلوب يكمن في طريقة اختيار أزواج العقد العشوائية. في البيئة الموزعة، يتم ذلك بأن تُرسل كل عقدة دوريًا مسارًا عشوائيًا ينتهي عند عقدة مُرشحة للتبديل.

نموذج كلاينبرغ

يُعدّ نموذج كلاينبرغ للشبكة فعالاً في إثبات فعالية توجيه العالم الصغير الجشع. يستخدم النموذج شبكة مربعة من n×n عقدة لتمثيل الشبكة، حيث ترتبط كل عقدة بجيرانها بحافة غير موجهة. ولإضفاء تأثير "العالم الصغير"، تُضاف إلى الشبكة عدد من الحواف طويلة المدى التي تميل إلى تفضيل العقد الأقرب مسافةً على العقد الأبعد. عند إضافة الحواف، يتغير احتمال توصيل أي رأس عشوائي.v{\displaystyle v}إلى رأس عشوائي آخر w يتناسب مع1/د(v،w)q{\displaystyle 1/d(v,w)^{q}}، أينq{\displaystyle q}هو معامل التجميع. [ 1 ]

التوجيه الجشع في نموذج كلاينبيرج

من السهل ملاحظة أن الخوارزمية الجشعة ، دون استخدام الحواف طويلة المدى، يمكنها التنقل من رؤوس عشوائيةv→w{\displaystyle v\rightarrow w}على الشبكة فييا(ن){\displaystyle O(n)}مع مرور الوقت، وباتباع الاتصالات المضمونة مع جيراننا، يمكننا التحرك وحدة واحدة في كل مرة باتجاه وجهتنا. وينطبق هذا أيضًا على مكون التجميع.q{\displaystyle q}عندما تكون كبيرة، فإن الحواف "بعيدة المدى" تبقى قريبة جدًا؛ ببساطة لا نستفيد من الروابط الأضعف في هذا النموذج.q=0{\displaystyle q=0}تتصل الحواف طويلة المدى بشكل عشوائي منتظم، مما يعني أن هذه الحواف "عشوائية للغاية" بحيث لا يمكن استخدامها بكفاءة في البحث اللامركزي. وقد أظهر كلاينبرغ أن معامل التجميع الأمثل لهذا النموذج هوq=2{\displaystyle q=2}أو توزيع التربيع العكسي. [ 2 ]

ولتفسير ذلك، إذا رُسمت دائرة نصف قطرها r حول العقدة الأولية، فسيكون لها كثافة عقديةن/(πر2){\displaystyle n/(\pi r^{2})}حيث n هو عدد العقد في المنطقة الدائرية. ومع توسع هذه الدائرة، يزداد عدد العقد في المنطقة المحددة بشكل متناسب معر2{\displaystyle r^{2}}حيث أن احتمال وجود رابط عشوائي مع أي عقدة يظل متناسبًا1/ر2{\displaystyle 1/r^{2}}وهذا يعني أن احتمال وجود علاقة ضعيفة بين العقدة الأصلية وأي عقدة أخرى على مسافة معينة لا يعتمد فعلياً على المسافة. لذلك، نستنتج أنه معq=2{\displaystyle q=2}، يتم توزيع الحواف طويلة المدى بالتساوي على جميع المسافات، وهو أمر فعال يسمح لنا بالتوجه إلى وجهتنا النهائية.

غالباً ما تقوم بعض أنظمة الند للند المهيكلة القائمة على جداول التجزئة الموزعة (DHTs) بتطبيق متغيرات من طوبولوجيا العالم الصغير لكلاينبرغ لتمكين التوجيه الفعال داخل شبكة الند للند ذات درجات العقد المحدودة. [ 3 ]

انظر أيضاً

مراجع

  1. ↑ كلاينبرغ، جون. "الشبكات والحشود والأسواق: التفكير في عالم شديد الترابط" (ملف PDF) . تم الاطلاع عليه بتاريخ 10 مايو 2011 .
  2. ↑ كلاينبرغ، جون م. (أغسطس 2000). "الملاحة في عالم صغير" . مجلة نيتشر . 406 (6798): 845. Bibcode : 2000Natur.406..845K . doi : 10.1038/35022643 . ISSN 1476-4687 . PMID 10972276 .  
  3. ↑ مانكو، جورميت سينغ مانكو. "سيمفونية: التجزئة الموزعة في عالم صغير" (ملف PDF) . usenix.org .