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

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

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

يُعرَّف توزيع الدرجات P ( k ) لشبكة ما بأنه نسبة العقد في الشبكة التي لها الدرجة k . وبالتالي، إذا كان هناك n عقدة إجمالاً في الشبكة، و _nk منها لها الدرجة k ، فإننا نحصل على

${\displaystyle P(k)={\frac {n_{k}}{n}}}$.

يتم عرض نفس المعلومات أحيانًا في شكل توزيع الدرجة التراكمية ، وهو نسبة العقد ذات الدرجة الأصغر من k ، أو حتى توزيع الدرجة التراكمية التكميلي ، وهو نسبة العقد ذات الدرجة الأكبر من أو تساوي k ( 1 - C ) إذا اعتبرنا C هو توزيع الدرجة التراكمية ؛ أي مكمل C.

يُعد توزيع الدرجات بالغ الأهمية في دراسة الشبكات الحقيقية، مثل الإنترنت والشبكات الاجتماعية ، والشبكات النظرية. أبسط نموذج للشبكة، على سبيل المثال، هو الرسم البياني العشوائي (نموذج إردوش-ريني) ، حيث تكون كل عقدة من العقد n متصلة (أو غير متصلة) بشكل مستقل باحتمالية p (أو 1 − p )، وله توزيع ثنائي الحد للدرجات k :

${\displaystyle P(k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}$

(أو توزيع بواسون في حالة n الكبيرة ، إذا كانت الدرجة المتوسطة${\displaystyle \langle k\rangle =p(n-1)}$(يُفترض أن تكون قيمة ثابتة). مع ذلك، فإن معظم الشبكات في العالم الحقيقي لها توزيعات درجات مختلفة تمامًا عن ذلك. فمعظمها منحرف بشدة نحو اليمين ، ما يعني أن غالبية العقد لها درجة منخفضة، بينما عدد قليل منها، يُعرف باسم "المحاور"، له درجة عالية. وقد قيل إن بعض الشبكات، ولا سيما الإنترنت والشبكة العنكبوتية العالمية وبعض الشبكات الاجتماعية، لها توزيعات درجات تتبع تقريبًا قانون القوة .${\displaystyle P(k)\sim k^{-\gamma }}$حيث γ ثابت. تُسمى هذه الشبكات بالشبكات غير المقياسية ، وقد حظيت باهتمام خاص لخصائصها البنيوية والديناميكية. ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}

يُعرَّف توزيع الدرجة الزائدة بأنه التوزيع الاحتمالي لعدد الحواف الأخرى المتصلة بعقدة ما، والتي يتم الوصول إليها عبر حافة معينة. ^{[ 5 ]} بعبارة أخرى، هو توزيع الروابط الصادرة من عقدة ما، والتي يتم الوصول إليها عبر رابط معين.

لنفترض أن شبكة ما لها توزيع درجات${\displaystyle P(k)}$باختيار عقدة واحدة (عشوائيًا أو لا) والانتقال إلى أحد جيرانها (بافتراض وجود جار واحد على الأقل)، فإن احتمال أن تحتوي تلك العقدة على${\displaystyle k}$الجيران لا يُعطون بواسطة${\displaystyle P(k)}$والسبب هو أنه كلما تم اختيار عقدة ما في شبكة غير متجانسة، فمن المرجح أن تصل إلى المحاور الرئيسية باتباع أحد جيرانها الحاليين. الاحتمال الحقيقي لامتلاك هذه العقد درجة معينة هو${\displaystyle k}$يكون${\displaystyle q(k)}$وهذا ما يُسمى بالدرجة الزائدة لتلك العقدة. في نموذج التكوين ، حيث تم تجاهل الارتباطات بين العقد، وافترض أن كل عقدة متصلة بأي عقدة أخرى في الشبكة بنفس الاحتمالية، يمكن إيجاد توزيع الدرجة الزائدة على النحو التالي: ^{[ 5 ]}

${\displaystyle q(k)={\frac {k+1}{\langle k\rangle }}P(k+1),}$

أين${\displaystyle {\langle k\rangle }}$يمثل متوسط ​​درجة العقدة في النموذج. ويترتب على ذلك أن متوسط ​​درجة جيران أي عقدة أكبر من متوسط ​​درجة تلك العقدة نفسها. في الشبكات الاجتماعية، يعني هذا أن أصدقاءك، في المتوسط، لديهم عدد أكبر من الأصدقاء مقارنةً بك. تُعرف هذه الظاهرة بمفارقة الصداقة . ويمكن إثبات أن الشبكة قد تحتوي على مكون عملاق إذا كان متوسط ​​درجة العقدة الزائدة فيها أكبر من واحد.

${\displaystyle \sum _{k}kq(k)>1\Rightarrow {\langle k^{2}\rangle }/{\langle k\rangle }-1>1\Rightarrow {\langle k^{2}\rangle }-2{\langle k\rangle }>0}$

ضع في اعتبارك أن المعادلتين الأخيرتين خاصتان بنموذج التكوين فقط ، ولاستنتاج توزيع الدرجة الزائدة لشبكة حقيقية، يجب علينا أيضًا إضافة ارتباطات الدرجة في الاعتبار. ^{[ 5 ]}

يمكن استخدام الدوال المولدة لحساب خصائص مختلفة للشبكات العشوائية. بمعرفة توزيع الدرجات وتوزيع الدرجات الزائدة لشبكة ما،${\displaystyle P(k)}$و${\displaystyle q(k)}$وبالتالي، من الممكن كتابة سلسلتي قوى بالشكلين التاليين:

${\displaystyle G_{0}(x)=\textstyle \sum _{k}\displaystyle P(k)x^{k}}$و${\displaystyle G_{1}(x)=\textstyle \sum _{k}\displaystyle q(k)x^{k}=\textstyle \sum _{k}\displaystyle {\frac {k}{\langle k\rangle }}P(k)x^{k-1}}$

${\displaystyle G_{1}(x)}$ويمكن الحصول عليها أيضًا من مشتقات${\displaystyle G_{0}(x)}$:

${\displaystyle G_{1}(x)={\frac {G'_{0}(x)}{G'_{0}(1)}}}$

إذا كنا نعرف الدالة المولدة لتوزيع احتمالي${\displaystyle P(k)}$عندها يمكننا استعادة قيم${\displaystyle P(k)}$عن طريق التمايز:

${\displaystyle P(k)={\frac {1}{k!}}{\operatorname {d} ^{k}\!G \over \operatorname {d} \!x^{k}}{\biggl \vert }_{x=0}}$

يمكن حساب بعض الخصائص، مثل العزوم، بسهولة من${\displaystyle G_{0}(x)}$ومشتقاته:

• ${\displaystyle {\langle k\rangle }=G'_{0}(1)}$
• ${\displaystyle {\langle k^{2}\rangle }=G''_{0}(1)+G'_{0}(1)}$

وبشكل عام: ^{[ 5 ]}

• ${\displaystyle {\langle k^{m}\rangle }={\Biggl [}{{\bigg (}\operatorname {x} {\operatorname {d} \! \over \operatorname {dx} \!}{\biggl )}^{m}}G_{0}(x){\Biggl ]}_{x=1}}$

بالنسبة للشبكات العشوائية الموزعة وفقًا لتوزيع بواسون ، مثل مخطط ER ،${\displaystyle G_{1}(x)=G_{0}(x)}$ولهذا السبب، فإن نظرية الشبكات العشوائية من هذا النوع بسيطة للغاية. يتم توليد التوزيعات الاحتمالية للجيران الأقرب الأول والثاني بواسطة الدوال.${\displaystyle G_{0}(x)}$و${\displaystyle G_{0}(G_{1}(x))}$وبالتالي، فإن توزيع${\displaystyle m}$يتم إنشاء الجيران رقم -th بواسطة:

${\displaystyle G_{0}{\bigl (}G_{1}(...G_{1}(x)...){\bigr )}}$، مع${\displaystyle m-1}$تكرارات الدالة${\displaystyle G_{1}}$^{[ 6 ]} يعمل على نفسه.

متوسط ​​عدد الجيران من الدرجة الأولى،${\displaystyle c_{1}}$، يكون${\displaystyle {\langle k\rangle }={dG_{0}(x) \over dx}|_{x=1}}$ويبلغ متوسط ​​عدد الجيران من الدرجة الثانية ما يلي:${\displaystyle c_{2}={\biggl [}{d \over dx}G_{0}{\big (}G_{1}(x){\big )}{\biggl ]}_{x=1}=G_{1}'(1)G'_{0}{\big (}G_{1}(1){\big )}=G_{1}'(1)G'_{0}(1)=G''_{0}(1)}$

في الشبكة الموجهة، يكون لكل عقدة درجة داخلية معينة${\displaystyle k_{in}}$وبعض الدرجات الخارجية${\displaystyle k_{out}}$وهي عدد الروابط التي دخلت وخرجت من تلك العقدة على التوالي. إذا${\displaystyle P(k_{in},k_{out})}$هي احتمالية أن يكون للعقدة المختارة عشوائياً درجة داخلية${\displaystyle k_{in}}$ودرجة خارجية${\displaystyle k_{out}}$عندئذٍ، يمكن كتابة الدالة المولدة المخصصة لتوزيع الاحتمال المشترك هذا باستخدام قيمتين.${\displaystyle x}$و${\displaystyle y}$مثل:

${\displaystyle {\mathcal {G}}(x,y)=\sum _{k_{in},k_{out}}\displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}}.}$

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

${\displaystyle \langle {k_{in}-k_{out}}\rangle =\sum _{k_{in},k_{out}}\displaystyle (k_{in}-k_{out})P({k_{in},k_{out}})=0}$،

مما يعني أن دالة التوليد يجب أن تحقق ما يلي:

${\displaystyle {\partial {\mathcal {G}} \over \partial x}\vert _{x,y=1}={\partial {\mathcal {G}} \over \partial y}\vert _{x,y=1}=c,}$

أين${\displaystyle c}$هو متوسط ​​درجة العقد (داخل وخارج) في الشبكة؛${\displaystyle \langle {k_{in}}\rangle =\langle {k_{out}}\rangle =c.}$

استخدام الدالة${\displaystyle {\mathcal {G}}(x,y)}$، يمكننا مرة أخرى إيجاد دالة التوليد لتوزيع درجة الدخول/الخروج وتوزيع درجة الدخول/الخروج الزائدة، كما كان من قبل.${\displaystyle G_{0}^{in}(x)}$يمكن تعريفها على أنها دوال توليد لعدد الروابط الواصلة إلى عقدة مختارة عشوائياً، و${\displaystyle G_{1}^{in}(x)}$يمكن تعريفها بأنها عدد الروابط الواصلة إلى عقدة يتم الوصول إليها باتباع رابط تم اختياره عشوائيًا. كما يمكننا تعريف الدوال المولدة.${\displaystyle G_{0}^{out}(y)}$و${\displaystyle G_{1}^{out}(y)}$بالنسبة للعدد الخارج من هذه العقدة: ^{[ 6 ]}

• ${\displaystyle G_{0}^{in}(x)={\mathcal {G}}(x,1)}$
• ${\displaystyle G_{1}^{in}(x)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial x}\vert _{y=1}}$
• ${\displaystyle G_{0}^{out}(y)={\mathcal {G}}(1,y)}$
• ${\displaystyle G_{1}^{out}(y)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial y}\vert _{x=1}}$

هنا، متوسط ​​عدد الجيران من الدرجة الأولى،${\displaystyle c}$أو كما سبق تقديمه على النحو التالي${\displaystyle c_{1}}$، يكون${\displaystyle {\partial {\mathcal {G}} \over \partial x}{\biggl \vert }_{x,y=1}={\partial {\mathcal {G}} \over \partial y}{\biggl \vert }_{x,y=1}}$ويُعطى متوسط ​​عدد الجيران من الدرجة الثانية الذين يمكن الوصول إليهم من عقدة مختارة عشوائياً بالصيغة التالية:${\displaystyle c_{2}=G_{1}'(1)G'_{0}(1)={\partial ^{2}{\mathcal {G}} \over \partial x\partial y}{\biggl \vert }_{x,y=1}}$وهذه هي أيضًا أعداد الجيران من الدرجة الأولى والثانية الذين يمكن الوصول منهم إلى عقدة عشوائية، نظرًا لأن هذه المعادلات متناظرة بشكل واضح في${\displaystyle x}$و${\displaystyle y}$[ ^{6 ]​}

في الشبكة الموقعة، يكون لكل عقدة درجة موجبة${\displaystyle k_{+}}$ودرجة سلبية${\displaystyle k_{-}}$وهي تمثل عدد الروابط الموجبة وعدد الروابط السالبة المتصلة بتلك العقدة على التوالي.${\displaystyle P(k_{+})}$و${\displaystyle P(k_{-})}$^{[ 7 ] [ 8 ]} تشير إلى توزيع الدرجة السالبة وتوزيع الدرجة الموجبة للشبكة الموقعة.

• نظرية الرسم البياني
• شبكة معقدة
• شبكة خالية من المقاييس
• رسم بياني عشوائي
• القطع الهيكلي

• ألبرت، ر.؛ باراباسي، أ.-ل. (2002). "الميكانيكا الإحصائية للشبكات المعقدة". مراجعات الفيزياء الحديثة . 74 (1): 47-97 . arXiv : cond-mat/0106096 . Bibcode : 2002RvMP...74...47A . doi : 10.1103/RevModPhys.74.47 . S2CID 60545 . 
• دوروغوفتسيف، س.؛ مينديز، ج. ف. ف. (2002). "تطور الشبكات". التقدم في الفيزياء . 51 (4): 1079-1187 . arXiv : cond-mat/0106144 . Bibcode : 2002AdPhy..51.1079D . doi : 10.1080/00018730110112519 . S2CID 429546 . 
• نيومان، إم إي جيه (2003). "بنية ووظيفة الشبكات المعقدة". مجلة SIAM Review ، 45 (2): 167-256 . arXiv : cond-mat/0303516 . Bibcode : 2003SIAMR..45..167N . doi : 10.1137/S003614450342480 . S2CID 221278130 .