نموذج واتس-ستروغاتز

نموذج واتس-ستروغاتز هو نموذج لتوليد الرسوم البيانية العشوائية ، ينتج رسومًا بيانية ذات خصائص العالم الصغير ، بما في ذلك أطوال المسارات المتوسطة القصيرة والتكتل العالي . اقترحه دنكان ج. واتس وستيفن ستروغاتز في مقالتهما المنشورة عام 1998 في مجلة نيتشر العلمية. ^{[ 1 ]} عُرف النموذج أيضًا باسم نموذج (واتس) بيتا بعد أن استخدمه واتس${\displaystyle \beta }$لصياغتها في كتابه العلمي الشهير "ست درجات" .

يعود تاريخ الدراسة الرسمية للرسوم البيانية العشوائية إلى أعمال بول إردوش وألفريد ريني . ^{[ 2 ]} الرسوم البيانية التي درسوها، والمعروفة الآن باسم الرسوم البيانية الكلاسيكية أو رسوم إردوش-ريني (ER) ، تقدم نموذجًا بسيطًا وقويًا مع العديد من التطبيقات.

ومع ذلك، لا تمتلك مخططات العلاقات بين الكيانات خاصيتين مهمتين لوحظتا في العديد من الشبكات الواقعية:

1. لا تُولّد هذه الرسوم البيانية تجميعًا محليًا ولا إغلاقات ثلاثية . بدلاً من ذلك، ولأنها تتمتع باحتمالية ثابتة وعشوائية ومستقلة لاتصال عقدتين، فإن رسوم ER البيانية لها معامل تجميع منخفض .
2. لا تأخذ هذه النماذج في الحسبان تكوين المحاور. من الناحية الرسمية، يتقارب توزيع درجات مخططات ER إلى توزيع بواسون ، بدلاً من قانون القوة الذي يُلاحظ في العديد من الشبكات الحقيقية غير المقياسية . ^{[ 3 ]}

صُمم نموذج واتس وستروغاتز ليكون أبسط نموذج ممكن يعالج القيد الأول من بين القيدين. فهو يأخذ في الحسبان التكتل مع الحفاظ على متوسط ​​أطوال المسارات القصيرة لنموذج الشبكة الإندوبلازمية-العشوائية. ويتحقق ذلك من خلال الاستيفاء بين بنية عشوائية قريبة من رسوم بيانية الشبكة الإندوبلازمية-العشوائية وشبكة حلقية منتظمة . ونتيجة لذلك، يستطيع النموذج تفسير ظاهرة "العالم الصغير" جزئيًا على الأقل في مجموعة متنوعة من الشبكات، مثل شبكة الطاقة، والشبكة العصبية لديدان C. elegans ، وشبكات ممثلي الأفلام، أو التواصل المتعلق باستقلاب الدهون في الخميرة المتبرعمة . ^{[ 4 ]}

بالنظر إلى العدد المطلوب من العقد${\displaystyle N}$، متوسط ​​الدرجة${\displaystyle K}$(بافتراض أنه عدد صحيح زوجي)، ومعامل${\displaystyle \beta }$كل ذلك مُرضٍ${\displaystyle 0\leq \beta \leq 1}$و${\displaystyle N\gg K\gg \ln N\gg 1}$يقوم النموذج بإنشاء رسم بياني غير موجه مع${\displaystyle N}$العقد و${\displaystyle {\frac {NK}{2}}}$الحواف بالطريقة التالية:

1. قم بإنشاء شبكة حلقية منتظمة، وهي رسم بياني مع${\displaystyle N}$كل عقدة متصلة بـ${\displaystyle K}$الجيران،${\displaystyle K/2}$على كل جانب. أي إذا كانت العقد مُصنَّفة ${\displaystyle 0\ldots {N-1},}$هناك حافة${\displaystyle (i,j)}$إذا وفقط إذا${\displaystyle 0<|ij|\ \mathrm {mod} \ \left(N-1-{\frac {K}{2}}\right)\leq {\frac {K}{2}}.}$
2. لكل عقدة${\displaystyle i=0,\dots ,{N-1}}$استغل كل حافة تربط${\displaystyle i}$إلى خاصته${\displaystyle K/2}$الجيران الأقرب إلى اليمين، أي كل حافة${\displaystyle (i,j)}$بحيث${\displaystyle 0<(ji)\ \mathrm {mod} \ N\leq K/2}$وأعد توصيله باحتمالية${\displaystyle \beta }$تتم عملية إعادة التوصيل عن طريق الاستبدال${\displaystyle (i,j)}$مع${\displaystyle (i,k)}$أين${\displaystyle k}$يتم اختيارها بشكل عشوائي ومنتظم من بين جميع العقد الممكنة مع تجنب الحلقات الذاتية (${\displaystyle k\neq i}$) وتكرار الروابط (لا يوجد حافة${\displaystyle (i,{k'})}$مع${\displaystyle k'=k}$(في هذه المرحلة من الخوارزمية).

تُنتج بنية الشبكة الأساسية للنموذج شبكةً مُتكتلةً محليًا، بينما تُقلل الروابط المُعاد توصيلها عشوائيًا بشكلٍ كبيرٍ من متوسط ​​أطوال المسارات . تُدخل الخوارزمية حوالي${\displaystyle \beta {\frac {NK}{2}}}$من هذه الحواف غير الشبكية. متغيرة${\displaystyle \beta }$يُتيح ذلك إمكانية الاستيفاء بين شبكة منتظمة (${\displaystyle \beta =0}$) وبنية قريبة من الرسم البياني العشوائي Erdős-Rényi${\displaystyle G(N,p)}$مع${\displaystyle p={\frac {K}{N-1}}}$في${\displaystyle \beta =1}$لا يقترب هذا من نموذج العلاقات الكيانية الفعلي، حيث ستكون كل عقدة متصلة على الأقل بـ${\displaystyle K/2}$عقد أخرى.

الخصائص الثلاث محل الاهتمام هي متوسط ​​طول المسار ، ومعامل التجميع ، وتوزيع الدرجة .

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

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

• شبكات العالم الصغير
• نموذج إردوش-ريني (ER)
• نموذج باراباسي-ألبرت
• الشبكات الاجتماعية