هذه المقالة يتيمة. ساعد بإضافة وصلة إليها في مقالة متعلقة بها

نموذج الشبكة الهرمية

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

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

الفكرة[عدل]

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

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

الخوارزميات[عدل]

عادة ما تُستمد نماذج الشبكة الهرمية في طريقة متكررة عن طريق استبدال المجموعة الأولية للشبكة وفقًا لقاعدة معينة. على سبيل المثال، عند دارسة أي شبكة أولية تتكون من خمس عقد مترابطة تمامًا (N=5). تتمثل الخطوة التالية في إنشاء أربع نسخ متماثلة من هذه المجموعة وتوصيل العقد المحيطة لكل نسخة مماثلة بالعقدة المركزية للمجموعة الأصلية (N=25). ويمكن تكرار هذه الخطوة إلى ما لا نهاية، ولذا ففي أي خطوات رئيسية قد يُستمد عدد العقد في النظام عن طريق N=5k+1.‏[1]

بالطبع هناك عدة طرق مختلفة لإنشاء نظم هرمية تم اقتراحها في الكتابات المتعلقة بهذا الموضوع. وعادة ما تختلف هذه الأنظمة في بنية المجموعة الأولية إضافة إلى درجة التمدد التي يشار إليها في كثير من الأحيان على أنها عامل النسخ المتماثل [2][3]

مثال على بنية الشبكة الهرمية.

الخصائص[عدل]

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

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

P\left(k\right)\sim ck^{-\gamma} \,

حيث إن c هي الثابت وأن γ هي درجة الأس. وفي معظم شبكات العالم الحقيقي التي تحمل خصائص عديمة القياس γ التي تقع في الفترة الفاصلة [2 و3].[4]

ونتيجة للنماذج الهرمية، قد ثبت أنه يمكن حساب درجة الأس لدالة التوزيع كما يلي

\gamma=1+\frac{lnM}{ln(M-1)}

حيث تمثل M عامل النسخ المتماثل للنموذج.[5]

معامل التجميع[عدل]

على العكس من النماذج عديمة القياس الأخرى (إيردوس ريني وباراباسي ألبرت وواتس ستروجاتس) حيث يكون معامل التجميع مستقلاً عن درجة عقدة معينة، يمكن التعبير عن معامل التجميع في الشبكات الهرمية على أنه دالة الدرجة كالتالي:

C\left(k\right)\sim k^{-\beta} \,

وقد أظهرت بصورة تحليلية أنه في الشبكات الحتمية عديمة القياس الأس β يأخذ القيمة1.[2]

أمثلة[عدل]

شبكة الممثلين[عدل]

استنادًا إلى قاعدة بيانات الممثلين المتوفرة على موقع www.IMDB.com فإنه يتم تحديد الشبكة عن طريق ممثلي هوليود المتصلين ببعضهم البعض إذا ظهروا معًا في فيلم واحد، ونتج عن ذلك مجموعة بيانات 392340 عقدة و15347957 حواف. وكما أظهرت دراسات أُجريت في وقت مبكر، فإن هذه الشبكة تحمل خصائص عديمة المقياس على الأقل فيما يتعلق بالقيم العالية لـk. إضافة إلى ذلك، يبدو أن معاملات التجميع تابعة لقانون القياس المطلوب مع المعامل -1 الذي قدم دليلاً على طوبولوجيا الشبكة الهرمية. بديهيًا، يمتلك ممثلو الدور الواحد بحكم التعريف معامل تجميع واحدًا بينما لا يكون عند الممثلين النجوم في عدة أفلام الرغبة في العمل مع الطاقم ذاته مما يؤدي إلى نتائج عامة في تقليل معامل التجميع على أنه رقم زيادة الممثلين النجوم المشتركين.[1]

شبكة اللغة[عدل]

يمكن اعتبار الكلمات على أنها شبكة إذا حدد شخص معايير الارتباط بين هذه الكلمات. تم إنشاء تحديد الروابط على أنها مفردات في قاموس ميريام وبستر (Merriam-Webster) لشبكة معاني 182853 عقدة مع 317658 حافة. وبما أنه تم تجميع هذه الكلمات، فإن شبكة الكلمات التي تم الحصول عليها في الواقع تتبع قانون القوة في توزيع الدرجات بينما يشير توزيع معامل التجميع إلى أن الويب الضمنية تتبع البنية الهرمية مع γ=3.25 وβ=1.‏[1]

شبكة صفحات الويب[عدل]

عن طريق وضع خرائط المجال www.nd.edu تم الحصول على شبكة بها 325729 عقدة و1497135 حافة التي تتبع قانون القوة مع γout=2.45 وγin=2.1 فيما يتعلق بالناتج - وبالدرجات على التوالي. ويعد دليل توزيع قانون المقياس لمعاملات التجميع ضعيفًا بدرجة كبيرة عما كان في الحالات السابقة ومع ذلك هناك نموذج متدنٍ مرئي واضح في توزيع C(k) مما يشير إلى أن معظم روابط المجال لديها أقل قوة اتصال بصفحات الويب.[1][6]

شبكة المجال[عدل]

وجد أن مجال الشبكة، أي الإنترنت في مستوى النظام الحر حيث يقال إن المجالات الإدارية تكون متصلة في حالة وجود جهاز توجيه يعمل على توصيلها معًا لتشكل 65520 عقدة و24412 ارتباطًا، يحمل صفات الشبكة عديمة القياس. تمت ملاءمة توزيع نموذج معاملات التجميع عن طريق وظيفة القياس C(k) ويمثل أُسها (من حيث القيمة المطلقة) أصغر إلى حد ما من المعامل النظري لشبكات عديمة القياس.[1][7]

المراجع[عدل]

  1. ^ أ ب ت ث ج Ravasz، E. B.؛ Barabási، A. L. S. (2003). "Hierarchical organization in complex networks". Physical Review E 67 (2). arXiv:cond-mat/0206130. Bibcode:2003PhRvE..67b6112R. doi:10.1103/PhysRevE.67.026112.  edit
  2. ^ أ ب Dorogovtsev، S.؛ Goltsev، A.؛ Mendes، J. (2002). "Pseudofractal scale-free web". Physical Review E 65 (6). arXiv:cond-mat/0112143. Bibcode:2002PhRvE..65f6122D. doi:10.1103/PhysRevE.65.066122.  edit
  3. ^ Barabási، A. L. S.؛ Ravasz، E. B.؛ Vicsek، T. S. (2001). "Deterministic scale-free networks". Physica A: Statistical Mechanics and its Applications 299 (3–4): 559. doi:10.1016/S0378-4371(01)00369-7.  edit
  4. ^ BarabÁSi، A.؛ Albert، R. (1999). "Emergence of Scaling in Random Networks". Science 286 (5439): 509–512. doi:10.1126/science.286.5439.509. PMID 10521342.  edit
  5. ^ Noh، J. (2003). "Exact scaling properties of a hierarchical network model". Physical Review E 67 (4). arXiv:cond-mat/0211399. Bibcode:2003PhRvE..67d5103N. doi:10.1103/PhysRevE.67.045103.  edit
  6. ^ Barabási، A. L. S.؛ Albert، R. K.؛ Jeong، H. (1999). Nature 401 (6749): 130. doi:10.1038/43601.  edit
  7. ^ Vázquez، A.؛ Pastor-Satorras، R.؛ Vespignani، A. (2002). "Large-scale topological and dynamical properties of the Internet". Physical Review E 65 (6). arXiv:cond-mat/0112400. Bibcode:2002PhRvE..65f6130V. doi:10.1103/PhysRevE.65.066130.  edit