مدل اردوش-رنیی

در نظریه گراف مدل اردوش-رنیی شامل دو مدل نزدیک به‌ هم برای ساختن گراف تصادفی است. از آنجا که برای اولین بار دو ریاضیدان پال اردوش و آلفرد رنیی یکی از این دو مدل را در سال ۱۹۵۹ معرفی کردند، این مدل به نام آن‌ها نامگذاری شده‌است.^[۱] ادگار گیلبرت مدل دیگر را همزمان و به‌طور مستقل از اردوش و رنیی معرفی کرد.^[۲] در مدل اردوش و رنیی، همه گراف‌ها با تعداد راس و یال ثابت و مشخص احتمال برابر دارند؛ در مدلی که توسط گیلبرت معرفی شد هر یال با احتمال ثابت و مشخصی وجود دارد یا ندارد که این احتمال مستقل از احتمال وجود سایر یال‌هاست.

تعریف ویرایش

دو مدل نزدیک به هم برای گراف تصادفی اردوش-رنیی وجود دارد.

گراف تولید شده توسط مدل دو جمله‌ای اردیش رینی (p = 0.01)

در مدل (G(n, M یک گراف به صورت یکنواخت و تصادفی از مجموعه‌ای از گراف‌ها با n گره و M یال انتخاب می‌شود. برای مثال در (3, 2)G هر کدام از سه گراف ممکن با 3 راس و 2 یال با احتمال 1/3 انتخاب می‌شوند.
در مدل (G(n, p گراف با وصل کردن گره‌ها به صورت تصادفی به وجود می‌آید. هر یال با احتمال p در گراف خواهد بود که این احتمال مستقل از احتمال وجود سایر یال‌هاست. تمام گراف‌ها با n گره و M یال احتمال برابر خواهند داشت این احتمال برابر است با:

p^{M}(1-p)^{{n \choose 2}-M}.

پارامتر p در این مدل می تواند به عنوان یک تابع وزن‌دهنده شناخته شود؛ همانطور که p از 0 به 1 افزایش می‌یابد، مدل به سمت گراف‌هایی با یال‌های بیشتر می‌رود و احتمال رخ دادن گراف‌ها با یال کم کمتر و کمتر می‌شود. مورد خاص p = 0.5 حالتی را نمایش می‌دهد که در آن تمام

2^{\binom {n}{2}}

گراف با n راس با احتمال برابر انتخاب می‌شوند.

رفتار گراف‌های تصادفی اغلب هنگامی مورد مطالعه قرار می‌گیرد که در آن n تعداد رئوس به بی نهایت میل کند. p و M در این مورد می‌توانند ثابت یا به صورت تابعی از n باشند. برای مثال عبارت:

تقریبا در هر گراف در (G(n, 2ln(n)/n همبند است.

به این معنا است که:

هر چه n به بی نهایت میل کند، احتمال این‌که یک گراف با n راس و 2ln(n)/n یال همبند باشد، به 1 میل می‌کند.

ویژگی‌های (G(n, p ویرایش

با توجه به تعاریف بالا یک گراف (G(n, p به‌طور متوسط ${\tbinom {n}{2}}p$ یال دارد. توزیع درجه هر راس از نوع توزیع دوجمله‌ای است:^[۳]

P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},

که در آن n تعداد رئوس در گراف است. از آن‌جایی که:

P(\deg(v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!}}\quad {\text{ as }}n\to \infty {\text{ and }}np={\text{constant}},

این توزیع برای nهای بزرگ و np = عدد ثابت پواسون است.

در سال 1960 اردوش و رنیی در مقاله‌ای که منتشر کردند^[۴] رفتار (G(n, p را به‌طور دقیق برای مقادیر مختلف p توصیف کردند. از جملهٔ این نتایج:

اگر np < 1 آنگاه یک گراف در (G(n, p با تقریب خوبی هیچ جز همبندی با اندازه بزرگتر از ((O(log(n نخواهد داشت.
اگر np = 1 آنگاه یک گراف در (G(n, p با تقریب خوبی مولفه همبندی با اندازه‌ای در حد n^2/3خواهد داشت.
اگر np → c > 1 که در آن c ثابت است، آنگاه یک گراف در (G(n, p با تقریب خوبی بزرگ‌ترین مؤلفه‌ای شامل کسر مثبتی از راس‌ها خواهد بود. هیچ جزء بیش از ((O(log(n راس نخواهد داشت.
اگر $p<{\tfrac {(1-\varepsilon )\ln n}{n}}$ شامل راس جدا(ایزوله) و در نتیجه غیرهمبند خواهد بود.
اگر $p>{\tfrac {(1+\varepsilon )\ln n}{n}}$ گراف با تقریب خوبی همبند خواهد بود.

در نتیجه ${\tfrac {\ln n}{n}}$ یک تابع مشخص‌کننده حد همبندی گراف (G(n, p است.

ویژگی‌های بیشتر از این گراف هنگامی که n به بی نهایت میل می‌کند قابل توضیح است. برای مثال (k(n وجود دارد (تقریبا برابر (2log₂(n) به طوری که بزرگترین گروهک (زیر گراف کامل) در (G(n, 0.5 با تقریب خوبی اندازه‌ای برابر با (k(n و یا k(n) + 1 خواهد داشت.^[۵]

بنابراین با وجود اینکه پیدا کردن اندازه بزرگترین زیر گراف کامل در یک گراف ان‌پی کامل است, اندازه بزرگترین زیر گراف کامل در یک گراف "معمولی" (بر اساس این مدل) به خوبی قابل درک است.

هشدارها ویرایش

هر دو فرض مهم مدل (G(n, p (که یال‌ها مستقل هستند و احتمال وجود هر یال مساوی است) ممکن است برای مدل سازی پدیده‌های زندگی واقعی نامناسب باشند. به طور خاص توزیع درجه گراف اردوش-رنیی دم‌سنگین ندارد در حالی که این باور وجود دارد که بسیاری از شبکه‌های واقعی دم‌سنگین هستند.

اخیرا مدلی برای شبکه اردوش رنیی قابل تعامل توسط Buldyrev et al توسعه داده شده‌است.^[۶]

تاریخچه ویرایش

مدل (G(n, p برای اولین بار در سال ۱۹۵۹ توسط ادگار گیلبرت در مقاله‌ای که آستانه همبند بودن را بررسی می‌کرد، معرفی شد.^[۷] اردوش و رنیی در سال ۱۹۵۹ مدل (G(n, M را در مقاله خود معرفی کردند. و همانند گیلبرت, اولین تحقیقات خود را به بررسی همبندی (G(n, M اختصاص دادند و در ادامه در سال ۱۹۶۰ تحلیل‌های جزیی‌تری را ارا‌یه کردند.

منابع ویرایش

↑ Erdős, P.; Rényi, A. (1959). "On Random Graphs. I.". Publicationes Mathematicae. 6: 290–297.
↑ Gilbert, E. N. (2001). "Random Graphs". Annals of Mathematical Statistics. 30: 1141–1144. {{cite journal}}: Cite has empty unknown parameter: |1= (help), Eq. (1)
↑ Newman, Mark. E. J.; Strogatz, S. H.; Watts, D. J. (2001). "Random graphs with arbitrary degree distributions and their applications". Physical Review E. 64: 026118. arXiv:cond-mat/0007235. doi:10.1103/PhysRevE.64.026118.
↑ Erdős, P.; Rényi, A. (1960). "On the evolution of random graphs" (PDF). Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences]. 5: 17–61. The probability p used here refers there to $N(n)={\tbinom {n}{2}}p$
↑ Matula, David W. (February 1972). "The employee party problem". Notices of the American Mathematical Society. 19: A-382.
↑ Buldyrev, S. V.; Parshani, R.; Paul, G.; Stanley, H. E.; Havlin, S. (2010). "Catastrophic cascade of failures in interdependent networks". Nature. 464 (7291): 1025–8. doi:10.1038/nature08932. PMID 20393559. Archived from the original on 18 اكتبر 2017. Retrieved 9 June 2018. {{cite journal}}: Check date values in: |archive-date= (help)
↑ Gilbert, E.N. (1959). "Random Graphs". Annals of Mathematical Statistics. 30 (4): 1141–1144. doi:10.1214/aoms/1177706098.

[1] Erdős, P.; Rényi, A. (1959). "On Random Graphs. I.". Publicationes Mathematicae. 6: 290–297.

[2] Gilbert, E. N. (2001). "Random Graphs". Annals of Mathematical Statistics. 30: 1141–1144. {{cite journal}}: Cite has empty unknown parameter: |1= (help), Eq. (1)

[3] Newman, Mark. E. J.; Strogatz, S. H.; Watts, D. J. (2001). "Random graphs with arbitrary degree distributions and their applications". Physical Review E. 64: 026118. arXiv:cond-mat/0007235. doi:10.1103/PhysRevE.64.026118.

[Erdos1960-4] Erdős, P.; Rényi, A. (1960). "On the evolution of random graphs" (PDF). Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences]. 5: 17–61. The probability p used here refers there to $N(n)={\tbinom {n}{2}}p$

[5] Matula, David W. (February 1972). "The employee party problem". Notices of the American Mathematical Society. 19: A-382.

[6] Buldyrev, S. V.; Parshani, R.; Paul, G.; Stanley, H. E.; Havlin, S. (2010). "Catastrophic cascade of failures in interdependent networks". Nature. 464 (7291): 1025–8. doi:10.1038/nature08932. PMID 20393559. Archived from the original on 18 اكتبر 2017. Retrieved 9 June 2018. {{cite journal}}: Check date values in: |archive-date= (help)

[g59-7] Gilbert, E.N. (1959). "Random Graphs". Annals of Mathematical Statistics. 30 (4): 1141–1144. doi:10.1214/aoms/1177706098.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]