رسم بياني عشوائي

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

يُحصل على الرسم البياني العشوائي بالبدء بمجموعة من n رأسًا معزولة وإضافة حواف متتالية بينها عشوائيًا. يهدف البحث في هذا المجال إلى تحديد المرحلة التي يُحتمل أن تظهر فيها خاصية معينة للرسم البياني. ^{[ 3 ]} تُنتج نماذج الرسوم البيانية العشوائية المختلفة توزيعات احتمالية مختلفة على الرسوم البيانية. النموذج الأكثر شيوعًا هو النموذج الذي اقترحه إدغار جيلبرت ، والذي يُطلق عليه غالبًا نموذج إردوش-ريني ، ويُرمز له بـ G ( n , p ). في هذا النموذج، تظهر كل حافة ممكنة بشكل مستقل باحتمالية 0 < p < 1. احتمال الحصول على أي رسم بياني عشوائي معين ذي m حافة هو${\displaystyle p^{m}(1-p)^{Nm}}$مع التدوين${\displaystyle N={\tbinom {n}{2}}}$[ ^{4 ]​}

يُخصص نموذجٌ وثيق الصلة، يُسمى أيضًا نموذج إردوش-ريني ويُرمز له بـ G ( n , M )، احتمالية متساوية لجميع الرسوم البيانية التي تحتوي على M حافة بالضبط. حيث 0 ≤ M ≤ N ، فإن G ( n , M ) يمتلك${\displaystyle {\tbinom {N}{M}}}$العناصر، وكل عنصر يحدث باحتمالية${\displaystyle 1/{\tbinom {N}{M}}}$[ ^{3 ]} يمكن اعتبار نموذج G ( n , M ) بمثابة لقطة في وقت محدد ( M ) لعملية الرسم ^{البياني} العشوائي${\displaystyle {\tilde {G}}_{n}}$، وهي عملية عشوائية تبدأ بـ n رأسًا ولا توجد حواف، وفي كل خطوة تضيف حافة جديدة يتم اختيارها بشكل موحد من مجموعة الحواف المفقودة.

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

بفرض أي n + m عنصرًا${\displaystyle a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V}$يوجد رأس c في V مجاور لكل من${\displaystyle a_{1},\ldots ,a_{n}}$ولا يقع بجوار أي من${\displaystyle b_{1},\ldots ,b_{m}}$.

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

نموذج آخر، يُعمم نموذج جيلبرت للرسم البياني العشوائي، هو نموذج الضرب النقطي العشوائي . يربط الرسم البياني العشوائي للضرب النقطي كل رأس بمتجه حقيقي . احتمال وجود حافة uv بين أي رأسين u و v هو دالة للضرب النقطي u • v لمتجهيهما.

تقوم مصفوفة احتمالية الشبكة بنمذجة الرسوم البيانية العشوائية من خلال احتمالات الحواف، والتي تمثل الاحتمالية${\displaystyle p_{i,j}}$أن حافة معينة${\displaystyle e_{i,j}}$يستمر هذا النموذج لفترة زمنية محددة. وهو قابل للتوسيع ليشمل الرسوم البيانية الموجهة وغير الموجهة، والموزونة وغير الموزونة، والثابتة والديناميكية.

بالنسبة لـ M ≃ pN ، حيث N هو الحد الأقصى لعدد الحواف الممكنة، فإن النموذجين الأكثر استخدامًا، G ( n , M ) و G ( n , p )، قابلان للتبادل تقريبًا. ^{[ 5 ]}

تشكل الرسوم البيانية المنتظمة العشوائية حالة خاصة، بخصائص قد تختلف عن الرسوم البيانية العشوائية بشكل عام.

بمجرد أن نحصل على نموذج للرسوم البيانية العشوائية، تصبح كل دالة على هذه الرسوم البيانية متغيرًا عشوائيًا . تهدف دراسة هذا النموذج إلى تحديد ما إذا كانت خاصية معينة قد تحدث، أو على الأقل تقدير احتمالية حدوثها. ^{[ 4 ]}

يشير مصطلح "تقريبًا كل" في سياق الرسوم البيانية العشوائية إلى سلسلة من المساحات والاحتمالات، بحيث تؤول احتمالات الخطأ إلى الصفر. ^{[ 4 ]}

تدرس نظرية الرسوم البيانية العشوائية الخصائص النموذجية للرسوم البيانية العشوائية، وهي الخصائص التي تتحقق باحتمالية عالية للرسوم البيانية المسحوبة من توزيع معين. على سبيل المثال، قد نطلب قيمة معينة لـ${\displaystyle n}$و${\displaystyle p}$ما هو احتمال ذلك؟${\displaystyle G(n,p)}$وهي متصلة . عند دراسة مثل هذه المسائل، غالبًا ما يركز الباحثون على السلوك التقاربي للرسوم البيانية العشوائية - القيم التي تتقارب إليها الاحتمالات المختلفة عندما${\displaystyle n}$تنمو بشكل كبير جدًا. تُحدد نظرية الترشيح مدى ترابط الرسوم البيانية العشوائية، وخاصة تلك التي لا نهائية الحجم.

يرتبط الترشيح بمتانة الرسم البياني (الذي يُسمى أيضًا الشبكة). بالنظر إلى رسم بياني عشوائي من${\displaystyle n}$العقد ودرجة متوسطة${\displaystyle \langle k\rangle }$ثم نقوم بإزالة جزء عشوائياً${\displaystyle 1-p}$من العقد، ولا تترك سوى جزء صغير${\displaystyle p}$توجد عتبة ترشيح حرجة${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$يصبح النظام مجزأً أسفل هذا المستوى، بينما يصبح مجزأً أعلاه.${\displaystyle p_{c}}$يوجد مكون متصل ضخم. ^{[ 1 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]}

يشير الترشيح الموضعي إلى إزالة عقدة من جيرانها، وجيرانها الأقرب التاليين، وما إلى ذلك، حتى يصبح جزء منها${\displaystyle 1-p}$تمت إزالة عدد من العقد من الشبكة. وقد تبين أنه بالنسبة للرسم البياني العشوائي ذي توزيع بواسون للدرجات${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$تمامًا كما هو الحال بالنسبة للإزالة العشوائية.

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

في الرسوم البيانية المنتظمة العشوائية ،${\displaystyle G(n,r-reg)}$هي مجموعة${\displaystyle r}$- رسوم بيانية منتظمة مع${\displaystyle r=r(n)}$بحيث${\displaystyle n}$و${\displaystyle m}$هي الأعداد الطبيعية،${\displaystyle 3\leq r<n}$، و${\displaystyle rn=2m}$هو زوجي. ^{[ 3 ]}

تسلسل درجات الرسم البياني${\displaystyle G}$في${\displaystyle G^{n}}$يعتمد فقط على عدد الحواف في المجموعات ^{[ 3 ]}

${\displaystyle V_{n}^{(2)}=\left\{ij\$ :\ 1\leq j\leq n,i\neq j\right\}\subset V^{(2)},\qquad i=1,\cdots ,n.}

إذا كانت هناك حواف،${\displaystyle M}$في رسم بياني عشوائي،${\displaystyle G_{M}}$كبيرة بما يكفي لضمان أن كل${\displaystyle G_{M}}$إذا كان الحد الأدنى للدرجة هو 1 على الأقل، فعندئذٍ يكون كل شيء تقريبًا${\displaystyle G_{M}}$متصل، وإذا${\displaystyle n}$متساوٍ، تقريبًا كل${\displaystyle G_{M}}$يوجد تطابق تام. على وجه الخصوص، في اللحظة التي يختفي فيها آخر رأس معزول في كل رسم بياني عشوائي تقريبًا، يصبح الرسم البياني متصلًا. ^{[ 3 ]}

تقريبًا كل عملية رسم بياني على عدد زوجي من الرؤوس مع حافة ترفع الحد الأدنى للدرجة إلى 1 أو رسم بياني عشوائي بأكثر بقليل من${\displaystyle {\tfrac {n}{4}}\log(n)}$الحواف وباحتمالية قريبة من 1 تضمن أن الرسم البياني يحتوي على تطابق كامل، باستثناء رأس واحد على الأكثر.

لبعض الثوابت${\displaystyle c}$، تقريبًا كل رسم بياني مُصنَّف مع${\displaystyle n}$الرؤوس وعلى الأقل${\displaystyle cn\log(n)}$الحواف هي هاميلتونية . مع اقتراب الاحتمالية من 1، فإن الحافة المحددة التي تزيد الحد الأدنى للدرجة إلى 2 تجعل الرسم البياني هاميلتونيًا.

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

بفرض وجود رسم بياني عشوائي G من الرتبة n ، حيث V ( G ) = {1, ..., n }، وباستخدام خوارزمية جشعة تعتمد على عدد الألوان، يمكن تلوين الرؤوس بالألوان 1، 2، ... (يُلوّن الرأس 1 باللون 1، ويُلوّن الرأس 2 باللون 1 إذا لم يكن مجاورًا للرأس 1، وإلا يُلوّن باللون 2، وهكذا). ^{[ 3 ]} لا يزال عدد التلوينات الصحيحة للرسوم البيانية العشوائية، عند استخدام عدد q من الألوان، والذي يُسمى متعدد الحدود اللوني ، غير معروف حتى الآن. وقد دُرست تجريبيًا عملية قياس أصفار متعدد الحدود اللوني للرسوم البيانية العشوائية ذات المعاملات n وعدد الحواف m أو احتمالية الاتصال p، باستخدام خوارزمية تعتمد على مطابقة الأنماط الرمزية. ^{[ 10 ]}

الشجرة العشوائية هي شجرة أو تفرع شجري يتشكل بفعل عملية عشوائية . في نطاق واسع من الرسوم البيانية العشوائية من الرتبة n والحجم M ( n )، يكون توزيع عدد مكونات الشجرة من الرتبة k مقاربًا لتوزيع بواسون . تشمل أنواع الأشجار العشوائية: الشجرة الممتدة المنتظمة ، والشجرة الممتدة الدنيا العشوائية ، والشجرة الثنائية العشوائية ، وشجرة treap ، والشجرة العشوائية سريعة الاستكشاف ، وشجرة براون ، والغابة العشوائية .

لنفترض نموذج رسم بياني عشوائي معين معرف على فضاء الاحتمالات${\displaystyle (\Omega ,{\mathcal {F}},P)}$ودع${\displaystyle {\mathcal {P}}(G):\Omega \rightarrow R^{m}}$لتكن دالة حقيقية القيمة تُسند إلى كل رسم بياني في${\displaystyle \Omega }$متجه من m خاصية. لـ ثابت${\displaystyle \mathbf {p} \in R^{m}}$الرسوم البيانية العشوائية الشرطية هي نماذج يكون فيها مقياس الاحتمال${\displaystyle P}$يُعيّن احتمالًا صفريًا لجميع الرسوم البيانية التي${\displaystyle {\mathcal {P}}(G)\neq \mathbf {p} }$.

تُعدّ الرسوم البيانية العشوائية المتجانسة المشروطة حالات خاصة ، حيث${\displaystyle P}$تُخصص هذه الطريقة احتمالية متساوية لجميع الرسوم البيانية التي لها خصائص محددة. ويمكن اعتبارها تعميمًا لنموذج إردوش-ريني G ( n , M )، حيث لا تكون معلومات التكييف بالضرورة عدد الحواف M ، بل أي خاصية أخرى عشوائية للرسم البياني.${\displaystyle {\mathcal {P}}(G)}$في هذه الحالة، تتوفر نتائج تحليلية قليلة جدًا، ويلزم إجراء محاكاة للحصول على التوزيعات التجريبية للخصائص المتوسطة.

كان أول استخدام لنموذج الرسم البياني العشوائي من قِبل هيلين هول جينينغز وجاكوب مورينو عام 1938، حيث تمّ استخدام "مخطط اجتماعي عشوائي" (نموذج إردوش-ريني الموجّه) في دراسة مقارنة نسبة الروابط المتبادلة في بيانات شبكتهم مع النموذج العشوائي. ^{[ 11 ]} كما استُخدم هذا النموذج، تحت مسمى "الشبكة العشوائية"، من قِبل راي سولومونوف وأناتول رابوبورت عام 1951، باستخدام نموذج من الرسوم البيانية الموجّهة ذات درجة خروج ثابتة وروابط مختارة عشوائيًا مع رؤوس أخرى. ^{[ 12 ]}

تم تعريف نموذج إردوس -ريني للرسوم البيانية العشوائية لأول مرة من قبل بول إردوس وألفريد ريني في ورقتهما البحثية عام 1959 "حول الرسوم البيانية العشوائية" ^{[ 8 ]} وبشكل مستقل من قبل جيلبرت في ورقته "الرسوم البيانية العشوائية". ^{[ 6 ]}

• تكثيف بوز-أينشتاين: نهج نظرية الشبكات - نموذج في علم الشبكات. صفحات تعرض أوصافًا موجزة لأهداف إعادة التوجيه. 
• طريقة التجويف – طريقة رياضية في الفيزياء الإحصائية 
• الشبكات المعقدة – شبكة ذات خصائص طوبولوجية غير بديهية. صفحات تعرض أوصافًا موجزة لأهداف إعادة التوجيه. 
• التطور ثنائي المرحلة – عملية تدفع التنظيم الذاتي داخل الأنظمة التكيفية المعقدة 
• نموذج Erdős – Rényi – نموذجان مرتبطان ارتباطًا وثيقًا بإنشاء رسوم بيانية عشوائية 
• نموذج الرسم البياني العشوائي الأسي – نماذج إحصائية لتحليل الشبكات. صفحات تعرض أوصافًا مختصرة لأهداف إعادة التوجيه. 
• نظرية الرسوم البيانية – مجال من مجالات الرياضيات المتقطعة 
• الشبكات المترابطة – مجال فرعي من علم الشبكات 
• علم الشبكات – مجال أكاديمي 
• الترشيح – ترشيح السوائل عبر المواد المسامية 
• نظرية الترشيح – نظرية رياضية حول سلوك المجموعات المتصلة في رسم بياني عشوائي 
• نظرية الرسم البياني العشوائي للتجلط – النظرية الرياضية لعمليات سول-جل 
• الرسم البياني المنتظم – الرسم البياني الذي يكون فيه لكل رأس نفس عدد الجيران 
• شبكة لا تعتمد على المقياس – شبكة يتبع توزيع درجاتها قانون القوة. صفحات تعرض أوصافًا مختصرة لأهداف إعادة التوجيه. 
• الاستجابة شبه الخطية – امتداد لنظرية الاستجابة الخطية في الأنظمة الميزوسكوبية 
• نموذج الكتلة العشوائية – مفهوم في علم الشبكات 
• معيار لانشينيتي-فورتوناتو-راديتشي – صفحات الخوارزمية التي تعرض أوصافًا مختصرة بدون مسافات