Rastgele Ağın Bağlantı Oranı Araştırması
Yang Yuqi, Zhu Lei
(İletişim Mühendisliği Okulu, PLA Bilim ve Teknoloji Üniversitesi, Nanjing 210007, Çin)
Rastgele grafik, gerçek dünyadaki çeşitli gerçek sistemleri soyutlamak için kullanılabilen basit bir ağdır. Diğer ağ modellerinden farklı olarak, rastgele grafiklerin yapımı, düğümlerinin eşdeğer olduğunu belirler ve ağda izole düğümler ve alt grafikler olabilir. Rastgele grafikler üzerine yapılan araştırmalar, özellikle bunların bağlanabilirliği, rastgele bağlantı özelliklerine ve düğüm eşleme özelliklerine sahip gerçek ağların daha derinlemesine anlaşılmasına yardımcı olur. Makale, rastgele grafiklerin bağlanabilirliğine ve rastgele grafiklerin bağlanabilirlik oranının hesaplanma yöntemine odaklanmak için teori ve simülasyonun bir kombinasyonunu kullanır, evrim sürecindeki rastgele grafiklerin morfolojik değişimlerini ortaya çıkarır ve rastgele grafiklerde ağaç yapılarının yaygın varlığını gösterir. Çalışma ayrıca, birbirine bağlı büyük alt grafiklerin oluşturulmasından önce, rastgele grafiklerin alt grafik boyutlarının bir güç yasası dağılımına sahip olduğunu buldu. Bu çalışmanın sonuçları, karmaşık ağlar üzerine deneysel araştırmalar ve karmaşık ağların faz geçişleri üzerine araştırmalar için teorik bir temel sağlar.
Rastgele grafik; bağlantı oranı; alt grafik
1960'larda ERDSP ve RNYI A tarafından önerilen rastgele grafik modelinden bu yana, rastgele grafik teorisi bir zamanlar karmaşık ağları incelemek için temel teori haline geldi. Araştırması çoğunlukla alt grafiklerin ortalama boyutu, birbirine bağlı devasa alt grafiklerin varoluş koşulları ve kompozisyon kurallarının iyileştirilmesi gibi kendi istatistiksel özelliklerinin tanımına odaklanmaktadır [2]. Rastgele bir grafikte, herhangi iki düğüm belirli bir olasılıkla doğrudan bağlantılıdır.İnsanlar bunu kişilerarası ağ, virüs aktarım ağı, ulaşım ağı gibi bazı doğal ağların temel soyutlaması olarak kullanmayı bekler. [3-5]. Bununla birlikte, büyük ölçekli deneysel çalışmalar, doğadaki çoğu gerçek ağın, rasgele grafiklerden oldukça farklı olan ölçeksiz ağlara [6] ait olduğunu (düğümlerin derece dağılımı bir güç yasası dağılımıdır) göstermiştir. Rastgele grafiklerin basit yapım yöntemi, gerçek ağların yapısının daha doğru bir simülasyonundan yoksun olduğunu belirler.Birçok gerçek ağın topolojik istatistiksel özelliklerini ve dinamik özelliklerini tek başına rastgele grafikler çalışarak elde etmek imkansızdır. Bununla birlikte, istatistiksel bir bakış açısından, ağın bağlanabilirliği hala rastgele grafiklerin incelenmesi yoluyla görülebilir.
Modern toplumda, insanlar her zaman çeşitli karmaşık sistemlerin içindedir veya onlarla iletişim kurmaktadır. Doğal düşünce, bir bireyin başka bir bireyle temas kurma olasılığıdır. Araştırma yöntemlerinin kısıtlılığı ve ağ topolojisinin karmaşıklığı nedeniyle, ağ bağlantısı üzerine geleneksel araştırmalar ağ düğümleri arasındaki bağlantının mikroskobik düşüncelerini göz ardı ederek ağ bağlanabilirliği alt grafiklerine [7-8] odaklanma eğilimindedir. Ek olarak, rastgele grafik alt grafiği üzerindeki araştırma, esas olarak alt grafiğin ortalama boyutuna odaklanır ve alt grafiğin boyut dağılımının nicel bir tanımından, özellikle de devasa bağlantılı alt grafikte [9-10] oluşmak üzere olan faz dönüşümünden yoksundur. Bu makale araştırma nesnesi olarak rastgele grafikleri alır, rastgele grafiklerin bağlantı oranını önerir ve inceler, alt grafiklerde dolambaçlı yolların varlığını varsayar ve doğrular ve simülasyon deneylerine dayalı faz geçişinde alt grafiklerin boyut dağılımını önerir. Elde edilen araştırma sonuçları, gerçek ağ sistemlerinin planlanmasına, inşasına ve analizine etkin bir şekilde uygulanabilir.
Ara Bağlantı Oranı (IR), Şekil 1 (b) 'de gösterildiği gibi, bağlı düğüm çiftlerinin sayısının (doğrudan bağlantı veya çoklu atlama bağlantısı) ağdaki toplam düğüm çifti sayısına oranı olarak tanımlanır. Ağ topolojisi göz önüne alındığında, ağın bağlantı hızı kolayca elde edilebilir. Dağınık düğümlerden oluşan bir ağ için bağlantı hızı 0'dır ve bağlı bir ağ için bağlantı hızı 1'dir. Grafiğin minimum yayılma ağacı, en verimli tam bağlantılı ağ olan en az sayıda kenarla tamamen bağlantılıdır. Şekil 1 (a), (c), (d) 'de gösterildiği gibi.
Rastgele grafik [1], herhangi iki düğümün bağlanma olasılığının p ve bağlı kenarların toplam sayısının L = N (N-1) p / 2 olduğu N düğümlü bir ağ olarak tanımlanır. Ağ yapısının evrimi açısından bakıldığında, ağa her yeni düğüm katıldığında, yeni düğümün p olasılıkla mevcut her düğümle bir kenar oluşturduğu şeklinde ifade edilebilir. Rastgele grafiğin derece dağılımı Poisson dağılımı [11] ve düğümlerin ortalama derecesi z = 2L / N = (N-1) p'dir. Eğer p küçükse, sadece N düğüm sayısı büyükse, yani ağ ölçeği büyükse daha büyük bir z olacaktır.Çok sayıda düğüm ve büyük düğüm derecesi çelişkili görünmektedir, ancak rastgele grafik ağında çok yakın İletişim. İnşa yönteminden, rastgele grafiklerin önemli bir özelliğinin, düğümler arasındaki ilişkilerin eşitliği olduğu görülebilir.Düğümlerin derecesi, diğer birçok karmaşık ağ modelinde (ölçeksiz ağ modelleri gibi) bulunmayan, ortalama derece z'ye yakın yoğunlaşmıştır. doğa. Eş ilişkileri olan rastgele grafikler için, ağ ölçeği yeterince büyükse veya tekrarlanan denemelerin sayısı büyükse, ağın bağlantı oranı, ağdaki herhangi iki düğümün birbirine bağlanma olasılığına istatistiksel olarak eşdeğerdir, böylece rastgele Grafiğin ağ seviyesi, düğüm seviyesi ile etkili bir şekilde birleştirilir.
Rastgele grafikler çalışmasında, p'nin değeri ve rastgele grafiğin ölçeği nasıl değişirse değişsin, ağın kenar sayısı L ve düğüm sayısı N, L = 2N'yi (yani z4) sağladığında, her zaman IR = 0,9613 olur. Bu, her düğümün ortalama olarak kalan 4 düğüme doğrudan bağlanması durumunda, bu düğüm 0.961 olasılıkla ağdaki herhangi bir düğüme bağlanacaktır. L / N daha fazla artarsa, bağlanabilirlik olasılığı buna göre artacaktır. Aslında, rastgele bir grafiğin [12] LER1 + ln (1 / p) / ln (z) ortalama yol uzunluğu, p = 0.001 ve z = 4 olduğunda, LER6, ünlü "altı" ile aynı gibi görünüyor Derece ayrımı "[13] da benzer bir sonuca sahiptir.
2 Rastgele grafiğin bağlantı oranı
2.1 Dolambaçsız durum
Düğüm sayısı ile yukarıdaki rastgele grafikteki kenarların sayısı arasındaki ikinci dereceden ilişkiden, düğüm sayısı N küçük olduğunda, L kenar sayısı nispeten küçüktür, şu anda ağda herhangi bir sapma olmadığı varsayılarak, yani herhangi iki düğüm bağlı değildir. Ya da sadece bir yol vardır, şu anda alt grafik bir ağaç yapısındadır. Sapmasız ağ durumunda, iki düğümün doğrudan bağlı olmama olasılığı 1-p'dir ve iki atlama ile bağlı olmama olasılığı (1-p2) A1N-2, ..., i (1iN aracılığıyla değil) -2) Atlama bağlantısının olasılığı (1-pi) Ai-1N-2'dir (burada Aba, b düğümlerinin bir düğümden seçildiği permütasyon sayısını temsil eder). Bu nedenle, rastgele bir grafikteki herhangi iki düğümün alternatif rota olmayan bağlantı oranı IRna:
Bunlar arasında, sağ uçtaki n parametresi, bağlı yoldaki ara düğümlerin sayısını temsil eden i'den farklıdır. P belirlendiğinde, formül (1) 'in sağ ucundaki ikinci terim, logaritma alınarak elde edilen N'nin bir fonksiyonudur:
Hallettim:
Formüle (1) getirelim:
Denklem (4), düğümler arasında dolambaçsız bağlantı oranıdır Yukarıda bahsedilen rastgele grafiğin doğasına göre, bu bağlantı hızı aynı zamanda ağ bağlantı hızıdır.
Evrimsel bir perspektiften, bağlanabilirliği fark etmeden önce, rastgele grafik iki formdan geçti. İlk biçim, ağın birçok küçük ölçekli bağlantılı alt grafikten oluşması ve ikinci biçimin, ağda birbirine bağlı çok büyük bir alt grafik ve bazı daha küçük bağlantılı alt grafiklerin bir arada bulunmasıdır [14]. Bu makale, birbirine bağlı devasa alt grafiklerin oluşumundan önceki ilk formun, alt grafiklerin genellikle bir ağaç yapısına sahip olduğuna, yani dolambaçlı yollar içermediğine inanmaktadır. Bu görünüm simülasyon test bölümünde doğrulanacaktır. İkinci formdaki bağlantı hızı aşağıda tartışılmaktadır.
2.2 Büyük bağlantılı alt grafikler var
Rastgele bir grafikte, devasa bağlı alt grafikteki düğüm sayısının toplam ağ düğüm sayısına oranı S [9]:
Büyük bağlantılı alt grafiğin kendisinin bir ağaç olma olasılığı çok küçüktür (pSN-1'den daha az), bu nedenle dolambaçlı yollar olmalıdır ve birbirine bağlı büyük alt grafiklerle birlikte var olan küçük bağlantılı alt grafiklerde dolambaçlı yollar olup olmadığı dikkate alınmaya değerdir. Şekil 2'de gösterilen senaryoyu düşünün. C düğümünün eklenmesi, A ve B düğümleri arasında fazladan bir dolambaçlı yol oluşturan iki kenar (kesikli çizgilerle gösterilmiştir) getirir. Ancak gerçek şu ki, C düğümü ağa katıldığında, devasa bağlı alt grafiğe bağlanma olasılığı P1 = 1 (1 p) SN'dir ve AB alt grafiğine bağlanma olasılığı P2 = 1 (1 p) 2, P1'dir. P2, dolayısıyla gerçek çıkarım ilkesine göre, Şekil 2'de gösterilen sahne pratikte neredeyse hiç olmayacak. Başka bir deyişle, ağda rastgele bir uç seçilirse, ağın diğer bölümlerinden ziyade büyük olasılıkla büyük bir bağlı alt grafiğe yerleştirilir. Bu sonuca dayanarak, büyük bağlantılı alt grafikler mevcut olduğunda, küçük bağlantılı alt grafiklerin dolambaçlı yollar içermediği belirlenebilir.
Büyük bağlı alt grafik oluşturulduktan sonra, bağlantı oranını hesaplamak için ağdan rastgele iki düğüm seçilir.Aşağıdaki gibi üç durum vardır:
(1) Her iki düğüm de büyük bir bağlı alt grafikte bulunur ve olası düğüm çiftlerinin sayısı düğüme bağlıdır;
(2) Büyük bağlı alt grafikte yalnızca bir düğüm vardır ve olası düğüm çiftlerinin sayısı
, Düğüm bağlı değil;
(3) Her iki düğüm de devasa bağlı alt grafikte değildir Olası düğüm çiftlerinin sayısı, bağlı düğüm çiftlerinin sayısının olduğu, sapmasız ağ bağlantı oranıyla ilgili yukarıdaki tartışmaya dayanmaktadır.
Özetle, devasa bağlı alt grafiğin oluşumundan sonra ağın bağlanabilirlik oranı:
Bunların arasında herhangi bir gerçek sayı vardır ve r, negatif olmayan bir tam sayıdır. IRna ve S parametreleri sırasıyla denklemler (4) ve (5) ile verilir ve ikinci eşit işaret kesinlikle N koşulu altında oluşturulur. Bağlantı olasılığı p belirlendiğinde, formül (6), IR'nin N'ye göre örtük fonksiyonudur ve bu, önce S'yi belirleyerek ve sonra N'yi belirleyerek hesaplanabilir.
2.3 Ağın faz dönüşümü
Yukarıdakiler, iki durumda rastgele grafiğin bağlantı oranının hesaplama yöntemlerini verir Hesaplama, alt grafiğin dolambaçlı yollar içermediği, yani alt grafiğin bir ağaç yapısında olduğu varsayımına dayanır. Bununla birlikte, rastgele grafiğin evriminde hala bir ara durum vardır. Bu durumda, alt grafikler ani bir değişimde büyük bağlantılı bir alt grafik oluşturmak için bir araya gelir. Bu süzülme durumuna rastgele grafiğin faz geçişi denir [15 ], çalışma büyük bağlı alt grafiğin oluşturduğu faz geçiş noktasının z = 1 [16] olduğunu göstermektedir. Faz dönüşümünün nicel analizi daha zordur ve çok az ilgili belge vardır. Bu yazıda, rastgele grafiklerin faz geçişlerinin alt grafiklerinin boyut dağılımını incelemek için çok sayıda deney yapılmış ve faz geçişlerinin alt grafiklerinin çift logaritmik koordinatlar altında güç yasası dağılımına uygun olduğu bulunmuştur.Şekil 3'te gösterildiği gibi, dağılım görüntüleri ters çevrilmiş boru şekilleridir.
Alt grafiklerin boyutunun güç yasası dağılımı, faz geçişindeki daha küçük ölçekli alt grafiklerin çoğunluğu hesaba kattığını gösterir, ancak yine de az sayıda nispeten büyük ölçekli alt grafik vardır Bu tür alt grafiklerin boyut dağılımı son derece düzensizdir. Bu makalede, üstel kuyruk y = 10xex / olan bir güç yasası dağılımı, bu durumda alt grafiğin boyut dağılımına uymak için kullanılmıştır; burada x, alt grafikteki düğüm sayısını, y, x düğümlü alt grafik sayısını ve , Firar uzunluğu. Montaj sonuçları Tablo 1'de gösterilmektedir.
3 Simülasyon testi
Önceki teorik analiz sayesinde, rastgele grafik bağlantı oranı ve rastgele grafik morfolojisi hakkında bazı önemli sonuçlar elde edildi. Bu makale, simülasyon testleri aracılığıyla yukarıdaki sonuçları doğrulamaktadır, esas olarak p = 0.005 (sonuçların geri kalanı benzerdir) ve test sonuçlarının ortalaması 1.000 kez olduğunda simülasyon test sonuçlarını vermektedir. Rastgele grafiğin bağlantı oranının simülasyonu Şekil 4 ve 5'de gösterilmektedir. Kesintisiz çizgi kısmı teorik değerdir ve faz dönüşümünden önceki ve sonraki bağlantı oranı sırasıyla formül (4) ve formül (6) ile hesaplanır. Şekil 4'te simülasyon sonuçları, bağlantı oranı için hesaplama formülünün doğruluğunu gösteren ve yukarıda belirtilen varsayımların doğruluğunu dolaylı olarak kanıtlayan teorik değerlerle iyi bir uyum içindedir, yani rastgele grafiğin küçük alt grafikleri temelde dolaylı nedenler olmaksızın bir ağaç yapısıdır. . Özellikle, bu makalenin 2. Bölümündeki bulgular için teorik bir temel sağlayan IR = 0.9613 elde etmek için formül (6) 'daki N = 801 (şu anda L = 2N) olsun.
Şekil 5, faz geçişinin bağlanabilirlik oranının simülasyon değerini göstermektedir (burada aralık z (0.85, 1.15) 'dir) Açıktır ki, ağ faz geçişinin bağlantı oranını hesaplamak için denklem (4) veya denklem (6) kullanıldığında büyük bir hata olacaktır. . Bu makalenin faz dönüşüm alt grafiğinin boyut dağılımına ilişkin sonuçları birleştirilerek ve Tablo 1'deki parametrelerin değerlerine uyarak, Şekil 6'da noktalı çizgi ile gösterildiği gibi faz dönüşümünün bağlantı oranının teorik değeri elde edilir. Simülasyon sonuçları teorik değerlerle iyi bir uyum içindedir, bu da faz dönüşüm alt grafiklerinin boyut dağılımı ve yerleştirme yönteminin uygulanabilirliği hakkındaki sonuçların doğruluğunu kanıtlar.
Yukarıda belirtilen analiz ve deneylere göre, rastgele grafiklerin veya eşler arası özelliklere sahip ağların evrim süreci, Şekil 7'de gösterildiği gibi açıkça tanımlanabilir: Ağın ilk aşaması yalnızca birkaç izole düğüm içerir ve yeni düğümler katılmaya devam ettikçe, bağlantılar yavaş yavaş artar. , Alt grafikler görünür; alt grafikler yavaş yavaş artıyor ve ölçek de genişliyor, ancak bunlar temelde ağaç benzeri yapılar; alt grafiklerin ölçeği artmaya devam ediyor ve önemli sayıda küçük alt grafik ve birkaç nispeten büyük alt grafik var ve alt grafiklerin boyutu güce uyuyor Ağ bir faz geçişine dönüşür; faz geçiş süresi çok kısadır.Birçok alt grafik hızla birbirine bağlı devasa alt grafiklere bağlanır. Büyük bağlantılı alt grafikler genişlemeye devam eder ve küçük alt grafikler hala bir ağaç yapısındadır ve kademeli olarak büyük bağlantılı alt grafiklerle birleşir. Orta; Son olarak ağ bağlanır.
4. Sonuç
Gerçek dünyada, rastgele bağlantı özelliklerine sahip, belirli bir dereceye kadar rastgele grafikler olarak soyutlanabilen birçok ağ veya sistem vardır ve rastgele grafik düğümlerinin eş durumundan dolayı, eşler arası ağ araştırmalarında büyük öneme sahiptir. Geleneksel rastgele grafik teorisi, ağ evrimi sürecindeki bağlantı, özellikle düğüm düzeyinde bağlantı üzerine çok az araştırmaya sahiptir. Bu yazıda, rastgele grafiklerin bağlanabilirlik oranı araştırması yoluyla, rastgele grafiklerin bağlanabilirlik oranının hesaplama yöntemi verilmiş; küçük alt grafiklerde sapma olmadığı hipotezi ve doğrulanması yoluyla, rastgele grafiklerde ağaç yapılarının yaygın varlığını; ayrıca deneylerle açıklamaktadır. Faz geçişinin alt grafiğinin boyutunun güç yasası dağılımını karşıladığı bulundu ve doğrulandı ve rastgele grafiğin evrim sürecini, yani aynı boyuttaki alt grafiğin durumunu, geçici fazı ve bir güç yasası dağılımına sahip devasa bir bağlı alt grafiğin varlığını daha açık bir şekilde özetledi. Ve genişleyen durum, bağlantılı durum. Bu makalenin araştırma sonuçları, gerçek ağlar için, özellikle de eşler arası ağların araştırılması, planlanması ve inşası için büyük önem taşımaktadır. Bununla birlikte, bu makalede hala birçok eksiklik var.Örneğin, bağlantı oranının tanımının basitliği, hesaplamada belirsiz faktörler getirebilir, bu da rastgele grafiğin gelişimindeki diğer önemli özellikleri maskeleyebilir; rastgele grafik faz değişiminin alt grafiğinin boyutuna uydurma Belli bir hata var. Bağlantı oranı hesaplamasının diğer ağ modellerine nasıl genişletileceği ve iletişim ağları gibi deneysel araştırmalara nasıl etkin bir şekilde uygulanacağı, araştırmanın bir sonraki aşamasının yönüdür.
Referanslar
[1] ERDS P, RNYI A. Rastgele grafiklerde J. Publ Math Debrecen, 1959 (6): 1-14.
2 ACHLIOPTAS D, DSOUZA R M, SPENCER J. Rastgele ağlarda patlayıcı süzülme J. Science, 2009, 323 (5920): 1453-1455.
3 KADUSHIN C. Sosyal ağları anlamak: teoriler, kavramlar ve finding M bulmak Oxford University Press, ABD, 2012
4 BALTHROP J, FORREST S, NEWMAN M E J, vd. Teknolojik ağlar ve bilgisayar virüslerinin yayılması J. Science, 2004, 304 (5670): 527-529.
5 Xiong Wei, Li Qingquan. Otoyol sahnesindeki araçlar için kendi kendini organize eden ağın düğüm derecesi J. Elektronik ve Bilgi Dergisi, 2010, 32 (9): 2033-2038.
6 KRAPIVSKY P L, REDNER S, LEYVRAZ F. Büyüyen rastgele ağların bağlanabilirliği J. Phys.Rev. Lett., 2000,85 (21): 4629-4632.
7 BOLLOBS B. Rastgele grafikler M. 2. Cambridge University Press, 2001.
[8] Huang Bin, Wu Chunwang, Zheng Fenghua ve diğerleri Karmaşık ağlarda rastgele grafik modelleri üzerine araştırma J Bilgisayar Mühendisliği ve Bilimi, 2014, 36 (7): 1377-1383.
9 NEWMAN M E J, STROGATZ S H, WATTS D J. Rastgele derece dağılımlı rastgele grafik ve uygulamaları J. Phys. Rev. E, 2001, 64 (22): 359-382.
[10] Lu Youjun, Xu Daoyun. Kgroup'un rasgele grafik G (n, p) J in. Journal of Guizhou University (Natural Science Edition), 2013, 30 (6): 86-90'daki faz geçiş özellikleri.
11 Tan Li, Hou Zhenting Bir çeşit ölçeksiz rasgele grafiğin derece dizisi J. Journal of Applied Mathematics, 2011, 34 (3): 440-447.
[12] Wang Xiaofan, Li Xiang, Chen Guanrong Karmaşık ağ teorisi ve uygulaması M Pekin: Tsinghua University Press, 2006.
13 MILGRAM S. Küçük dünya sorunu J. Psychology Today, 1967,2 (1): 185-195.
14 NEWMAN M E J, WATTS D J, STROGATZ S H.Sosyal ağların rastgele grafik modelleri C. Amerika Birleşik Devletleri Ulusal Bilimler Akademisi'nin Bildirileri, 2002, 99: 2566-2572.
[15] Wang Bin. Rastgele grafiklerde iki faz geçişi D Tianjin: Nankai Üniversitesi, 2011.
16 MOLLOY M, REED B, MOLLOY M. Sabit dereceli bir dizide rastgele bir grafiğin en büyük bileşeninin boyutu J. Combinatorica, 1998, 7 (3): 295-305.
AET üyeleri için yıl sonu avantajları!
