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

جزء من سلسلة مقالات حول :
علم الشبكات :
نظرية الشبكات
البيان
تعقيد الشبكة
شبكات العالم الصغير
الشبكات غير المحدودة
بينة المجتمع
نظرية التخلل
الشبكات المتطورة
التحكم في الشبكة
رسم البيان
رأس المال الاجتماعي
تحليل الرابط
التحسين المشترك
التبادل
الإغلاق الثلاثي
محبة الذات
العلاقة المتعدية
المُرفقات التفضيليّة
نظرية التوازن
تأثير الشبكة
تأثير إجتماعي :
أنماط الشبكات
حاسوب
اتصالات
نقل
اجتماعيّة
علميّة
بيولوجيّة
عصبونيّة
مستقلة
دلاليّة
جيو متريّة
مترابطة
شبكات التدفق :
نظرية البيان
الميزات
كليك (Clique)
المكونات
قطع
مسار
بنية البيانات
وصلة
حلقة
جار
مسار
رأس
قائمة المجاورة / مصفوفة المجاورة
قائمة الإصابة / مصفوفة الإصابة
الأنماط
ثنائي
كامل
مُوجّه
هجين (Hypergraph)
متعدد (Multigraph)
عشوائي
موزون (Weighted) :
الأوزانالخوارزميات
المركزية
درجة العقد
المركزية البينيّة
خوازمية بيج رانك
الزخارف
معامل التجميع
توزع الدرجة
الازدواجية (Assortativity)
المسافة
النمطيّة
الكفاءة :
النماذج
الطوبولوجيا
النموذج العشوائي
نموذج إردوس-ريني
نموذج بارباسي-إلبرت
نموذج واتس-ستروغيتز
نموذج البيان العشوائي الأسي (ERGM)
البيان الهندسي القطعي (HGN)
نموذج الشبكة الهرمية
نموذج الكتلة العشوائية
الآليّة
الشبكات البُوليانيّة
نموذج العميل
النماذج المُجزّئة في علم الأوبئة :
قوائمتصانيف
قائمة
برمجيات
قائمة
تصنيف:نظرية الشبكات
تصنيف:نظرية المخططات :
عنت :
الرسم البياني العشوائي (بالإنجليزية: Random Graph)‏ في الرياضيات، هو الرسم البياني الذي يَنشأ عن طريق عملية عشوائية. ونظرية الرسم البيانى العشوائي تعتبر نقطة التقاطع بين نظريتي الاحتمال والرسم البياني، وتقوم بدراسة خصائص الرسوم البيانية العشوائية المتطابقة.

## نماذج الرسم البياني العشوائي

و يتم الحصول على رسم بياني عشوائي من خلال البدء بعدد ن من القمم ومن ثم ايصال بعض الخطوط بينها على نحو عشوائي. وتنتج نماذج الرسوم البيانية العشوائية المختلفة توزيعات احتمالية مختلفة على الرسوم البيانية. ويعتبر النموذج الأكثر دراسة هو النموذج إيردوس - Rényi، حيث يمثل ب مجموعة (ن، ع)، حيث كل خط واصل بين نقطتين يكون له احتمال ع. مستقل عن غيره.وهناك نموذج شديد الصلة ب هذا النموذج، يمثل بالمجموعة (ن، م)، حيث ياخد كل رسم بياني قيمة احتمال متساوى مع بقية الرسوم البيانية الأخرى مع عدد ص من الخطوط.والنموذج الأخير يمكن أن ينظر إليه باعتباره لقطة في وقت معين (م) من العملية العشوائية للرسم البياني، التي تكون عملية عشوائية تبدأ مع النقاط ن وليس لها خطوط واصلة ويضيف في كل خطوة واحدة خط جديد يتم اختياره بشكل موحد من مجموعة الخطوط المفقودة.
و لو بدانا مع مجموعة لانهائية من القمم، ومرة أخرى يكون كل خط له احتمال ع منفصل عن بقية الخطوط، فسوف نحصل على العنصر ل والذي يسمى الرسم البياني العشوائي اللا منتهى.إلا في الحالات النادرة عندما يكون ع 0 أو 1 ،و هنا من المؤكد أن يكون العنصر ل له الخواص التالية :
    لأي $n+m$ العناصر n+m a_1,\ldots, a_n,b_1,\ldots, b_m \in V، هناك قمة$c\in V$ تكون متاخمة لكل من وليس متاخمة إلى أي من $b_{1},\ldots ,b_{m}$
كما تبين أنه إذا كانت مجموعة القمم قابلة للعد إذا هناك، طبقا إلى التماثل، فقط رسم بياني واحد تنطبق عليه هذه الخاصية، ويسمى عندها باسم الرسم البياني رادو. وبالتالي أي رسم بياني عشوائي غير قابل للعد يكاد يكون من المؤكد أنه رسم بياني رادو، لهذا السبب بمكن ان يسمى أحيانا ببساطة الرسم البياني العشوائي.
نموذج آخر، والذي يعمم الرسوم البيانية إيردوس - Rényi، هو نموذج random dot-product. والرسم البياني random dot-product يربط متجه حقيقي. مع كل قمة احتمال وجود خط واصل uv بين أي من القمم u و v هو دالة في u.v بالنسبة للقمم الخاصة بهم.
الرسوم البيانية العشوائية لنماذج مصفوفة شبكة الاحتمالات عبر خواص الخطوط الواصلة بين القمم، والتي تمثل احتمال $p_{i,j}$ أن يكون الخط $e_{i,j}$ موجودا لفترة زمنية محددة. هذا النموذج قابل للتوسع للرسوم البيانية الموجهة وغير الموجهة ؛ المرجحة وغير المرجحة ؛ والساكنة أو المتحركة.
الرسم البياني العشوائي العادييشكل حالة خاصة، مع الخصائص التي قد تختلف عن الرسوم البيانية العشوائية بصفة عامة.

## خصائص الرسوم البيانية العشوائية

نظرية الرسوم البيانية العشوائية تدرس الخصائص النموذجية لللرسوم البيانية بشكل عشوائي، وتلك التي تعقد مع احتمال كبير لاستخلاصها من الرسوم البيانية لتوزيع معين. على سبيل المثال، قد نسأل عن قيمة معينة ل n و p ما هو احتمال أن تكون المجموعة (n، p) متصلة. في دراسة مثل هذه المسائل، يركزالباحثين في كثير من الأحيان على السلوك المقارب للرسوم البيانية العشوائية، والقيم التي تتلاقى لمختلف الاحتمالات وn تتزايد بسرعة كبيرة جدا. نظرية الطبقاتتمثل الترابط بين الرسوم البيانية العشوائية، ولا سيما الكبيرة منها بلا حدود.
(دوال العتبة، وتطور مجموعة ~)
الرسوم البيانية العشوائية تستخدم على نطاق واسع في الأسلوب احتمالي، حيث واحدة تحاول إثبات وجود الرسوم البيانية مع خصائص معينة. وجود خاصية في الرسم البياني العشوائي يمكن أن يعني في كثير من الأحيان، عبر الشهير Szemerédi فرضية انتظامها، ووجود تلك الخصائص تقريبا على جميع الرسوم البيانية.

## تاريخ الرسوم البيانية العشوائية

الرسوم البيانية العشوائية حددت لأول مرة من قبل بول إيردوس وألفريد Rényi في 1959 على الورق «في الرسوم البيانية العشوائية» في سنة النشر. الرياضيات. دبريسين 6، ص 290-297.