گراف تصادفی

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

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

فرض کنید n نقطه در فضا و همچنین سکه‌ای اریب با احتمال رو آمدن p در اختیار داریم. با پرتاب سکه و با احتمال رو آمدن متناظر p، دو نقطه انتخابی دلخواه را به هم وصل می‌کنیم یعنی یالی از این رئوس می‌گذرانیم. قابل ذکر است که رئوس شماره‌دار هستند. برای روشن شدن مطلب یک حالت خاص n و p را بررسی می‌کنیم.[2]
مثال: در حالت 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 ارائه گردیده و مثالش در بالا ذکر شده‌است.[1]

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

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

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

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

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

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

منابع

، ویکی‌پدیا انگلیسیen:Random graph
، نشریه دانشجویی

ویکی‌پدیا انگلیسی، Random graph
نشریه دانشجویی آمار (ندا)، مفهوم گراف تصادفی و مدل‌هایی از آن

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[wiki-1] ، ویکی‌پدیا انگلیسیen:Random graph

[nashriye-2] ، نشریه دانشجویی

فرایندهای تصادفی
فرایند تصادفی	فرایند برنولی فرایند شاخه‌ای فرایند رستوران چینی فرایند گالتون-واتسون متغیرهای تصادفی مستقل با توزیع یکسان زنجیره مارکوف فرایند مورن ولگشت Loop-erased ولگشت خودپرهیز (قدم زدن بدون قطع کردن خود)
Continuous time	Bessel process Birth–death process فرایند وینر Bridge Excursion Fractional Geometric Meander فرایند کوشی Contact process گام-تصادفی زمان-پیوسته Cox process Diffusion process Empirical process فرایند فلر فرایند فلمینگ-ویوت Gamma process Hunt process Interacting particle systems Itô diffusion فرایند ایتو Jump diffusion Jump process فرایند لوی Local time Markov additive process McKean–Vlasov process فرایند اورنستین-یولنبک فرایند پواسون Compound فرایند پواسون فرایند پواسون تحول شرام و لونر Semimartingale Sigma-martingale Stable process Superprocess Telegraph process Variance gamma process فرایند وینر Wiener sausage
Both	فرایند شاخه‌ای Galves–Löcherbach model فرایند گاوسی مدل پنهان مارکف زنجیره مارکوف مارتینگیل Differences Local مارتینگیل مارتینگیل Random dynamical system Regenerative process نظریه تجدید Stochastic chains with memory of variable length نویز سفید
Fields and other	فرایند دیریکله Gaussian random field Gibbs measure شبکه هاپفیلد مدل آیزینگ Potts model شبکه بولی میدان تصادفی مارکفی نظریه تراوش فرایند پیتمن-یور فرایند نقطه ای Cox فرایند پواسون میدان تصادفی گراف تصادفی
سری زمانی	واریانس ناهمسانی شرطی اتورگرسیو میانگین متحرک خودهمبسته یکپارچه مدل خودهمبسته مدل خودهمبسته میانگین متحرک واریانس ناهمسانی شرطی اتورگرسیو مدل میانگین متحرک
Financial models	مدل بلک-درمن-توی Black–Karasinski مدل بلک-شولز مدل چن Constant elasticity of variance (CEV) مدل کاکس-اینگرسول-راس Garman–Kohlhagen Heath–Jarrow–Morton (HJM) Heston Ho–Lee Hull–White LIBOR market Rendleman–Bartter SABR volatility مدل واسیچک Wilkie
بیمسنجی	Bühlmann Cramér–Lundberg Risk process Sparre–Anderson
نظریه صفs	Bulk Fluid Generalized queueing network M/G/1 صف M/M/1 M/M/c
Properties	تابع Càdlàg Continuous Continuous paths ارگادیسیتی متغیرهای تصادفی تعویض پذیر Feller-continuous فرآیندهای تصادفی گاوسی-مارکوف خاصیت مارکف Mixing Piecewise deterministic Predictable Progressively measurable Self-similar فرایند مانا Time-reversible
Limit theorems	قضیه حد مرکزی Donsker's theorem Doob's martingale convergence theorems نظریه ارگودیک Fisher–Tippett–Gnedenko theorem Large deviation principle قانون اعداد بزرگ قانون لگاریتم‌های تکراری Maximal ergodic theorem Sanov's theorem
Inequalities	Burkholder–Davis–Gundy Doob's martingale Kunita–Watanabe
Tools	Cameron–Martin formula همگرایی متغیرهای تصادفی Doléans-Dade exponential Doob decomposition theorem Doob–Meyer decomposition theorem Doob's optional stopping theorem Dynkin's formula Feynman–Kac formula Filtration Girsanov theorem Infinitesimal generator Itô integral Itô's lemma Kolmogorov continuity theorem Kolmogorov extension theorem Lévy–Prokhorov metric Malliavin calculus Martingale representation theorem Optional stopping theorem Prokhorov's theorem Quadratic variation Reflection principle Skorokhod integral Skorokhod's representation theorem تابع Càdlàg Snell envelope معادله دیفرانسیل تصادفی Tanaka زمان توقف Stratonovich integral Uniform integrability Usual hypotheses Wiener space Classical Abstract
Disciplines	بیمسنجی اقتصادسنجی نظریه ارگودیک نظریه مقدار حدی قضیه انحرافات بزرگ مالیه ریاضیاتی آمار ریاضی نظریه احتمالات نظریه صف نظریه تجدید Ruin theory آمار حسابان تصادفی سری زمانی یادگیری ماشین
List of topics