Verimlilik (ağ bilimi) - Efficiency (network science)

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 kapatma homofili geçişlilik tercihli ek denge teorisi ağ etkisi Sosyal etki
Ağ türleri
Bilgi (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 klik Bileşen Kesmek Çevrim Veri yapısı Köşe Döngü Komşu Yol tepe noktası Komşuluk listesi  / matrisi İnsidans listesi  / matrisi Türler iki parçalı Tamamlayınız yönlendirilmiş Aşırı Çok Rastgele Ağırlıklı
Metrikler algoritmalar
merkezilik Derece motif kümeleme Derece dağılımı asortivite Mesafe modülerlik Yeterlik
Modeller
topoloji rastgele grafik Erdős–Rényi Barabasi-Albert Spor modeli Watt – Strogatz Üstel rastgele (ERGM) Rastgele geometrik (RGG) Hiperbolik (HGN) Hiyerarşik stokastik blok blok modelleme maksimum entropi Yumuşak yapılandırma LFR Kıyaslaması dinamikler Boole ağı ajan bazlı Salgın / SIR
Listeler Kategoriler
Konular Yazılım ağ bilimciler Kategori:Ağ teorisi Kategori:Grafik teorisi
v T e

Gelen ağ bilimi , verimlilik a ağının bu bilgi alışverişi yöntemleri verimli bir ölçüsüdür ve aynı zamanda denir iletişim etkinliği . Temel fikir (ve ana varsayım), ağdaki iki düğüm ne kadar uzaksa, iletişimlerinin o kadar az verimli olacağıdır. Verimlilik kavramı, bir ağda hem yerel hem de küresel ölçeklere uygulanabilir. Küresel ölçekte verimlilik, bilginin eş zamanlı olarak değiş tokuş edildiği tüm ağ boyunca bilgi alışverişini nicelleştirir. Yerel verimlilik, bir ağın başarısızlığa karşı direncini küçük ölçekte ölçer. Bu, bir düğümün yerel verimliliği , kaldırıldığında komşuları tarafından bilginin ne kadar iyi değiş tokuş edildiğini karakterize eder. ${\görüntüleme stili ben}$

Tanım

İletişim verimliliğinin tanımı, verimliliğin uzaklıkla ters orantılı olduğunu varsayar, yani matematiksel olarak

${\displaystyle \epsilon _{ij}={\frac {1}{d_{ij}}}}$

nerede düğümlerin çiftli verimliliktir ağda ve onların olduğu mesafe . ${\displaystyle \epsilon _{ij}}$${\görüntüleme stili i,j\in V}$${\görüntüleme stili G=(V,E)}$${\displaystyle d_{ij}}$

Ortalama iletişim verimliliği ağının daha sonra ikili verimliliğine ortalamayla olarak tanımlanır: ${\görüntüleme stili G}$

${\displaystyle E(G)={\frac {1}{N(N-1)}}\sum _{i\neq j\in V}{\frac {1}{d_{ij}}}}$

nerede ağdaki düğüm sayısını gösterir. ${\görüntüleme stili N=|V|}$

Mesafeler, ağların türüne bağlı olarak farklı şekillerde ölçülebilir. İçin en doğal mesafe ağırlıksız ağları olan en kısa yol uzunluğu bir düğümler arasında ve arasında, örneğin, bir kısa yol düşük kenarlarının sayısı ve kenarlarının sayısı, uzunluğu olan bir yol. Gözlemleyin ki eğer o zaman -ve yolu üzerinde toplamı bitti olduğunu - orada bağlayan hiçbir yolu ise ederken ve , ve bunların ikişerli verimliliği sıfırdır. Bir sayı olmak , for ve so , 0 ile 1 arasında sınırlandırılmıştır, yani normalleştirilmiş bir tanımlayıcıdır. ${\görüntüleme stili ben}$${\görüntüleme stili j}$${\görüntüleme stili ben,j}$${\görüntüleme stili i=j}$${\displaystyle d_{ij}=0}$${\görüntüleme stili i\neq j}$${\görüntüleme stili ben}$${\görüntüleme stili j}$${\displaystyle d_{ij}=\infty}$${\displaystyle d_{ij}}$${\görüntüleme stili i\neq j}$ ${\displaystyle d_{ij}\geq 1}$${\görüntüleme stili E(G)}$

Ağırlıklı ağlar

En kısa yol mesafesi ayrıca ağırlıklı ağlara genelleştirilebilir, bkz. ağırlıklı en kısa yol mesafesi , ancak bu durumda ve farklı ağlar arasında karşılaştırılabilir olması için ortalama iletişim verimliliğinin uygun şekilde normalleştirilmesi gerekir. ${\displaystyle d_{ij}^{W}\in [0,+\infty ]}$

Yazarlar, onu ağın idealize edilmiş bir versiyonunun verimliliği ile bölmeyi normalleştirmeyi önerdi : ${\görüntüleme stili E(G)}$${\görüntüleme stili G}$

${\displaystyle E_{\text{glob}}(G)={\frac {E(G)}{E(G^{\text{ideal}})}}.}$

${\displaystyle G^{\metin{ideal}}}$tüm olası kenarların mevcut olduğu düğümler üzerindeki "ideal" grafiktir . Ağırlıksız durumda her kenarın birim ağırlığı vardır, bir kliktir , tam bir ağdır ve . Kenarları ağırlıklı zaman, (uygun bir normalleşme, yani olması için bu tek başına yeterli bu kez adı doğru ağ mesafelerde), olduğu ${\görüntüleme stili N}$${\displaystyle G^{\metin{ideal}}}$${\displaystyle E(G^{\metin{ideal}})=1}$${\displaystyle E_{\text{glob}}(G)\in [0,1]}$${\displaystyle l_{ij}}$

${\displaystyle l_{ij}\leq d_{ij}}$

için . tüm düğüm çiftleri için bilinmelidir (ve sıfırdan farklı). Yaygın bir seçim coğrafi veya fiziksel mesafeler olarak almaktır mekansal ağlar veya örneğin tüm bağlantılar üzerinde maksimum maliyet olarak ağda maksimum etkileşim gücünü gösterir. Bununla birlikte, yazarlar, heterojen yapı ve akışlarla karakterize edilen gerçek dünya ağlarıyla uğraşırken bu seçimlerin konularını vurgulamaktadır. Örneğin, seçim yapmak, küresel ölçüyü, ağırlıkların dağılımındaki aykırı değerlere karşı çok hassas hale getirir ve bir ağın gerçek verimliliğini küçümseme eğilimi gösterir. Yazarlar ayrıca bir normalleştirme prosedürü, yani istatistiksel olarak sağlam ve fiziksel olarak temellendirilmiş kenar ağırlıklarında bulunan (ve coğrafi mesafeler gibi başka meta-verileri olmayan) tüm ve yalnızca bilgileri kullanarak bir bina oluşturmak için bir yol önermektedir . ${\görüntüleme stili i,j=1,...,N}$${\displaystyle l_{ij}}$${\displaystyle l_{ij}={\frac {1}{w_{\max }}}}$${\displaystyle w_{\max }}$${\displaystyle l_{ij}={\frac {1}{w_{\max }}}}$${\displaystyle G^{\metin{ideal}}}$

Verimlilik ve küçük dünya davranışı

Ağın küresel verimliliği, yalnızca ortalama yol uzunluğunun kendisinden ziyade, ile karşılaştırılabilir bir ölçüdür . Temel ayrım, ağda yalnızca bir bilgi paketinin taşındığı bir sistemde verimliliği ölçerken, paralel iletişimin, yani tüm düğümlerin aynı anda birbirleriyle bilgi paketleri alışverişinde bulunduğu durumlarda verimliliği ölçmesidir. ${\görüntüleme stili 1/L}$ ${\görüntüleme stili L}$${\görüntüleme stili 1/L}$${\displaystyle E_{\metin{glob}}(G)}$

Bir ağın kümeleme katsayısına alternatif olarak, ikili iletişim verimliliklerinin yerel ortalaması kullanılabilir . Yerel etkinliği bir ağın olarak tanımlanır: ${\görüntüleme stili N}$

${\displaystyle E_{loc}(G,i)={\frac {1}{N}}\sum _{i\in G}E(G_{i})}$

düğümün kendisinden değil, yalnızca bir düğümün yakın komşularından oluşan yerel alt grafik nerede . ${\görüntüleme stili G_{i}}$${\görüntüleme stili ben}$${\görüntüleme stili ben}$

Uygulamalar

Genel olarak konuşursak, bir ağın verimliliği, ağlardaki küçük dünya davranışını ölçmek için kullanılabilir . Verimlilik, ağırlıklı ve ağırlıksız ağlarda maliyet etkin yapıları belirlemek için de kullanılabilir . Bir ağın ne kadar ekonomik olarak kurulduğunu görmek için bir ağdaki iki verimlilik ölçüsünü aynı büyüklükteki rastgele bir ağla karşılaştırmak. Ayrıca, küresel verimliliğin sayısal olarak kullanımı, karşılığı olan yol uzunluğuna göre daha kolaydır.

Bu nedenlerle verimlilik kavramı, ağ biliminin birçok farklı uygulamasında kullanılmıştır. Verimlilik, ulaşım ağları ve iletişim ağları gibi insan yapımı ağların analizinde faydalıdır. Belirli bir ağ yapısının ne kadar düşük maliyetli olduğunu ve hataya ne kadar dayanıklı olduğunu belirlemeye yardımcı olmak için kullanılır. Bu tür ağlarla ilgili çalışmalar, kaynakların iyi kullanımını, ancak düşük yerel verimliliği ima eden yüksek küresel verimliliğe sahip olma eğiliminde olduklarını ortaya koymaktadır. Bunun nedeni, örneğin, bir metro ağının kapalı olmaması ve ağdaki belirli bir hat kapalı olsa bile, örneğin otobüslerle yolcuların yeniden yönlendirilebilmesidir.

İnsan yapımı ağların ötesinde, verimlilik, fiziksel biyolojik ağlardan bahsederken yararlı bir ölçüdür. Biyolojinin herhangi bir alanında, kaynak kıtlığı kilit bir rol oynar ve biyolojik ağlar da bir istisna değildir. Verimlilik, sinirbilimde , fiziksel alan ve kaynak kısıtlamalarının önemli bir faktör olduğu sinir ağları arasında bilgi transferini tartışmak için kullanılır . Verimlilik, genellikle geniş odalardan ve birçok genişleyen tünelden oluşan karınca kolonisi tünel sistemlerinin çalışmasında da kullanılmıştır . Karınca kolonilerine yapılan bu uygulama çok şaşırtıcı değil çünkü bir koloninin geniş yapısı, başta gıda olmak üzere çeşitli kaynaklar için bir ulaşım ağı görevi görmelidir.

Referanslar