İçeriğe atla
Arama sonuçlarına dön

Ağırlıklı Aradalık Merkeziyeti

Ortaya koyan
Opsahl, T.; Agneessens, F.; Skvoretz, J. (extending Freeman 1977 and Brandes 2001)
Yıl
2010
Tür
Centrality measure (path-based)
Aile
Network science

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Ağırlıklı Aradalık Merkeziyeti, kenar ağırlıklı çizelgeler için Freeman'ın aradalık ölçüsünü, kenar ağırlıklarının ayarlanabilir bir dönüşümü aracılığıyla en kısa yolları yönlendirerek genişletir.

Çok sayıda yüksek değerli en kısa yol üzerinde bulunan düğümler yüksek puanlar alır ve bağ gücünün önemli olduğu sosyal, biyolojik ve bilgi ağlarındaki aracılar ve köprüleri tanımlar.

Yöntemin mantığı

Trafik kapasiteleri farklı olan bir şehir hayal edin. En etkili kavşaklar sadece çok sayıda yola sahip olanlar değil, aynı zamanda birçok konum çifti arasındaki en hızlı veya en yüksek kapasiteli rotalar üzerinde bulunanlardır. Ağırlıklı aradalık merkeziyeti tam olarak bunu yakalar: aracılık eden kritik röle noktaları olarak hizmet veren, üzerlerinden geçen bağlantıların ne kadar güçlü veya zayıf olduğunu hesaba katan düğümleri bulur. Yüksek ağırlıklı aradalığa sahip bir düğüm, kaldırılması birçok güçlü yolu bozacak bir köprü veya kapı bekçisidir.

Tarih

Aradalık merkeziyeti, Linton Freeman tarafından 1977'de düğümlerin başkalarını en kısa yollar aracılığıyla bağlamadaki rolünü ölçmek için tanıtıldı. Ulrik Brandes, 2001 yılında hesaplamayı ağırlıksız çizelgeler için O(n^3)'ten O(n + m)'ye düşüren dönüm noktası niteliğinde verimli bir algoritma geliştirdi. Ağırlıklı uzantı, 2001 yılında Opsahl, Agneessens ve Skvoretz tarafından sistematik olarak biçimlendirildi; onlar alfa parametreli ağırlık-mesafe dönüşümünü önerdiler ve bunu ampirik işbirliği ve havayolu ağlarına karşı doğruladılar.

Ne zaman kullanılır?

Kenar ağırlıklarının anlamlı bağ gücünü (iletişim sıklığı, akış hacmi, işbirliği yoğunluğu, benzerlik) temsil ettiği ve bir ağdaki aracılar, kapı bekçileri veya tek hata noktalarını belirlemek istediğinizde ağırlıklı aradalık merkeziyetini kullanın. Bağlantıların gücünün aslında hangi rotaların kullanıldığını şekillendirdiği sosyal ağlar, işbirliği ağları, ulaşım ağları ve biyolojik yollar için uygundur. Kenar ağırlıklarının gürültülü veya keyfi olduğu durumlarda bundan kaçının - bu durumda düz aradalık merkeziyeti daha güvenlidir. Ayrıca çok büyük ağlar (milyonlarca düğüm) için yaklaşık algoritmalar olmadan bundan kaçının, çünkü en kötü durumda kesin hesaplama O(n^3)'tür.

Sınırlar ve dikkat edilmesi gerekenler

  • Yoğun çizelgeler için uzay ve zamanda kesin hesaplama O(n^3)'tür, bu da ölçeklenebilirliği çok büyük ağlarla sınırlar.
  • Sonuçlar alfa seçimine duyarlıdır; farklı değerler düğümlerin sıralamasını önemli ölçüde değiştirebilir.
  • Bilgi veya etkinin yalnızca jeodezik (en kısa) yollar boyunca aktığı varsayılır, bu da gerçek yayılma süreçlerini yansıtmayabilir.
  • Negatif veya sıfır kenar ağırlıkları özel işlem gerektirir ve en kısa yol algoritmalarını bozabilir.
  • Bağlantısız ağlar, farklı bileşenlerdeki çiftler için tanımsız aradalık üretir, bu da bileşen düzeyinde analiz gerektirir.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Bağ gücünün hangi yolların tercih edildiğini belirlediği ağlarda aracılığı ve kontrolü yakalar.
  • Alfa ayar parametresi, analistlerin ağırlıksız ve tam ağırlıklı yol mantığını harmanlamasına olanak tanır, bu da ölçüyü uyarlanabilir hale getirir.
  • Kaldırılmasının ağı parçalayacağı veya yavaşlatacağı darboğaz düğümlerini doğrudan tanımlar.
  • Hesaplamayı on binlerce düğüme sahip ağlar için uygulanabilir hale getiren Brandes'in verimli algoritmasıyla uyumludur.
  • Normalleştirilmiş puanlar farklı boyutlardaki ağlar arasında yorumlanabilir.
  • Geniş atıf alan, hakemli bir genelleştirme çerçevesine (Opsahl vd. 2010) iyi dayanır.

Uygulama alanları

  • Organizasyonel ve işbirliği ağlarında bilgi aracılarının ve sınır tarayıcılarının belirlenmesi.
  • Direnç analizi için iletişim veya tedarik zinciri ağlarındaki kritik röle düğümlerinin yerinin belirlenmesi.
  • Ulaşım ağlarında şehirlerarası trafiğin çoğunu taşıyan ana havalimanlarının veya aktarma istasyonlarının bulunması.
  • Protein-etkileşim veya gen-düzenleyici ağlardaki düzenleyici darboğazların tespiti.
  • Ağırlıklı salgın veya bilgi yayılma modellerinde etkili yayıcıların belirlenmesi.
  • Ağırlıklı ortak yazarlık ve atıf ağlarında topluluk düzeyinde aracılık analizi.

Nasıl çalışır?

Nasıl çalışır?

1

Kenar ağırlıkları, bir ayar parametresi alfa tarafından kontrol edilen ters bir dönüşüm kullanılarak mesafelere dönüştürülür. Alfa sıfıra eşit olduğunda ölçü standart ağırlıksız aradalığa indirgenir; alfa bire doğru arttıkça, daha güçlü bağlar daha kısa ve dolayısıyla tercih edilen yollar olarak kabul edilir, bu da ölçüyü bağ gücüne duyarlı hale getirir.

Formül
d_{ij} = w_{ij}^{-\alpha}, \; \alpha \in [0,1]
2

Dijkstra algoritması (veya verimlilik için Brandes'in lineer cebir varyantı), ağırlıklandırma yapılandırması göz önüne alındığında hangi rotaların jeodezik olarak en uygun olduğunu belirleyen bu adımı kullanarak, dönüştürülmüş mesafeleri kullanarak ağdaki her kaynak ve hedef düğüm çifti arasındaki en kısa ağırlıklı yollar kümesini hesaplar.

3

Her sıralı düğüm çifti için algoritma, en kısa ağırlıklı yolların toplam sayısını ve bu yolların her bir aday düğüm v'den geçen alt kümesini sayar. Bu sayımlar, algoritmayı orta büyüklükteki ağlar için izlenebilir tutan Brandes'in geri yayılma tekniği kullanılarak verimli bir şekilde biriktirilir.

4

Her düğüm v için ham aradalık puanı, tüm kaynak-hedef çiftleri üzerinden v'den geçen en kısa yollarının kesri toplamıdır. Bir çift arasındaki tüm en kısa yollar üzerinde bulunan bir düğüm, o çift için puanına 1.0 katkıda bulunur; tüm yollar tarafından atlanan bir düğüm 0 katkıda bulunur.

Formül
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}
5

Ham puanlar, puanların [0, 1] aralığında düşmesi ve farklı boyutlardaki ağlar arasında karşılaştırılabilir olması için maksimum olası değere - yönlendirilmemiş ağlar için (n-1)(n-2)/2 - bölünür. Yönlendirilmiş ağlar için payda (n-1)(n-2) olarak ikiye katlanır.

Formül
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}

Sık yapılan hatalar

  • Varsayılan alfayı raporlamadan veya değerini gerekçelendirmeden kullanmak - her zaman alfa seçiminizi belirtin ve gerekçelendirin.
  • Farklı boyutlardaki ağlar arasında karşılaştırılabilir ham (normalleştirilmemiş) puanları yorumlamak.
  • Yönlendirilmiş ağlardaki kenarların yönünü göz ardı etmek ve bunun yerine yönlendirilmemiş aradalığı hesaplamak.
  • Yüksek aradalığı yüksek etki olarak yorumlamak, akışların aslında alandaki en kısa yolları izleyip izlemediğini dikkate almadan.
  • Bağlantısız bileşenleri kontrol etmeyi unutmak, bu da daha küçük bileşenlerdeki düğümler için aradalık puanlarını yapay olarak düşürür.

Sık sorulan sorular

Alfa parametresini nasıl seçerim?

Alfa, ağırlığın yol seçimini ne kadar etkilediğini kontrol eder. Alfa=0'da klasik ağırlıksız aradalığı elde edersiniz; alfa=1'de daha güçlü bağlar en kısa yolları tam olarak tanımlar. Yaygın bir uygulama, alfa=0, 0.5 ve 1'i test etmek ve hassasiyeti raporlamaktır. Düğüm sıralamaları değerler arasında kararlıysa, herhangi bir seçim savunulabilir; önemli ölçüde farklılık gösteriyorsa, güçlü bağların tercih edilmesi gerekip gerekmediğine dayanarak teorik olarak seçiminizi gerekçelendirin.

Ağırlıklı ve ağırlıksız aradalık merkeziyeti arasındaki fark nedir?

Ağırlıksız aradalık sıçramaları sayar; her kenarın aynı uzunluğu vardır. Ağırlıklı aradalık, kenar ağırlıklarını (mesafelere dönüştürülmüş) kullanır, böylece yollar öncelikli olarak daha güçlü veya daha kısa bağlantıları takip eder. Bağ gücünün esasen anlamlı olduğu ağlarda - işbirliği sıklığı veya ticaret hacmi gibi - ağırlıklı versiyon, hangi düğümlerin gerçek akışları kontrol ettiğine dair daha doğru bir resim verir.

Ağırlıklı aradalık merkeziyeti çok büyük ağlar için uygun mudur?

Kesin hesaplama, yaklaşık 100.000 düğümün üzerinde maliyetli hale gelir. Çok büyük ağlar için, rastgele pivot örnekleme (NetworkX'te k parametresiyle betweenness_centrality olarak uygulanır) gibi yaklaşık algoritmalar kullanın veya cuGraph gibi GPU hızlandırmalı araçlardan yararlanın. Kesin veya yaklaşık hesaplama kullanıp kullanmadığınızı bildirin.

Ağımda izole düğümler veya birden fazla bileşen olduğunda ağırlıklı aradalığı kullanabilir miyim?

Evet, ancak izole düğümler her zaman sıfır puana sahip olacaktır ve küçük bileşenlerdeki düğümler yalnızca kendi bileşenleri içindeki yollara dayalı puanlara sahip olacaktır. Bileşen içi sıralamaları istiyorsanız bileşen başına aradalığı ayrı ayrı hesaplayın ve bileşen yapısını puanların yanında bildirin.

Ağırlıklı aradalık merkeziyetini bir makalede nasıl raporlamalıyım?

Kullanılan yazılımı ve sürümü (örneğin, NetworkX, igraph), alfa değerini, puanların normalleştirilip normalleştirilmediğini, bağlantısız bileşenleri nasıl ele aldığınızı ve puanların yanında bir özet istatistiği (ortalama, aralık) bildirin. Derece-aradalık saçılım grafiği veya düğüm boyutu puana orantılı bir ağ görselleştirmesi yorumlamaya yardımcı olur.

İlgili yöntemler

Kaynaklar

  1. Opsahl, T., Agneessens, F., & Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks, 32(3), 245–251.

    DOI kaynağını aç
    Kopyalandı.
  2. Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.

    DOI kaynağını aç
    Kopyalandı.