Gelişen ağ - Evolving network

İlk Barabasi-Albert modeline göre gelişen bir ağın animasyonu

Gelişen ağlar , zamanın bir işlevi olarak değişen ağlardır . Neredeyse tüm gerçek dünya ağları, zaman içinde düğümleri veya bağlantıları ekleyerek veya kaldırarak zaman içinde geliştiğinden, bunlar ağ biliminin doğal bir uzantısıdır . Çoğu zaman bu süreçlerin tümü, örneğin insanların zaman içinde arkadaş edindikleri ve kaybettikleri sosyal ağlarda eşzamanlı olarak gerçekleşir , böylece kenarlar oluşur ve yok olur ve bazı insanlar ağdaki düğümleri değiştirerek yeni sosyal ağların parçası olur veya ağlarından ayrılır. Gelişen ağ kavramları, yerleşik ağ teorisine dayanmaktadır ve şimdi birçok farklı alandaki ağları incelemeye dahil edilmektedir.

Ağ teorisi arka planı

Ağların incelenmesi, temellerini , ilk olarak 1736'da Leonhard Euler tarafından ünlü Königsberg'in Yedi Köprüsünü yazdığı zaman analiz edilen grafik teorisinin gelişimine dayandırır . Olasılıksal ağ teorisi daha sonra Paul Erdős ve Alfréd Rényi tarafından yazılan rastgele grafikleri inceleyen sekiz ünlü makalenin yardımıyla geliştirildi . Erdos-Rényi modeli (ER) oluşan bir grafiktir varsayar N düğümlerin her bir çift, bir önceden olasılığı ile bağlandığı yerde düğümleri etiketli p .

Watt-Strogatz grafiği

ER modelinin basitliği birçok uygulamayı bulmasına yardımcı olurken, birçok gerçek dünya ağını doğru bir şekilde tanımlamaz. ER modeli , gerçek dünya ağlarında bulundukları sıklıkta yerel kümeleme ve üçlü kapanışlar oluşturmada başarısız olur . Bu nedenle, Watt ve Strogatz modeli bir ağ normal bir halka kafes olarak inşa edilir ve böylece, teklif edilen ve daha sonra düğümler bir olasılık göre rewired edilir p . Bu, yerel olarak kümelenmiş bir ağ üretir ve ortalama yol uzunluğunu önemli ölçüde azaltır, birçok gerçek dünya ağında gözlemlenen küçük dünya fenomenini temsil eden ağlar oluşturur.

Bu başarıya rağmen, hem ER hem de Watts ve Storgatz modelleri, birçok gerçek dünya ağında gözlemlendiği gibi merkezlerin formülasyonunu açıklamada başarısız oldu. ER modelinde derecesi dağılımı aşağıdaki Poisson dağılımına Watt ve Strogatz modeli olan grafikler üretir iken, homojen olarak derece . Çoğu ağ, bunun yerine ölçeklendirmeden özgürdür, yani derece dağılımlarının bir güç yasasını takip ettiği anlamına gelir :

${\ displaystyle P (k) \ sim k ^ {- \ gamma}}$

Bu üs, birçok gerçek dünya ağı için yaklaşık 3'tür, ancak evrensel bir sabit değildir ve sürekli olarak ağın parametrelerine bağlıdır.

İlk gelişen ağ modeli - ölçeksiz ağlar

Barabási-Albert (BA) modeli, ölçeksiz ağlar üreten ilk yaygın kabul gören modeldi . Bu, düğümlerin zamanla ağa eklendiği ve yüksek dereceli dağılımlara sahip diğer düğümlere bağlanma olasılığının daha yüksek olduğu tercihli bağlanma ve büyümeyi birleştirerek gerçekleştirildi . BA modeli ilk olarak, bu etkilerin her ikisinin de açıkça görülebildiği web üzerindeki derece dağılımlarına uygulandı. Zamanla yeni web sayfaları eklenir ve her yeni sayfanın, yalnızca birkaç bağlantıya sahip düğümlere göre yüksek dereceli dağıtımlara sahip Google gibi oldukça görünür merkezlere bağlanma olasılığı daha yüksektir . Resmi olarak bu tercihli ek şudur:

${\ displaystyle p_ {i} = {\ frac {k_ {i}} {\ displaystyle \ sum _ {j} k_ {j}}},}$

BA modeline eklemeler

BA modeli, ağ topolojisini, zaman içinde eklenen düğümler ve bağlantılarla ağın inşa edilme biçiminden türeten ilk modeldi. Bununla birlikte, model yalnızca ölçeksiz bir ağın ortaya çıkması için gerekli olan en basit varsayımları, yani doğrusal büyüme ve doğrusal tercihli bağlanma olduğunu varsayar. Bu minimal model, derece dağılımının şeklindeki varyasyonları, derece üssündeki varyasyonları veya boyuttan bağımsız kümeleme katsayısını yakalamaz . Bu nedenle, orijinal model birkaç yeni özellik sunarak gelişen ağların özelliklerini daha tam olarak yakalayacak şekilde değiştirildi.

Fitness

BA modeliyle ilgili bir endişe, her düğümün derece dağılımlarının güçlü pozitif geri bildirim almasıdır, bu sayede yüksek dereceli dağılımlara sahip ilk düğümler sonsuza kadar ağa hakim olmaya devam eder. Bununla birlikte, bu, her bir düğüm için yeni bağlantıların yaratılma olasılığını veya hatta bu düğüme giden bağlantıların kaldırılma olasılığını değiştiren bir uygunluk getirilerek hafifletilebilir.

BA modelinden tercihli eki korumak için, bu uygunluk, daha sonra derece dağılımına dayalı tercihli ek ile çarpılarak düğüm i'ye bağlanan bir bağlantının yaratılması gerçek olasılığını verir .

${\ displaystyle \ Pi (k_ {i}) = {\ frac {\ eta _ {i} k_ {i}} {\ displaystyle \ toplamı _ {j} \ eta _ {j} k_ {j}}},}$

Zamana da bağlı olabilen uygunluk nerede . Zamana göre bir uygunluk azalması meydana gelebilir ve aşağıdaki şekillerde resmileştirilebilir: ${\ displaystyle \ eta}$

${\ displaystyle \ Pi (k_ {i}) \ propto k_ {i} (t-t_ {i}) ^ {- \ nu},}$

nerede artar ${\ displaystyle \ gamma}$${\ displaystyle \ nu.}$

Düğümleri kaldırma ve bağlantıları yeniden bağlama

Düğümler bir olasılıkla ağdan kaldırılabildiğinden başka karmaşıklıklar da ortaya çıkar. Ek olarak, mevcut bağlantılar yok edilebilir ve mevcut düğümler arasında yeni bağlantılar oluşturulabilir. Bu eylemlerin gerçekleşme olasılığı zamana bağlı olabilir ve ayrıca düğümün uygunluğuyla ilgili olabilir. Aynı özelliklere sahip bir model ağ oluşturmak için söz konusu ağın özelliklerini inceleyerek bu olaylara olasılıklar atanabilir. Bu büyüme, her adımda aşağıdaki eylemlerden biriyle gerçekleşecektir:

Prob p: dahili bir bağlantı ekleyin.

Sorun q: bir bağlantıyı silin.

Sorun r: bir düğümü silin.

Prob 1-pqr: bir düğüm ekleyin.

Gelişen ağları karakterize etmenin diğer yolları

Yukarıda açıklandığı gibi büyüyen ağ modellerine ek olarak, gelişen ağların belirli özelliklerini karakterize etmek için diğer yöntemlerin daha yararlı veya uygun olduğu zamanlar olabilir.

Dengeye yakınsama

Rekabetçi karar vermenin gerçekleştiği ağ tabanlı sistemlerde, oyun teorisi genellikle sistem dinamiklerini modellemek için kullanılır ve dengeye doğru yakınsama, topolojik evrimin itici gücü olarak düşünülebilir. Örneğin, Kasthurirathna ve Piraveenan, bir sistemdeki bireyler farklı düzeylerde rasyonalite sergilediğinde, genel sistem mantığını iyileştirmenin ölçeksiz ağların ortaya çıkmasının evrimsel bir nedeni olabileceğini göstermiştir. Bunu, bir dizi klasik oyunu simüle eden başlangıçta rastgele bir ağa evrimsel baskı uygulayarak gösterdiler, böylece ağ, yeniden bağlantı kurmasına izin verilirken, ağ Nash dengesine doğru birleşti. Bu işlem sırasında ağlar giderek daha fazla ölçeksiz hale gelir.

Gelişen ağları, statik bir ağın ardışık anlık görüntüleri olarak ele alın

Gelişen ağları görmenin en yaygın yolu, onları ardışık statik ağlar olarak düşünmektir. Bu, bir sinema filmi oluşturan tek tek hareketsiz görüntüler olarak kavramsallaştırılabilir . Statik bir ağı (düğüm sayısı, kenarlar, yol uzunluğu, bağlı bileşenler) tanımlamak veya grafikteki bağlantı sayısı veya kümeleme katsayısı gibi belirli düğümleri tanımlamak için birçok basit parametre mevcuttur. Bu özellikler daha sonra sinyal işleme kavramları kullanılarak bir zaman serisi olarak ayrı ayrı incelenebilir. Örneğin, ağın birbirini izleyen anlık görüntülerine bakarak ve bu bağlantıları her anlık görüntüde sayarak dakika başına bir sunucuya kurulan bağlantı sayısını izleyebiliriz.

Ne yazık ki, anlık görüntülerin bir sinema filmine benzetilmesi, bu yaklaşımdaki ana zorluğu da ortaya koymaktadır: kullanılan zaman adımları, ağ tarafından çok nadiren önerilmektedir ve bunun yerine keyfidir. Her anlık görüntü arasında son derece küçük zaman adımlarının kullanılması çözünürlüğü korur, ancak aslında yalnızca daha uzun zaman ölçeklerinde görünür hale gelen daha geniş eğilimleri gizleyebilir. Tersine, daha büyük zaman ölçekleri kullanmak, her anlık görüntüdeki olayların zamansal sırasını kaybeder. Bu nedenle, bir ağın gelişimini statik anlık görüntülere bölmek için uygun zaman ölçeğini bulmak zor olabilir.

Dinamik özellikleri tanımlayın

Gelişmekte olan ağları, düğümler arasındaki temasların süresi gibi bir anlık görüntü dizisi olarak ele alarak doğrudan gözlemlenemeyen özelliklere bakmak önemli olabilir.Diğer benzer özellikler tanımlanabilir ve daha sonra bu özellikleri evrim yoluyla izlemek mümkündür. bir ağın ve bunları doğrudan görselleştirin.

Ardışık anlık görüntüleri kullanmanın bir başka sorunu, ağ topolojisindeki yalnızca küçük değişikliklerin, toplulukları bulmak için tasarlanmış algoritmaların sonucu üzerinde büyük etkilere sahip olabilmesidir. Bu nedenle, topluluğun evrimini doğum, ölüm, birleşme, bölünme, büyüme ve daralma gibi bir dizi kuralla takip etmeye izin veren klasik olmayan bir topluluk tanımı kullanmak gerekir.

Başvurular

Dünyanın planlanmış ticari havayolu trafiğinin rota haritası, 2009. Bu ağ, yeni rotalar planlandıkça veya iptal edildikçe sürekli olarak gelişmektedir.

Neredeyse tüm gerçek dünya ağları, zaman içinde inşa edildikleri için ağları geliştirmektedir. Yukarıda açıklanan ilgili olasılıkları değiştirerek, gözlemlenen birçok ağ ile hemen hemen aynı özelliklere sahip bir ağ oluşturmak için genişletilmiş BA modelini kullanmak mümkündür. Dahası, ölçeksiz ağlar kavramı bize zaman evriminin ağın özelliklerini anlamanın gerekli bir parçası olduğunu ve mevcut bir ağı anında yaratılmış olarak modellemenin zor olduğunu gösteriyor. Şu anda üzerinde çalışılmakta olan gerçek gelişen ağlar arasında sosyal ağlar , iletişim ağları , internet , film oyuncu ağı , dünya çapında ağ ve ulaşım ağları bulunmaktadır .

daha fazla okuma

• "Ağ Bilimini Anlamak", https://web.archive.org/web/20110718151116/http://www.zangani.com/blog/2007-1030-networkingscience
• "Bağlantılı: Ağların Yeni Bilimi", A.-L. Barabási Perseus Publishing, Cambridge.

Referanslar