گراف تصادفی

در ریاضیات، گراف تصادفی اصطلاحی کلی است که به احتمال پراکندگی روی گراف‌ها اطلاق می‌گردد و نقطه برخورد تئوری گراف و تئوری احتمالات است. از جنبه ریاضیات، گراف تصادفی برای پاسخ به پرسش‌هایی در مورد خواص گراف‌ها بکار گرفته می‌شود، اما برنامه‌های کاربردی آن در تمام حوزه‌هایی که در آن شبکه‌های پیچیده نیاز به مدل‌سازی دارند وجود دارد. در مبحث ریاضی، گراف تصادفی تقریباً به مدل گراف تصادفی Erdös-Renyi منحصر است. در زمینه‌های دیگر، هر مدل گراف دیگر ممکن است به یک گراف تصادفی نسبت داده شود.

مفهوم گراف تصادفی

فرض کنید n نقطه در فضا و همچنین سکه‌ای اریب با احتمال رو آمدن p در اختیار داریم. با پرتاب سکه و با احتمال رو آمدن متناظر p، دو نقطه انتخابی دلخواه را به هم وصل می‌کنیم یعنی یالی از این رئوس می‌گذرانیم. قابل ذکر است که رئوس شماره‌دار هستند. برای روشن شدن مطلب یک حالت خاص n و p را بررسی می‌کنیم.
مثال: در حالت n = ۳ و فرض $p={\frac {4}{5}}$، ${\frac {1}{125}}$ احتمال دارد سه نقطه ایزوله تشکیل شود؛ یعنی هیچ یالی بین سه راس تشکیل نشود. در این حالت هر یک از سه یال ممکن، یعنی همان اضلاع مثلث با احتمال ${\frac {1}{5}}$ ظاهر نمی‌شوند. از این رو احتمال اینکه هیچ‌یک از اضلاع در گراف حضور نداشته باشند، برابر با ${\frac {1}{5}}*{\frac {1}{5}}*{\frac {1}{5}}={\frac {1}{125}}$ می‌باشد. با احتمال ${\binom {3}{1}}*{\frac {4}{5}}*{\frac {1}{5}}*{\frac {1}{5}}={\frac {12}{125}}$، تنها یک یال ایجاد می‌شود؛ یعنی سه گراف که در آن رأس ۱ یا ۲ یا ۳ تنها بوده و یال، بین دو رأس دیگر ایجاد می‌شود؛ به این معنی که در شماره رأس‌ها تفاوت دارند. همچنین به همین صورت با احتمال ${\binom {3}{2}}*{\frac {4}{5}}*{\frac {4}{5}}*{\frac {1}{5}}={\frac {48}{125}}$ دو یال ایجاد می‌گردد و در آخر با احتمال${\frac {4}{5}}*{\frac {4}{5}}*{\frac {4}{5}}={\frac {64}{125}}$ یک گراف کامل از مرتبه ۳ خواهیم داشت.

مدل‌هایی از گراف تصادفی

یک گراف تصادفی از یکسری رئوس منفرد به علاوه یال‌های متوالی تصادفی میان آن‌ها بدست می‌آید. هدف مطالعه در این زمینه این است که تعیین کنیم احتمال رخ دادن خاصیت بخصوصی از گراف در چه مرحله‌ای است. چندین نوع گراف از گراف تصادفی وجود دارد اما متداول‌ترین نوع گراف، گرافی است که توسط Edgar Gilbert ارائه گردیده و مثالش در بالا ذکر شده‌است.

گراف تصادفی G(n,P)

در این مدل رئوس گراف ثابت بوده و تصادفی بودن گراف به واسطه وجود پارامتر P بوده که در بازه [۰٬۱] تغییر می‌کند. در این مدل یال‌ها به صورت تصادفی و مستقل از هم انتخاب می‌شوند. احتمال به دست آوردن گراف تصادفی بخصوصی با m یال، با توجه به اینکه $N={\binom {n}{2}}$، $P^{m}(1-P)^{N-m}$ می‌باشد.

گراف تصادفی G(n,M)

مدل G(n,M) نشان‌دهنده گراف تصادفی با n رأس و M یال ثابت است و تصادفی بودن گراف به واسطه جایگشت یال‌ها می‌باشد که در بین رئوس شماره دار تغییر می‌کند. اگر N ≥ M ≥ ۰ و $N={\binom {n}{2}}$ باشد، گراف تصادفی G(n,M) دارای ${\binom {N}{M}}$ عضو است و هر عضو با احتمال ${\frac {1}{\binom {N}{M}}}$ در مدل حضور دارد. این مدل را می‌توان به عنوان یک عضو از مجموعه گراف‌های G(n,M)، با M یال مشخص، در نظر گرفت طوری‌که ابتدا با n رأس و بدون یال شروع شده و در هر مرحله یال جدیدی اضافه کند تا به N یال برسد. اجتماع تمام این گراف‌ها به صورت $\bigcup _{M=0}^{N}G(n,M)$ نشان داده می‌شود.

گراف تصادفی نامحدود

اگر بی‌نهایت رأس داشته باشیم و هر یال به‌طور مستقل با احتمال p که در بازه [۰٬۱] تغییر می‌کند، به وجود بیاید، گرافی خواهیم داشت که گراف تصادفی نامحدود نامیده می‌شود؛ مگر در مواردی جزئی که P صفر یا یک است.

منابع

• نشریه دانشجویی آمار (ندا)، مفهوم گراف تصادفی و مدل‌هایی از آن