Rastgele grafik - Random graph

Gelen matematik , rasgele grafik başvurmak için genel bir terimdir olasılık dağılımları üzerinde grafik . Rastgele grafikler, basitçe bir olasılık dağılımıyla veya onları oluşturan rastgele bir süreçle tanımlanabilir . Rastgele grafikler teorisi, grafik teorisi ve olasılık teorisi arasındaki kesişme noktasında yer alır . Matematiksel bir bakış açısından, tipik grafiklerin özellikleri hakkındaki soruları yanıtlamak için rastgele grafikler kullanılır . Pratik uygulamaları, karmaşık ağların modellenmesi gereken tüm alanlarda bulunur - bu nedenle, farklı alanlarda karşılaşılan çeşitli karmaşık ağ türlerini yansıtan birçok rastgele grafik modeli bilinmektedir. Matematiksel bir bağlamda, rastgele grafik neredeyse yalnızca Erdős–Rényi rastgele grafik modeline atıfta bulunur . Diğer bağlamlarda, herhangi bir grafik modeli rastgele bir grafik olarak adlandırılabilir .

Modeller

Rastgele bir grafik, izole edilmiş n tane köşe kümesiyle başlayarak ve aralarına rasgele ardışık kenarlar eklenerek elde edilir . Bu alandaki çalışmanın amacı, grafiğin belirli bir özelliğinin hangi aşamada ortaya çıkma olasılığının olduğunu belirlemektir. Farklı rastgele grafik modelleri , grafikler üzerinde farklı olasılık dağılımları üretir . En fazla çalışılan önerdiği biridir Edgar Gilbert , gösterilen G ( n , p , mümkün olan her kenar bağımsız bir şekilde, olasılığı, 0 <ile ortaya çıktığı), p <elde etme ihtimali 1. Herhangi bir özel rasgele grafik m kenarları olan ibaresiyle . ${\ Displaystyle p^{m}(1-p)^{Nm}}$ $N={\tbinom {n}{2}}$

Yakından ilişkili bir model olan Erdős–Rényi modeli G ( n , M ) ile gösterilir ve tam olarak M kenarlı tüm grafiklere eşit olasılık atar . 0 ≤ M ≤ N ile G ( n , M ) öğelerine sahiptir ve her öğe olasılıkla oluşur . İkinci model, n köşe ile başlayan ve kenarsız bir stokastik süreç olan rastgele grafik sürecinin belirli bir zamanındaki ( M ) bir anlık görüntüsü olarak görülebilir ve her adımda, kümeden eşit olarak seçilen bir yeni kenar ekler. eksik kenarlar ${\tbinom {N}{M}}$ $1/{\tbinom {N}{M}}$ ${\tilde {G}}_{n}$

Bunun yerine sonsuz bir köşe kümesiyle başlarsak ve yine olası her kenarın 0 < p < 1 olasılıkla bağımsız olarak gerçekleşmesine izin verirsek , sonsuz rastgele grafik adı verilen bir G nesnesi elde ederiz . p'nin 0 veya 1 olduğu önemsiz durumlar dışında , böyle bir G hemen hemen kesinlikle aşağıdaki özelliğe sahiptir:

Herhangi bir n + m elemanı verildiğinde , V'de her birine bitişik olan ve hiçbirine bitişik olmayan bir c tepe noktası vardır . $a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V$ $a_{1},\ldots ,a_{n}$ $b_{1},\ldots ,b_{m}$

Eğer köşe kümesi sayılabilir ise, o zaman izomorfizme kadar , bu özelliğe sahip sadece tek bir grafik, yani Rado grafiği vardır . Bu nedenle, herhangi bir sayılabilir sonsuz rastgele grafik neredeyse kesinlikle Rado grafiğidir ve bu nedenle bazen basitçe rastgele grafik olarak adlandırılır . Bununla birlikte, yukarıdaki özelliği karşılayan birçok (isomorfik olmayan) grafiğin bulunduğu sayılamayan grafikler için benzer sonuç doğru değildir.

Gilbert'in rastgele çizge modelini genelleştiren bir diğer model ise rastgele nokta çarpım modelidir . Rastgele bir nokta-çarpım grafiği, her bir köşe ile gerçek bir vektörü ilişkilendirir . Herhangi bir u ve v köşeleri arasında bir uv kenarı olasılığı, ilgili vektörlerinin nokta çarpımının u • v'nin bir fonksiyonudur .

Ağ olasılık matrisi modelleri olasılığını temsil eden kenar olasılıkları ile rastgele grafikler, belirli bir kenarı olduğu , belirli bir süre için var. Bu model yönlendirilmiş ve yönlendirilmemiş olarak genişletilebilir; ağırlıklı ve ağırlıksız; ve statik veya dinamik grafik yapısı. $p_{i,j}$ $e_{i,j}$

İçin M ≃ pN , N da kenar maksimal sayısıdır, iki en yaygın olarak kullanılan model, G ( n , E ) ve G ( n , p ), hemen hemen birbirinin yerine kullanılabilir.

Rastgele düzenli grafikler, genel olarak rastgele grafiklerden farklı olabilecek özelliklere sahip özel bir durum oluşturur.

Rastgele grafikler modelimiz olduğunda, grafiklerdeki her fonksiyon rastgele bir değişken haline gelir . Bu modelin çalışması, bir özelliğin ortaya çıkıp çıkmayacağını veya en azından olasılığını tahmin etmektir.

terminoloji

Rastgele grafikler bağlamında 'neredeyse her' terimi, hata olasılıkları sıfıra eğilimli olacak şekilde bir dizi boşluk ve olasılık anlamına gelir .

Özellikler

Rastgele grafikler teorisi, belirli bir dağılımdan çizilen grafikler için yüksek olasılıkla tutulan rastgele grafiklerin tipik özelliklerini inceler. Örneğin, belirli bir değeri için isteyebilir ve ne ihtimal olduğunu edilir bağlı . Bu tür soruları incelerken, araştırmacılar genellikle rastgele grafiklerin asimptotik davranışına odaklanırlar - çok büyüdükçe çeşitli olasılıkların yakınsadığı değerler . Sızma teorisi , özellikle sonsuz büyük olanlar olmak üzere rastgele grafiklerin bağlantılılığını karakterize eder. ${\görüntüleme stili n}$ ${\görüntüleme stili p}$ ${\görüntüleme stili G(n,p)}$ ${\görüntüleme stili n}$

Percolation, grafiğin sağlamlığı ile ilgilidir (ağ olarak da adlandırılır). Rastgele bir düğüm grafiği ve ortalama bir derece verildi . Daha sonra rastgele bir düğüm parçasını kaldırırız ve yalnızca bir kesri bırakırız . Altında devasa bir bağlı bileşen varken ağın parçalandığı kritik bir sızma eşiği vardır. ${\görüntüleme stili n}$ $\langle k\rangle$ ${\ Displaystyle 1-p}$ ${\görüntüleme stili p}$ $p_{c}={\tfrac {1}{\langle k\rangle }}$ ${\ Displaystyle p_{c}}$

Yerelleştirilmiş sızma, bir düğümün komşularını, bir sonraki en yakın komşularını vb . ağdan düğümlerin bir kısmı kaldırılıncaya kadar kaldırmayı ifade eder . Poisson derece dağılımı ile rastgele grafik için tam olarak rastgele çıkarma için olduğu gibi gösterildi. Derece dağılımları diğer türleri için lokalize saldırının rastgele saldırı farklıdır (eşik fonksiyonları, evrimi ) ${\ Displaystyle 1-p}$ $p_{c}={\tfrac {1}{\langle k\rangle }}$ ${\ Displaystyle p_{c}}$ ${\görüntüleme stili {\tilde {G}}}$

Rastgele grafikler, belirli özelliklere sahip grafiklerin varlığını kanıtlamaya çalışan olasılık yönteminde yaygın olarak kullanılır . Rastgele bir grafikte bir özelliğin varlığı, genellikle, Szemerédi düzenlilik lemması aracılığıyla, hemen hemen tüm grafiklerde bu özelliğin varlığını ima edebilir .

İçinde rastgele normal grafikler , grubu olduğu ile -Normal grafikler şekildedir ve doğal sayılardır, ve hatta bir. ${\görüntüleme stili G(n,r-reg)}$ ${\görüntüleme stili r}$ ${\görüntüleme stili r=r(n)}$ ${\görüntüleme stili n}$ ${\görüntüleme stili m}$ $3\leq r<n$ ${\görüntüleme stili n=2m}$

Bir grafiktir derecesi sekansı in sadece setleri kenarların sayısına bağlıdır ${\görüntüleme stili G}$ ${\görüntüleme stili G^{n}}$

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

Rastgele bir grafikteki kenarlar, hemen hemen her birinin minimum derecesi en az 1 olmasını sağlayacak kadar büyükse, hemen hemen her biri bağlantılıdır ve eğer çift ise, hemen hemen her birinin mükemmel bir eşleşmesi vardır. Özellikle, hemen hemen her rasgele grafikte son yalıtılmış köşe kaybolduğu anda, grafik bağlantılı hale gelir. ${\görüntüleme stili M}$ ${\ Displaystyle G_{M}}$ ${\ Displaystyle G_{M}}$ ${\ Displaystyle G_{M}}$ ${\görüntüleme stili n}$ ${\ Displaystyle G_{M}}$

Kenar minimum dereceyi 1'e yükselten çift sayıda köşe üzerindeki hemen hemen her grafik işlemi veya kenarlardan biraz daha fazla ve 1'e yakın olasılıkla rastgele bir grafik , grafiğin en fazla bir köşe dışında tam bir eşleşmeye sahip olmasını sağlar. . ${\tfrac {n}{4}}\log(n)$

Bazı sabitler için , köşeleri ve en azından kenarları olan hemen hemen her etiketli grafik Hamiltonyendir . Olasılığın 1'e yaklaşmasıyla, minimum dereceyi 2'ye yükselten belirli kenar grafiği Hamiltonyen yapar. ${\görüntüleme stili c}$ ${\görüntüleme stili n}$ ${\ Displaystyle cn\log(n)}$

Rastgele grafiğin özellikleri, grafik dönüşümleri altında değişebilir veya değişmez kalabilir. Örneğin, Mashaghi A. ve diğerleri, rastgele grafikleri kenar-çift grafiklerine (veya çizgi grafiklerine) dönüştüren bir dönüşümün, hemen hemen aynı derece dağılımına sahip, ancak derece korelasyonları ve önemli ölçüde daha yüksek kümeleme ile bir grafikler topluluğu ürettiğini göstermiştir. katsayı.

Boyama

V ( G ) = {1, ..., n } köşesine sahip n dereceli rastgele bir G grafiği verildiğinde , renk sayısı konusundaki açgözlü algoritma ile köşeler 1, 2, ... renklerle renklendirilebilir. (köşe 1, tepe 1'e bitişik değilse 1 renklidir, aksi takdirde 2 renklidir vb.). Kromatik polinom adı verilen bir dizi q renk verilen rastgele grafiklerin uygun renklerinin sayısı şimdiye kadar bilinmiyor. Parametreleri n ve kenar sayısı m olan rastgele grafiklerin kromatik polinomunun sıfırlarının ölçeklendirilmesi veya bağlantı olasılığı p , sembolik örüntü eşleştirmeye dayalı bir algoritma kullanılarak ampirik olarak incelenmiştir.

rastgele ağaçlar

Bir rastgele üç a, ağaç veya ağaçlık bir oluşturulur stokastik süreç . n mertebesinde ve M ( n ) büyüklüğünde rasgele grafiklerin geniş bir aralığında, k mertebesinden ağaç bileşenlerinin sayısının dağılımı asimptotik olarak Poisson'dur . Rastgele ağaç türleri arasında tek tip yayılan ağaç , rastgele minimum yayılan ağaç , rastgele ikili ağaç , treap , hızla keşfedilen rastgele ağaç , Brown ağacı ve rastgele orman bulunur .

Koşullu rastgele grafikler

Olasılık uzayında tanımlanan belirli bir rastgele grafik modeli göz önünde ve izin her grafik için gerçek değerli bir fonksiyondur olan atar olduğu bir vektör m özellikleri. Sabit , koşullu rastgele grafikler için, olasılık ölçüsünün tüm grafiklere sıfır olasılık atadığı modellerdir . ${\ Displaystyle (\Omega ,{\Mathcal {F}},P)}$ ${\mathcal {P}}(G):\Omega \rightarrow R^{m}$ ${\görüntüleme stili\Omega }$ $\mathbf {p} \inR^{m}$ ${\görüntüleme stili P}$ ${\mathcal {P}}(G)\neq \mathbf {p}$

Özel durumlar vardır şartlı düzgün rastgele grafikleri , atar tüm belirtilen özelliklere sahip olan grafikler olasılığını eşittir. Koşullandırma bilgisinin mutlaka kenar sayısı M olmadığı , ancak diğer keyfi grafik özelliği ne olursa olsun , Erdős–Rényi modeli G'nin ( n , M ) bir genellemesi olarak görülebilirler . Bu durumda çok az analitik sonuç mevcuttur ve ortalama özelliklerin ampirik dağılımlarını elde etmek için simülasyon gereklidir. ${\görüntüleme stili P}$ ${\görüntüleme stili {\matematiksel {P}}(G)}$

birbirine bağlı grafikler

Birbirine bağlı grafiklerde, bir ağdaki (graf) düğümler, çalışmak için diğer ağlara bağlıdır. Bu nedenle, bir veya birkaç grafikteki arızalar, grafikler arasında ani çökmeye neden olabilecek ardışık arızalara neden olur.

Tarih

Rastgele bir grafik modelinin ilk kullanımı, 1938'de Helen Hall Jennings ve Jacob Moreno tarafından, ağ verilerindeki karşılıklı bağlantıların fraksiyonunu rastgele modelle karşılaştırırken bir "şans sosyogramı" (yönlendirilmiş bir Erdős-Rényi modeli) dikkate alındı. . "Rastgele ağ" adı altında başka bir kullanım, 1951'de Solomonoff ve Rapoport tarafından, diğer köşelere sabit dereceli ve rastgele seçilmiş ekleri olan bir yönlendirilmiş grafikler modeli kullanılarak yapıldı.

Erdos-Rényi modeli rastgele grafiğin ilk tarafından tanımlandı Paul Erdös ve Alfréd Renyi onların 1959 Kağıt "Açık Rastgele Grafikleri" ve bağımsız onun kağıt "Rastgele grafikleri" in Gilbert tarafından.

Languages

In other projects