Arasındalık merkeziliği - Betweenness centrality

En küçükten (kırmızı) en büyüğe (mavi) her bir tepe noktasının arasındaki merkeziyete dayalı olarak renklendirilen yönsüz bir grafik .

Olarak grafik teorisi , betweenness dışmerkezlik (veya "betweeness dışmerkezlik") bir ölçüsüdür merkezî bir de grafik göre en kısa yol . Bağlı bir grafikteki her bir köşe çifti için, köşeler arasında en az bir en kısa yol vardır, öyle ki ya yolun geçtiği kenar sayısı (ağırlıksız grafikler için) veya kenarların ağırlıklarının toplamı (ağırlıklı grafikler için) ) en aza indirilir. Her tepe noktası için aradalık merkeziliği, tepe noktasından geçen bu en kısa yolların sayısıdır.

Arasındalık merkeziliği, genel bir merkezilik ölçüsü olarak tasarlandı: sosyal ağlar , biyoloji, ulaşım ve bilimsel işbirliği ile ilgili problemler de dahil olmak üzere ağ teorisindeki çok çeşitli problemler için geçerlidir . Daha önceki yazarlar, merkeziliği sezgisel olarak arasındalık temelli olarak tanımlamış olsalar da, Freeman (1977) arasındalık merkeziyetinin ilk resmi tanımını verdi.

Arasındalık merkeziliği, ağ teorisinde geniş uygulama alanı bulur ; düğümlerin birbirleri arasında durma derecesini temsil eder. Örneğin, bir telekomünikasyon ağında , arasındalık merkeziliği daha yüksek olan bir düğüm, ağ üzerinde daha fazla kontrole sahip olacaktır, çünkü bu düğümden daha fazla bilgi geçecektir.

Tanım

Bir düğümün aradalık merkeziliği şu ifadeyle verilir: ${\görüntüleme stili v}$

${\displaystyle g(v)=\sum _{s\neq v\neq t}{\frac {\sigma _{st}(v)}{\sigma _{st}}}}$

burada düğümünden kısa yolların toplam sayısıdır düğüme ve geçen bu yollar sayısıdır . ${\displaystyle \sigma _{st}}$${\görüntüleme stili s}$${\görüntüleme stili t}$${\displaystyle \sigma _{st}(v)}$${\görüntüleme stili v}$

Bir düğümün arasındalık merkeziliğinin, toplama endeksleri tarafından önerildiği gibi düğüm çiftlerinin sayısıyla ölçeklendiğine dikkat edin. Bu nedenle, hesaplama, içermeyen düğüm çiftlerinin sayısına bölünerek yeniden ölçeklendirilebilir , böylece . Bölme, yönlendirilmiş grafikler için ve dev bileşendeki düğüm sayısı olan yönsüz grafikler için yapılır . Bunun, bir düğümün her bir en kısa yoldan geçtiği mümkün olan en yüksek değer için ölçeklendiğini unutmayın. Bu genellikle böyle değildir ve bir normalleştirme, hassasiyet kaybı olmadan gerçekleştirilebilir. ${\görüntüleme stili v}$${\displaystyle g\in [0,1]}$${\görüntüleme stili (N-1)(N-2)}$${\görüntüleme stili (N-1)(N-2)/2}$${\görüntüleme stili N}$

${\displaystyle {\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}}$

hangi sonuçlanır:

${\görüntüleme stili \max(normal)=1}$

${\görüntüleme stili \min(normal)=0}$

Bunun her zaman daha küçük bir aralıktan daha geniş bir aralığa ölçeklendirme olacağını ve bu nedenle hassasiyet kaybı olmayacağını unutmayın.

Ağırlıklı ağlar

Ağırlıklı bir ağda, düğümleri birbirine bağlayan bağlantılar artık ikili etkileşimler olarak ele alınmaz, ancak kapasitelerine, etkilerine, frekanslarına vb. orantılı olarak ağırlıklandırılır, bu da ağ içinde topolojik etkilerin ötesinde başka bir heterojenlik boyutu ekler. Ağırlıklı bir ağdaki bir düğümün gücü, bitişik kenarlarının ağırlıklarının toplamı ile verilir.

${\displaystyle s_{i}=\sum _{j=1}^{N}a_{ij}w_{ij}}$

Sırasıyla düğümler ve arasında bitişiklik ve ağırlık matrisleri ile ve olmak . Ölçeksiz ağlarda bulunan derecenin güç yasası dağılımına benzer şekilde, belirli bir düğümün gücü de bir güç yasası dağılımını takip eder. ${\displaystyle a_{ij}}$${\displaystyle w_{ij}}$${\görüntüleme stili ben}$${\görüntüleme stili j}$

${\görüntüleme stili s(k)\yaklaşık k^{\beta}}$

Aradalıklı köşeler için ortalama gücün değeri üzerine yapılan bir çalışma , fonksiyonel davranışın bir ölçekleme formuyla yaklaşık olarak tahmin edilebileceğini göstermektedir: ${\görüntüleme stili s(b)}$${\görüntüleme stili b}$

sızma merkeziliği

Sızma merkeziliği, ağırlıklı arasındalık merkeziliğinin bir versiyonudur, ancak bu ağırlığı hesaplarken her en kısa yolun kaynak ve hedef düğümlerinin 'durumunu' dikkate alır. Bir 'bulaşma'nın sızması, bir dizi senaryoda karmaşık ağlarda meydana gelir. Örneğin, viral veya bakteriyel enfeksiyon, iletişim ağları olarak bilinen insanların sosyal ağlarına yayılabilir. Hastalığın yayılması, karayolu, demiryolu veya hava bağlantıları ile birbirine bağlı bir kasabalar veya nüfus merkezleri ağı düşünülerek daha yüksek bir soyutlama düzeyinde de düşünülebilir. Bilgisayar virüsleri bilgisayar ağları üzerinden yayılabilir. İş teklifleri ve anlaşmaları hakkında söylentiler veya haberler, insanların sosyal ağları aracılığıyla da yayılabilir. Tüm bu senaryolarda, bir "bulaşma", karmaşık bir ağın bağlantıları üzerinden yayılır ve yayılırken düğümlerin "durumlarını", kurtarılabilir veya başka bir şekilde değiştirir. Örneğin, epidemiyolojik bir senaryoda, enfeksiyon yayıldıkça bireyler 'duyarlı' durumdan 'enfekte' duruma geçerler. Bireysel düğümlerin yukarıdaki örneklerde alabileceği durumlar ikili (bir haber alındı/alınmadı gibi), ayrık (hassas/enfekte/kurtarıldı) veya hatta sürekli (bir kasabadaki enfekte kişilerin oranı gibi) olabilir. ), bulaşma yayıldıkça. Tüm bu senaryolardaki ortak özellik, bulaşmanın yayılmasının ağlardaki düğüm durumlarının değişmesine neden olmasıdır. Sızma merkeziliği (PC) bu akılda tutularak önerildi ve bu, özellikle ağ üzerinden sızmaya yardımcı olmak açısından düğümlerin önemini ölçtü. Bu önlem Piraveenan, Prokopenko & Hossain (2013) tarafından önerilmiştir .

Percolation merkeziliği, belirli bir düğüm için, belirli bir zamanda, o düğümden geçen 'süzülmüş yolların' oranı olarak tanımlanır. 'Süzülen yol', kaynak düğümün süzüldüğü (örneğin, virüs bulaştığı) bir çift düğüm arasındaki en kısa yoldur. Hedef düğüm, süzülmüş veya süzülmemiş olabilir veya kısmen süzülmüş durumda olabilir.

${\displaystyle PC^{t}(v)={\frac {1}{N-2}}\sum _{s\neq v\neq r}{\frac {\sigma _{sr}(v)} {\sigma _{sr}}}{\frac {{x^{t}}_{s}}{{\sum {[{x^{t}}_{i}}]}-{x^{ televizyon}}}}$

burada düğümünden kısa yolların toplam sayısıdır düğüme ve geçen bu yollar sayısıdır . Düğümün o andaki süzülme durumu ile gösterilir ve iki özel durum, o sırada süzülmemiş bir durumu belirtirken , hangisinin o sırada tam olarak süzülmüş bir durumu gösterdiği zamandır . Aradaki değerler kısmen süzülmüş durumları gösterir (örneğin, bir ilçeler ağında bu, o kasabada enfekte olan kişilerin yüzdesi olacaktır). ${\displaystyle \sigma _{sr}}$${\görüntüleme stili s}$${\görüntüleme stili r}$${\displaystyle \sigma _{sr}(v)}$${\görüntüleme stili v}$${\görüntüleme stili ben}$${\görüntüleme stili t}$${\ Displaystyle {x^{t}}_{i}}$${\displaystyle {x^{t}}_{i}=0}$${\görüntüleme stili t}$${\ Displaystyle {x^{t}}_{i}=1}$${\görüntüleme stili t}$

Sızma yollarına eklenen ağırlıklar, bir kaynak düğümün süzülme düzeyi ne kadar yüksek olursa, o düğümden kaynaklanan yolların o kadar önemli olduğu öncülüne dayanarak, kaynak düğümlere atanan süzülme düzeylerine bağlıdır. Bu nedenle, yüksek oranda süzülmüş düğümlerden kaynaklanan en kısa yollarda bulunan düğümler, potansiyel olarak süzülme için daha önemlidir. PC'nin tanımı, hedef düğüm ağırlıklarını da içerecek şekilde genişletilebilir. Sızma merkezilik hesaplamaları , Brandes'in hızlı algoritmasından uyarlanan verimli bir uygulama ile zamanında çalışır ve hesaplamanın hedef düğüm ağırlıklarını dikkate alması gerekiyorsa, en kötü durum süresi . ${\görüntüleme stili O(NM)}$${\görüntüleme stili O(N^{3})}$

algoritmalar

Bir grafikteki tüm köşelerin arasındalık ve yakınlık merkeziliklerini hesaplamak, bir grafikteki tüm köşe çiftleri arasındaki en kısa yolların hesaplanmasını içerir; bu , Floyd-Warshall algoritması ile zaman alır , yalnızca bir tane bulmakla kalmayıp iki arasındaki en kısa yolları saymak için değiştirilir. düğümler. Seyrek bir grafikte, Johnson'ın algoritması veya Brandes'in algoritması daha verimli olabilir, her ikisi de zaman alır. Ağırlıksız grafiklerde, Brandes'in algoritmasını kullanarak aradalık merkeziliğini hesaplamak zaman alır . ${\displaystyle \Theta (|V|^{3})}$${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$${\displaystyle O(|V||E|)}$

Bir grafikteki tüm köşelerin arasındalık ve yakınlık merkezliklerini hesaplarken, grafiklerin yönsüz olduğu ve döngüler ve çoklu kenarlar payı ile bağlantılı olduğu varsayılır. Özellikle ağ grafikleriyle uğraşırken, grafikler basit ilişkileri sürdürmek için genellikle döngüler veya çoklu kenarlar içermez (burada kenarlar iki kişi veya tepe arasındaki bağlantıları temsil eder). Bu durumda, Brandes'in algoritmasını kullanmak, iki kez sayılan her en kısa yolu hesaba katmak için nihai merkezilik puanlarını 2'ye böler.

Başka bir algoritma, keşif ve sömürü arasındaki değiş tokuşu kontrol eden bir hiper parametre sunarak, Freeman'ın jeodeziklerde hesaplanan arasındalığını ve tüm yollarda hesaplanan Newman'ın arasındalığını genelleştirir. Zaman karmaşıklığı, grafikteki kenar sayısı çarpı düğüm sayısıdır.

İki yönlü genişlik öncelikli arama kullanılarak yolların örneklenmesiyle, aradalık merkezlerinin yaklaşık, olasılıksal bir tahmini çok daha hızlı elde edilebilir .

Uygulamalar

Sosyal ağlar

Gelen sosyal ağ analizi , betweenness merkezilik farklı etkileri olabilir. Makroskopik bir perspektiften, köprüleme konumları veya "yapısal delikler" (yüksek arasındalık merkeziliği ile belirtilir) gücü yansıtır, çünkü köprüleme konumundaki kişinin bağlantı kurduğu kişiler üzerinde kontrol uygulamasına (örneğin, bilgi paylaşıp paylaşmayacağına karar vermesine) izin verirler. arasında. Bununla birlikte, ego ağlarının mikroskobik perspektifinden (yani, yalnızca birinci derece bağlantıları dikkate alarak), çevrimiçi sosyal ağlarda yüksek bir aradalık merkeziliği, en yakın arkadaşların aday gösterilmesiyle (yani, güçlü kişilerarası bağlar ) örtüşür , çünkü sosyal sermaye yatırımlarını ilişkiye yansıtır. uzak sosyal çevreler (örneğin, aile ve üniversite) köprülendiğinde (genellikle ego tarafından yapılan bir girişten kaynaklanır).

Nehir ağları

Betweenness merkeziyet analiz için kullanılmıştır topolojik karmaşıklığı içinde nehir ağlar .

Ilgili kavramlar

Arasındalık merkeziliği , bir ağın bağlanabilirliği ile ilgilidir , yüksek arasındalık köşeleri, kaldırılırsa grafiklerin bağlantısını kesme potansiyeline sahip olduğu kadar (bkz. kesim kümesi ).

Ayrıca bakınız

• merkezilik

Referanslar

bibliyografya