نموذج باراباسي-ألبرت

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 35 صور
الموسوعة الحرة
عرض لثلاثة رسوم بيانية تم إنشاؤها باستخدام نموذج باراباسي-ألبرت (BA). يحتوي كل رسم بياني على 20 عقدة ومعامل ارتباط m كما هو محدد. يعتمد لون كل عقدة على درجتها (بنفس المقياس لكل رسم بياني).

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

المفاهيم

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

النمو يعني أن عدد العقد في الشبكة يزداد بمرور الوقت.

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

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

الخوارزمية

خطوات نمو الشبكة وفقًا لنموذج باراباسي-ألبرت (م0=م=2{\displaystyle m_{0}=m=2})

المعلمة الوحيدة في نموذج BA هيم{\displaystyle m}، عدد صحيح موجب. تبدأ الشبكة بشبكة منم0≥م{\displaystyle m_{0}\geq m}العقد.

في كل خطوة، أضف عقدة جديدة، ثم قم بأخذ عينة.م{\displaystyle m}يتم اختيار الجيران بين الرؤوس الموجودة في الشبكة، باحتمالية تتناسب مع عدد الروابط التي تمتلكها العقد الموجودة بالفعل (لم تحدد الأوراق الأصلية كيفية التعامل مع الحالات التي يتم فيها اختيار نفس العقدة الموجودة عدة مرات). رسميًا، الاحتماليةصأنا{\displaystyle p_{i}}أن العقدة الجديدة متصلة بالعقدةأنا{\displaystyle i}هو [ 1 ]

صأنا=كأنا∑جكج،{\displaystyle p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}},}

أينكأنا{\displaystyle k_{i}}درجة العقدةأنا{\displaystyle i}ويتم حساب المجموع على جميع العقد الموجودة مسبقًاج{\displaystyle j}(أي أن المقام ينتج عنه ضعف عدد الحواف الحالية في الشبكة). يمكن تنفيذ هذه الخطوة عن طريق أخذ عينة عشوائية منتظمة من حافة واحدة أولاً، ثم أخذ عينة عشوائية من أحد الرأسين الموجودين على الحافة.

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

شبكة شجرية مُولَّدة وفقًا لنموذج باراباسي-ألبرت. تتكون الشبكة من 50 رأسًام=1{\displaystyle m=1}.

ملكيات

توزيع الدرجات

توزيع درجات رؤوس مخطط BA ذي 200000 عقدة وحافتين جديدتين لكل خطوة. مُرسم بمقياس لوغاريتمي مزدوج. يتبع التوزيع قانون القوة بمعامل -2.78.

إن توزيع الدرجات الناتج عن نموذج BA لا يعتمد على المقياس، وعلى وجه الخصوص، فهو قانون قوة من الشكل

P(ك)∼ك-3{\displaystyle P(k)\sim k^{-3}\,}

توزيع مؤشر هيرش

وقد تبين أن مؤشر h أو توزيع مؤشر هيرش هو أيضًا خالٍ من المقياس وتم اقتراحه كمؤشر للوبي، لاستخدامه كمقياس للمركزية [ 2 ].

ح(ك)∼ك-6{\displaystyle H(k)\sim k^{-6}\,}

علاوة على ذلك، يمكن الحصول على نتيجة تحليلية لكثافة العقد ذات مؤشر h يساوي 1 في الحالة التيم0=1{\displaystyle m_{0}=1}

ح(1)|م0=1=4-π{\displaystyle H(1){\Big |}_{m_{0}=1}=4-\pi \,}

ارتباطات درجة العقدة

تنشأ الارتباطات بين درجات العقد المتصلة تلقائيًا في نموذج BA بسبب طريقة تطور الشبكة. الاحتمالية،نكℓ{\displaystyle n_{k\ell }}، إيجاد رابط يربط عقدة من الدرجة ك{\displaystyle k}إلى عقدة سلف من الدرجة ℓ{\displaystyle \ell }في نموذج BA للحالة الخاصة لـم=1{\displaystyle m=1}(شجرة BA) معطاة بواسطة

نكℓ=4(ℓ-1)ك(ك+1)(ك+ℓ)(ك+ℓ+1)(ك+ℓ+2)+12(ℓ-1)ك(ك+ℓ-1)(ك+ℓ)(ك+ℓ+1)(ك+ℓ+2).{\displaystyle n_{k\ell }={\frac {4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}+{\frac {12\left(\ell -1\right)}{k\left(k+\ell -1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}.}

يؤكد هذا وجود ارتباطات في الدرجات، لأنه إذا كانت التوزيعات غير مرتبطة، فسنحصل علىنكℓ=ك-3ℓ-3{\displaystyle n_{k\ell }=k^{-3}\ell ^{-3}}[ 1 ]​

بشكل عامم{\displaystyle m}، نسبة الروابط التي تربط عقدة من الدرجةك{\displaystyle k} إلى عقدة من الدرجة ℓ{\displaystyle \ell }هو [ 3 ]

ص(ك،ℓ)=2م(م+1)ك(ك+1)ℓ(ℓ+1)[1-(2م+2م+1)(ك+ℓ-2مℓ-م)(ك+ℓ+2ℓ+1)].{\displaystyle p(k,\ell )={\frac {2m(m+1)}{k(k+1)\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}

كذلك، توزيع درجة الجوار الأقربص(ℓ|ك){\displaystyle p(\ell \mid k)}أي توزيع درجات جيران عقدة ذات درجةك{\displaystyle k}، يتم تحديده بواسطة [ 3 ]

ص(ℓ|ك)=م(ك+2)كℓ(ℓ+1)[1-(2م+2م+1)(ك+ℓ-2مℓ-م)(ك+ℓ+2ℓ+1)].{\displaystyle p(\ell \mid k)={\frac {m(k+2)}{k\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}

بمعنى آخر، إذا اخترنا عقدة ذات درجة ك{\displaystyle k}ثم نختار أحد جيرانه عشوائيًا، فما احتمال أن يكون لهذا الجار المختار عشوائيًا درجةℓ{\displaystyle \ell }يُعطى بالتعبيرص(ℓ|ك){\displaystyle p(\ell |k)}فوق.

معامل التجميع

القضية المتعلقة بـ م=1{\displaystyle m=1}من البديهي أن الشبكات عبارة عن أشجار، ومعامل التجميع يساوي صفرًا. وقد توصل كليم وإيغيلوز [ 4 ] إلى نتيجة تحليلية لمعامل التجميع في نموذج BA، وأثبتها بولوباس [ 5 ] . كما طبق فرونتشاك وفرونتشاك وهوليست [ 6 ] منهج المجال المتوسط ​​لدراسة معامل التجميع.

يعتمد متوسط ​​معامل التجميع لنموذج باراباسي-ألبرت على حجم الشبكة N:

⟨ج⟩∼لنشمال2/شمال.{\displaystyle \langle C\rangle \sim lnN^{2}/N.}

يختلف هذا السلوك عن سلوك شبكات العالم الصغير حيث يكون التجميع مستقلاً عن حجم النظام.

التجميع كدالة لدرجة العقدةج(ك){\displaystyle C(k)} مستقل عمليًا عنك{\displaystyle k}[ 6 ]​

الخصائص الطيفية

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

الحالات المحددة

النموذج أ

يحتفظ النموذج (أ) بالنمو ولكنه لا يتضمن الارتباط التفضيلي. احتمالية اتصال عقدة جديدة بأي عقدة موجودة مسبقًا متساوية. توزيع الدرجات الناتج في هذه الحالة هندسي، [ 9 ] مما يشير إلى أن النمو وحده لا يكفي لإنتاج بنية لا تعتمد على المقياس.

النموذج ب

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

يشير فشل النموذجين أ و ب في الوصول إلى توزيع لا يعتمد على المقياس إلى أن النمو والارتباط التفضيلي ضروريان في آن واحد لإعادة إنتاج توزيع قانون القوة الثابت الذي لوحظ في الشبكات الحقيقية. [ 1 ]

الارتباط التفضيلي غير الخطي

يمكن اعتبار نموذج BA حالة خاصة من نموذج الارتباط التفضيلي غير الخطي (NLPA) الأكثر عمومية. [ 10 ] خوارزمية NLPA مطابقة لنموذج BA مع استبدال احتمال الارتباط بالشكل الأكثر عمومية.

صأنا=كأناα∑جكجα،{\displaystyle p_{i}={\frac {k_{i}^{\alpha }}{\sum _{j}k_{j}^{\alpha }}},}

أينα{\displaystyle \alpha }هو أس موجب ثابت. إذاα=1{\displaystyle \alpha =1}يُختزل تحليل الانحدار غير الخطي (NLPA) إلى نموذج تحليل الأعمال (BA) ويُشار إليه باسم "الخطي". إذا0<α<1{\displaystyle 0<\alpha <1}يُشار إلى خوارزمية NLPA بأنها "شبه خطية"، ويميل توزيع درجات الشبكة إلى توزيع أسي ممتد .α>1{\displaystyle \alpha >1}يُشار إلى NLPA باسم "الخطية الفائقة"، حيث يتصل عدد قليل من العقد بجميع العقد الأخرى تقريبًا في الشبكة. بالنسبة لكليهماα<1{\displaystyle \alpha <1}وα>1{\displaystyle \alpha >1}تُفقد خاصية التوزيع غير المقياسي للشبكة في حالة حجم النظام اللانهائي. ومع ذلك، إذاα{\displaystyle \alpha }أكبر قليلاً من1{\displaystyle 1}قد ينتج عن NLPA توزيعات درجات تبدو وكأنها خالية من المقياس بشكل مؤقت. [ 11 ]

تاريخ

ظهر مفهوم الارتباط التفضيلي لأول مرة عام 1923 في نموذج الجرة الشهير لعالم الرياضيات المجري جيورجي بوليا . [ 12 ] وطُبقت طريقة المعادلة الرئيسية، التي تُقدم اشتقاقًا أكثر وضوحًا، على هذه المسألة من قِبل هربرت أ. سيمون عام 1955 [ 13 ] خلال دراساته لأحجام المدن وظواهر أخرى. وطُبقت هذه الطريقة لأول مرة لشرح ترددات الاستشهاد من قِبل ديريك دي سولا برايس عام 1976. [ 14 ] كان برايس مهتمًا بتراكم الاستشهادات بالأوراق العلمية، واستخدم نموذجه "الميزة التراكمية" (وهو الاسم الذي أطلقه على الارتباط التفضيلي) لتوليد توزيع ذي ذيل سميك. وبلغة شبكات الاستشهاد الحديثة، يُنتج نموذج برايس شبكة موجهة، أي نسخة من نموذج باراباسي-ألبرت. يعود اسم "الارتباط التفضيلي" والشعبية الحالية لنماذج الشبكات غير المقياسية إلى عمل ألبرت-لازلو باراباسي وريكا ألبرت ، اللذين اكتشفا وجود عملية مماثلة في الشبكات الحقيقية، وقاما بتطبيق الارتباط التفضيلي في عام 1999 لشرح توزيعات الدرجات المرصودة عدديًا على الويب. [ 15 ]

انظر أيضاً

مراجع

  1. 1 2 3 ألبرت, ريكا ; باراباسي، ألبرت لازلو (2002). "الميكانيكا الإحصائية للشبكات المعقدة" (PDF) . مراجعات للفيزياء الحديثة . 74 (47): 47– 97. أرخايف : cond-mat/0106096 . بيب كود : 2002RvMP...74...47A . سيتيسيركس 10.1.1.242.4753 . دوى : 10.1103/RevModPhys.74.47 . S2CID 60545 . مؤرشفة من الأصلي (PDF) بتاريخ 2015-08-24.  
  2. ↑ كورن، أ .؛ شوبرت، أ .؛ تيلكس، أ. (2009). "مؤشر اللوبي في الشبكات". فيزيكا أ . 388 (11): 2221-2226 . arXiv : 0809.0514 . Bibcode : 2009PhyA..388.2221K . doi : 10.1016/j.physa.2009.02.013 . S2CID 1119190 . 
  3. 1 2 فوتوحي، بابك؛ رباط، مايكل (2013). "ارتباط الدرجة في الرسوم البيانية غير المقياسية". المجلة الأوروبية للفيزياء ب . 86 (12): 510. arXiv : 1308.5169 . Bibcode : 2013EPJB...86..510F . doi : 10.1140/epjb/e2013-40920-6 . S2CID 7520124 . 
  4. ↑ كليم، ك.؛ إيغيلوز، ف.س. (2002). "شبكات متنامية خالية من المقاييس ذات سلوك العالم الصغير". مجلة Physical Review E. 65 ( 5) 057102. arXiv : cond-mat/0107607 . Bibcode : 2002PhRvE..65e7102K . doi : 10.1103/PhysRevE.65.057102 . hdl : 10261/15314 . PMID 12059755. S2CID 12945422 .  
  5. ↑ بولوباس، ب. (2003). "نتائج رياضية حول الرسوم البيانية العشوائية غير المقياسية". كتيب الرسوم البيانية والشبكات . ص 1-37 . CiteSeerX 10.1.1.176.6988 .  
  6. 1 2 فرونتشاك، أغاتا؛ فرونتشاك، بيوتر؛ هويست، يانوش أ (2003). "نظرية المجال المتوسط ​​لمعاملات التجميع في شبكات باراباسي-ألبرت". مجلة الفيزياء E. 68 ( 4) 046126. arXiv : cond-mat/0306255 . Bibcode : 2003PhRvE..68d6126F . doi : 10.1103/PhysRevE.68.046126 . PMID 14683021. S2CID 2372695 .  
  7. ↑ فاركاس، آي جيه؛ ديريني، آي؛ باراباسي، أ.-ل؛ فيسيك، تي. (20 يوليو 2001) [19 فبراير 2001]. "أطياف الرسوم البيانية "الواقعية": ما وراء قانون نصف الدائرة". مجلة Physical Review E. 64 ( 2) 026704. arXiv : cond - mat/0102335 . Bibcode : 2001PhRvE..64b6704F . doi : 10.1103/PhysRevE.64.026704 . hdl : 2047/d20000692 . PMID 11497741. S2CID 1434432 .  
  8. ↑ بريسيادو، ف.م.؛ رحيميان، أ. (ديسمبر 2017). "التحليل الطيفي القائم على العزوم للرسوم البيانية العشوائية ذات تسلسل درجة متوقعة مُعطى" . معاملات IEEE في علوم وهندسة الشبكات . 4 (4): 215-228 . arXiv : 1512.03489 . doi : 10.1109/TNSE.2017.2712064 . S2CID 12187100 . 
  9. ↑ بيكوز، إيرول؛ رولين، أ.؛ روس، ن. (2012). "التغير الكلي وحدود الخطأ المحلية للتقريب الهندسي" . برنولي . مؤرشف من الأصل في 23 سبتمبر 2015. تم الاسترجاع في 25 أكتوبر 2012 .
  10. ↑ كرابيفسكي، ب. ل.؛ ريدنر، س.؛ ليفراز، ف. (20 نوفمبر 2000). "ترابط الشبكات العشوائية المتنامية". رسائل المراجعة الفيزيائية . 85 (21): 4629-4632 . arXiv : cond-mat/0005139 . Bibcode : 2000PhRvL..85.4629K . doi : 10.1103 /PhysRevLett.85.4629 . PMID 11082613. S2CID 16251662 .  
  11. ↑ كرابيفسكي، بول؛ كريوكوف، ديمتري (21 أغسطس 2008). "الشبكات غير المقياسية كنظم ما قبل التقارب للارتباط التفضيلي فوق الخطي". مجلة Physical Review E. 78 ( 2) 026114. arXiv : 0804.1366 . Bibcode : 2008PhRvE..78b6114K . doi : 10.1103/PhysRevE.78.026114 . PMID 18850904. S2CID 14292535 .  
  12. ^ ألبرت لازلو، باراباسي (2012). "الحظ أو السبب". طبيعة . 489 (7417): 507-508 . دوى : 10.1038 / طبيعة 11486 . بميد 22972190 . S2CID 205230706 .  
  13. ↑ سيمون، هربرت أ. (ديسمبر 1955). "حول فئة من دوال التوزيع المائل". Biometrika . 42 ( 3-4 ): 425-440 . doi : 10.1093/biomet/42.3-4.425 .
  14. ↑ برايس، دي جيه دي سولا (سبتمبر 1976). "نظرية عامة لعمليات قياس الإنتاجية البحثية وغيرها من عمليات الميزة التراكمية". مجلة الجمعية الأمريكية لعلوم المعلومات . 27 (5): 292-306 . CiteSeerX 10.1.1.161.114 . doi : 10.1002/asi.4630270505 . S2CID 8536863 .  
  15. ^ باراباسي، ألبرت لازلو ؛ ألبرت ، ريكا (أكتوبر 1999). "ظهور التوسع في الشبكات العشوائية" (PDF) . علوم . 286 (5439): 509–512 . أرخايف : cond-mat/9910332 . بيب كود : 1999Sci...286..509B . دوى : 10.1126/science.286.5439.509 . بميد 10521342 . S2CID 524106 . مؤرشفة من الأصلي (PDF) بتاريخ 2012-04-17.