Rastgele grafik - Random graph

Ağ bilimi
Teori
Grafik Karmaşık ağ Bulaşma Küçük dünya Ölçeksiz Topluluk yapısı Süzülme Evrim Kontrol edilebilirlik Grafik çizimi Sosyal sermaye Bağlantı analizi Optimizasyon Mütekabiliyet Kapanış Homofilik Geçişlilik Tercihli ek Denge teorisi Ağ etkisi Sosyal etki
Ağ türleri
Bilgilendirici (bilgi işlem) Telekomünikasyon Ulaşım Sosyal Bilimsel işbirliği Biyolojik Yapay sinir Birbirine bağımlı Anlamsal Mekansal Bağımlılık Akış Çip üzerinde
Grafikler
Özellikleri Clique Bileşen Kesmek Döngü Veri yapısı Kenar Döngü Semt Yol Köşe Komşuluk listesi  / matris Olay listesi  / matris Türler Bipartit Tamamlayınız Yönetmen Aşırı Çok Rastgele Ağırlıklı
Metrikler Algoritmalar
Merkeziyet Derece Arasılık Yakınlık PageRank Motif Kümeleme Derece dağılımı Çeşitlilik Mesafe Modülerlik Verimlilik
Modeller
Topoloji Rastgele grafik Erdős – Rényi Barabási-Albert Spor modeli Watt-Strogatz Üstel rastgele (ERGM) Rastgele geometrik (RGG) Hiperbolik (HGN) Hiyerarşik Stokastik blok Maksimum entropi Yumuşak konfigürasyon LFR Benchmark Dinamikler Boole ağı ajan tabanlı Epidemi /BAYIM
Listeler Kategoriler
Konular Yazılım Ağ bilimcileri Kategori: Ağ teorisi Kategori: Grafik teorisi

İçinde matematik, rastgele grafik atıfta bulunulacak genel terim olasılık dağılımları bitmiş grafikler. Rastgele grafikler basitçe bir olasılık dağılımı veya bir rastgele süreç onları oluşturur.^[1][2] Rastgele grafikler teorisi, arasındaki kesişme noktasındadır. grafik teorisi ve olasılık teorisi. Matematiksel bir bakış açısıyla, rastgele grafikler, nesnelerin özellikleri hakkındaki soruları cevaplamak için kullanılır. tipik grafikler. Pratik uygulamaları, tüm alanlarda bulunur. karmaşık ağlar modellenmesi gerekir - 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 sadece Erdős – Rényi rastgele grafik modeli. Diğer bağlamlarda, herhangi bir grafik modeli bir rastgele grafik.

Modeller

Bir dizi ile başlayarak rastgele bir grafik elde edilir. n izole köşeler ve aralarına rastgele kenarlar ekleyerek. Bu alandaki çalışmanın amacı, grafiğin belirli bir özelliğinin hangi aşamada ortaya çıkabileceğini belirlemektir.^[3] Farklı rastgele grafik modelleri farklı üretmek olasılık dağılımları grafiklerde. En yaygın olarak incelenen, Edgar Gilbert, belirtilen G(n,p), burada olası her kenar bağımsız olarak 0 olasılıkla oluşur < p <1. Elde etme olasılığı herhangi biri rastgele grafik m kenarlar ${ displaystyle p ^ {m} (1-p) ^ {N-m}}$ gösterimle ${ displaystyle N = { tbinom {n} {2}}}$.^[4]

Yakından ilişkili bir model olan Erdős-Rényi modeli belirtilen G(n,M), tüm grafiklere tam olarak eşit olasılık atar. M kenarlar. 0 ≤ ile M ≤ N, G(n,M) vardır ${ displaystyle { tbinom {N} {M}}}$ öğeler ve her öğe olasılıkla oluşur ${ displaystyle 1 / { tbinom {N} {M}}}$.^[3] İkinci model, belirli bir zamanda anlık görüntü olarak görüntülenebilir (M) of the rastgele grafik süreci ${ displaystyle { tilde {G}} _ {n}}$, hangisi bir Stokastik süreç şununla başlar n köşeler ve kenarlar yok ve her adımda, eksik kenarlar kümesinden tek tip olarak seçilen bir yeni kenar ekliyor.

Bunun yerine sonsuz bir köşe kümesiyle başlarsak ve yine olası her kenarın 0 olasılıkla bağımsız olarak oluşmasına izin verirsek < p <1, sonra bir nesne alıyoruz G aradı sonsuz rastgele grafik. Önemsiz durumlar hariç p 0 veya 1, böyle bir G neredeyse kesin aşağıdaki özelliğe sahiptir:

Herhangi bir n + m elementler ${ displaystyle a_ {1}, ldots, a_ {n}, b_ {1}, ldots, b_ {m} V’de}$bir tepe var c içinde V her birine bitişik olan ${ displaystyle a_ {1}, ldots, a_ {n}}$ ve hiçbirine bitişik değil ${ displaystyle b_ {1}, ldots, b_ {m}}$.

Köşe seti ise sayılabilir o zaman var kadar izomorfizm, bu özelliğe sahip yalnızca tek bir grafik, yani Rado grafiği. Böylelikle, sayılabilir şekilde sonsuz rastgele herhangi bir grafik neredeyse kesinlikle Rado grafiğidir ve bu nedenle bazen basitçe rastgele grafik. Ancak, yukarıdaki özelliği karşılayan çok sayıda (izomorfik olmayan) grafiğin bulunduğu sayılamayan grafikler için benzer sonuç doğru değildir.

Gilbert'in rastgele grafik modelini genelleyen başka bir model, rastgele iç çarpım modeli. Rastgele bir iç çarpım grafiği, her bir köşe ile ilişkilendirir a gerçek vektör. Bir kenar olasılığı uv herhangi bir köşe arasında sen ve v bir işlevi nokta ürün sen • v kendi vektörlerinin.

ağ olasılık matrisi Olasılığı temsil eden kenar olasılıkları aracılığıyla rastgele grafikleri modeller ${ displaystyle p_ {i, j}}$ bu belirli bir kenar ${ displaystyle e_ {i, j}}$ 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ı.

İçin M ≃ pN, nerede N mümkün olan maksimum kenar sayısı, en yaygın kullanılan iki model, G(n,M) ve G(n,p), neredeyse birbirinin yerine kullanılabilir.^[5]

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

Bir rastgele grafik modeline sahip olduğumuzda, grafiklerdeki her fonksiyon bir rastgele değişken. Bu modelin çalışması, bir mülkün meydana gelip gelmeyeceğini belirlemek veya en azından olasılığını tahmin etmektir.^[4]

Terminoloji

Rastgele grafikler bağlamında 'hemen hemen her' terimi, boşluklar ve olasılıklar dizisini ifade eder, öyle ki hata olasılıkları sıfır eğilimindedir.^[4]

Özellikleri

Rastgele grafikler teorisi, belirli bir dağılımdan çizilen grafikler için yüksek olasılıkla tutan rastgele grafiklerin tipik özelliklerini inceler. Örneğin, belirli bir değeri isteyebiliriz ${ displaystyle n}$ ve ${ displaystyle p}$ Olasılık nedir ${ displaystyle G (n, p)}$ dır-dir bağlı. Bu tür soruları incelerken, araştırmacılar genellikle rastgele grafiklerin asimptotik davranışına, yani çeşitli olasılıkların yakınsadığı değerler üzerine yoğunlaşırlar. ${ displaystyle n}$ çok büyür. Süzülme teorisi Rastgele grafiklerin, özellikle sonsuz büyüklükteki grafiklerin bağlantılılığını karakterize eder.

Süzülme grafiğin sağlamlığı ile ilgilidir (ağ olarak da adlandırılır). Rastgele bir grafik verildiğinde ${ displaystyle n}$ düğümler ve ortalama derece ${ displaystyle langle k rangle}$. Sonra rastgele bir kesiri kaldırıyoruz ${ displaystyle 1-p}$ düğüm sayısı ve sadece bir kısmını bırakın ${ displaystyle p}$. Kritik bir süzülme eşiği var ${ displaystyle p_ {c} = { tfrac {1} { langle k rangle}}}$ altındayken ağ parçalanır ${ displaystyle p_ {c}}$ devasa bir bağlı bileşen var.^{[1][5][6][7][8][9]}

Lokalize süzülme, bir düğümün komşularının, en yakın komşularının vb. ${ displaystyle 1-p}$ ağdaki düğümlerin sayısı kaldırılır. Poisson derece dağılımına sahip rastgele grafik için ${ displaystyle p_ {c} = { tfrac {1} { langle k rangle}}}$ tam olarak rastgele kaldırmada olduğu gibi. Diğer derece dağılım türleri için ${ displaystyle p_ {c}}$ yerel saldırı için rastgele saldırıdan farklıdır^[10](eşik fonksiyonları, evrimi ${ displaystyle { tilde {G}}}$)

Rastgele grafikler yaygın olarak kullanılmaktadır. olasılık yöntemi, belirli özelliklere sahip grafiklerin varlığını kanıtlamaya çalışıldığında. Rastgele bir grafikte bir mülkün varlığı, genellikle Szemerédi düzenlilik lemma, hemen hemen tüm grafiklerde bu özelliğin varlığı.

İçinde rastgele düzenli grafikler, ${ displaystyle G (n, r-reg)}$ kümesidir ${ displaystyle r}$-düzenli grafikler ${ displaystyle r = r (n)}$ öyle ki ${ displaystyle n}$ ve ${ displaystyle m}$ doğal sayılardır ${ displaystyle 3 leq r$, ve ${ displaystyle rn = 2m}$ eşittir.^[3]

Bir grafiğin derece dizisi ${ displaystyle G}$ içinde ${ displaystyle G ^ {n}}$ sadece setlerdeki kenar sayısına bağlıdır^[3]

${ displaystyle V_ {n} ^ {(2)} = sol {ij : 1 leq j leq n, ben neq j sağ } alt küme V ^ {(2)}, qquad i = 1, cdots, n.}$

Kenar varsa, ${ displaystyle M}$ rastgele bir grafikte ${ displaystyle G_ {M}}$ neredeyse her birinin ${ displaystyle G_ {M}}$ en az 1, sonra hemen hemen her ${ displaystyle G_ {M}}$ bağlı ve eğer ${ displaystyle n}$ eşit, neredeyse her ${ displaystyle G_ {M}}$ mükemmel bir eşleşmeye sahiptir. Özellikle, en son izole edilmiş köşe neredeyse her rastgele grafikte yok olduğu anda, grafik bağlanır.^[3]

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

Bazıları için ${ displaystyle c}$, hemen hemen her etiketli grafik ${ displaystyle n}$ köşeler ve en azından ${ displaystyle cn log (n)}$ kenarlar Hamiltoniyen. Olasılık 1'e yöneldiğinde, minimum dereceyi 2'ye çıkaran belirli kenar grafiğini Hamiltonian yapar.

Rastgele grafiğin özellikleri, grafik dönüşümleri altında değişebilir veya değişmez kalabilir. Mashaghi A. ve diğerleri, örneğin, rastgele grafikleri kenar çift grafiklerine (veya çizgi grafiklerine) dönüştüren bir dönüşümün, neredeyse aynı derece dağılımına sahip, ancak derece korelasyonları ve önemli ölçüde daha yüksek bir kümeleme katsayısına sahip bir grafik topluluğu oluşturduğunu gösterdi.^[11]

Boyama

Rastgele bir grafik verildiğinde G düzenin n tepe noktası ile V(G) = {1, ..., n} tarafından Açgözlü algoritma renk sayısında, köşeler 1, 2, ... renkleriyle renklendirilebilir (köşe 1, köşe 1'e bitişik değilse 1 renklidir, aksi takdirde 2 renklidir vb.) .^[3]Bir dizi verilen rastgele grafiklerin uygun renklendirme sayısı q renkler, buna denir kromatik polinom, şu ana kadar bilinmiyor. Parametrelerle rastgele grafiklerin kromatik polinomunun sıfırlarının ölçeklendirilmesi n ve kenarların sayısı m veya bağlantı olasılığı p deneysel olarak sembolik örüntü eşleştirmeye dayalı bir algoritma kullanılarak incelenmiştir.^[12]

Rastgele ağaçlar

Bir rastgele ağaç bir ağaç veya ağaçlandırma tarafından oluşturulan Stokastik süreç. Çok çeşitli rasgele grafiklerde n ve boyut M(n) siparişteki ağaç bileşenlerinin sayısının dağılımı k asimptotik olarak Poisson. Rastgele ağaç türleri şunları içerir: tek tip yayılma ağacı, rastgele minimal genişleyen ağaç, rastgele ikili ağaç, Treap, rastgele ağacı hızla keşfediyor, Brownian ağacı, ve rastgele orman.

Koşullu rastgele grafikler

Olasılık uzayında tanımlanan belirli bir rastgele grafik modelini düşünün ${ displaystyle ( Omega, { mathcal {F}}, P)}$ ve izin ver ${ displaystyle { mathcal {P}} (G): Omega sağ r ^ {m}}$ her grafiğe atayan gerçek değerli bir işlev ${ displaystyle Omega}$ bir vektör m özellikleri. Sabit bir ${ displaystyle mathbf {p} içinde R ^ {m}}$, koşullu rastgele grafikler olasılık ölçüsünün kullanıldığı modellerdir ${ displaystyle P}$ tüm grafiklere sıfır olasılık atar, öyle ki '${ displaystyle { mathcal {P}} (G) neq mathbf {p}}$.

Özel durumlar koşullu olarak tek tip rastgele grafikler, nerede ${ displaystyle P}$ belirtilen özelliklere sahip tüm grafiklere eşit olasılık atar. Bir genelleme olarak görülebilirler. Erdős-Rényi modeli G(n,M), koşullandırma bilgisi mutlaka kenar sayısı olmadığında M, ancak diğer rasgele grafik özelliği ${ displaystyle { mathcal {P}} (G)}$. Bu durumda çok az analitik sonuç mevcuttur ve ortalama özelliklerin ampirik dağılımlarını elde etmek için simülasyon gereklidir.

Birbirine bağlı grafikler

Birbirine bağlı grafiklerde, bir ağdaki (grafik) düğümlerin çalışması diğer ağlara bağlıdır. Bu nedenle, bir veya birkaç grafikteki arızalar, grafikler arasında ani çökmeye neden olabilecek kademeli arızalara neden olur.^[13][14]

Tarih

Rastgele bir grafik modelinin ilk kullanımı Helen Hall Jennings ve Jacob Moreno 1938'de, ağ verilerindeki karşılıklı bağlantıların fraksiyonunu rastgele modelle karşılaştırırken çalışırken bir "şans sosyogramı" (yönlendirilmiş bir Erdős-Rényi modeli) düşünülmüştür.^[15] "Rastgele net" adı altında başka bir kullanım, 1951'de Solomonoff ve Rapoport tarafından, sabit dış dereceli ve diğer köşelere rastgele seçilen eklere sahip yönlendirilmiş bir grafik modeli kullanarak gerçekleştirildi.^[16]

Erdős-Rényi modeli rastgele grafiklerin yüzdesi ilk olarak Paul Erdős ve Alfréd Rényi 1959 tarihli "Rastgele Grafikler Üzerine" başlıklı makalesinde^[9] ve bağımsız olarak Gilbert tarafından "Random graphs" adlı makalesinde.^[6]

Ayrıca bakınız

• Bose-Einstein yoğunlaşması: bir ağ teorisi yaklaşımı
• Boşluk yöntemi
• Karmaşık ağlar
• Çift fazlı evrim
• Erdős-Rényi modeli
• Üstel rastgele grafik modeli
• Grafik teorisi
• Birbirine bağlı ağlar
• Ağ bilimi
• Süzülme
• Süzülme teorisi
• Normal grafik
• Serbest ağı ölçeklendirin
• Yarı doğrusal yanıt
• Stokastik blok modeli
• Lancichinetti – Fortunato – Radicchi karşılaştırması

Referanslar