Arakesme Merkeziyeti
- Ortaya koyan
- Freeman, L. C.
- Yıl
- 1977
- Tür
- Centrality measure
- Aile
- Network science
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Arakesme merkeziyeti, Linton C. Freeman tarafından 1977'de biçimlendirilmiş olup, bir düğümün ağdaki diğer her düğüm çiftini birbirine bağlayan en kısa yol üzerinde ne sıklıkla bulunduğunu ölçer.
Yüksek arakesme değerine sahip düğümler köprü veya aracılar olarak işlev görür: bu düğümlerin kaldırılması, ağı diğer herhangi bir düğümün kaldırılmasından daha şiddetli bir şekilde bağlantısız bileşenlere ayırır.
Yöntemin mantığı
Tüm şehirlerarası güzergahların tek bir kavşaktan geçtiği bir şehir yol ağı düşünün. Bu kavşağın, yalnızca orta düzeyde sayıda yolu olsa bile maksimum arakesme değeri vardır. Bir sosyal ağda, iki aksi takdirde bağlantısız küme arasında düzenli olarak bilgi aktaran bir kişi aynı konumu işgal eder: doğrudan çok fazla insan tanımayabilir, ancak ağı bir arada tutan kritik yol üzerinde oturur. Arakesme merkeziyeti, ham bağlantı sayısından bağımsız olarak tam olarak bu aracılık rolünü nicelleştirir.
Tarih
Linton Freeman, 1977 tarihli önemli Sosyometri makalesinde arakesme merkeziyetini biçimlendirmiş, Bavelas'ın (1948) iletişim deneylerindeki daha önceki gayri resmi kullanımlarından yararlanmıştır. Freeman'ın formülasyonu, düğüm önemi hakkındaki birkaç gevşek sezgiyi tek bir hesaplanabilir ölçüde birleştirmiş ve ağ biliminde kullanılan kanonik tanım haline gelmiştir. Ulrik Brandes'in 2001 algoritması, hesaplamayı O(V^3)'ten O(VE)'ye düşürerek, arakesme merkeziyetini binlerce düğüme sahip ağlar için pratik hale getirmiş ve sosyal ağ analizi yazılımlarında standart bir araç olarak yerini sağlamlaştırmıştır.
Ne zaman kullanılır?
Araştırma sorunuz aracılık, kapıcılık veya köprü düğümleri - bilgi akışını veya ağ uyumunu bozacak aktörlerin kaldırılmasıyla ilgili olduğunda arakesme merkeziyetini kullanın. Yönlendirilmemiş ve yönlendirilmiş graflar için ve kenar ağırlıklarının mesafeyi veya maliyeti temsil ettiği ağırlıklı graflar için uygundur. Özellikle iletişim ağları, atıf ağları, işbirliği grafikleri ve tedarik zincirlerinde değerlidir. Aracılığın teorik odak noktası olmadığı durumlarda tek merkeziyet ölçüsü olarak kullanmayın: derece merkeziyeti daha basittir ve saf bağlantı soruları için yeterlidir ve özvektör veya PageRank merkeziyeti prestij yayılımını daha iyi yakalar. Verimli bir uygulama olmadan çok büyük seyrek ağlar için bundan kaçının, çünkü kaba hesaplama O(V^2 E)'dir.
Sınırlar ve dikkat edilmesi gerekenler
- Brandes algoritması ile bile çok yoğun ağlarda hesaplama açısından pahalıdır; web ölçeğindeki graflar için yaklaştırma algoritmaları gerekebilir.
- Akışların daha uzun rotaları (örneğin, elektrik ağlarındaki rastgele yürüyüşler) izlediği ağlarda gerçekçi olmayabilecek en kısa yolları kullandığı varsayımını yapar.
- Eksik veya gürültülü kenarlara duyarlıdır: birkaç gözlemlenmemiş bağ bile arakesme sıralamalarını önemli ölçüde değiştirebilir.
- Kenar kapasiteleri veya ilişki güçleri önemli ölçüde farklı olsa bile tüm en kısa yollara eşit ağırlık verir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Derece ve özvektör merkeziyetinin tamamen kaçırdığı yapısal aracılık ve köprü rollerini yakalar.
- Aynı formülle yönlendirilmiş, yönlendirilmemiş, ağırlıklı ve ağırlıksız ağlara uygulanabilir.
- Normalleştirilmiş puan, tek bir ağ içindeki ve farklı boyutlardaki ağlar arasındaki düğümlerin anlamlı karşılaştırmasını sağlar.
- Brandes algoritması, NetworkX veya igraph gibi optimize edilmiş kütüphanelerde uygulandığında milyonlarca düğüme sahip ağlar için hesaplamayı yönetilebilir hale getirir.
- İyi temellendirilmiş teorik yorum: yüksek arakesme değerine sahip düğümler, örgütsel ve sosyal araştırmalarda bilgi kontrolü, güç ve yapısal boşluklarla ampirik olarak ilişkilidir.
Uygulama alanları
- Örgütsel iletişim ağlarında kapıcıları ve bilgi aracılarının belirlenmesi.
- Ulaşım, güç şebekesi ve internet topolojisi çalışmalarında kritik altyapı düğümlerinin tespiti.
- Atıf ve işbirliği ağlarında kilit aracı yazarların veya makalelerin bulunması.
- Firmalar arası ittifak ağlarında yapısal boşlukların ve aracılık pozisyonlarının haritalanması.
- Epidemiyolojik ve söylenti yayılma modellerinde etkili yayıcıların yerinin belirlenmesi.
- Halk sağlığı ve güvenlik araştırmalarında hedeflenen müdahaleler (örneğin, aşılama, aksatma) için düğümlerin önceliklendirilmesi.
Nasıl çalışır?
Nasıl çalışır?
Ağdaki her sıralı farklı düğüm çifti (s, t) için, aralarındaki tüm en kısa yollar (jeodezikler) belirlenir. Ağırlıklı graflar için en kısa yollar minimum toplam kenar ağırlığı ile; ağırlıksız graflar için en az geçiş sayısı ile tanımlanır. Bu adım, arakesmenin dağıtılacağı yollar evrenini oluşturur.
Her (s, t) çifti için en kısa yolların toplam sayısı sigma(s, t) sayılır. Birden fazla eşit derecede kısa yol varsa, her biri ayrı ayrı sayılır. Bu payda, yönlendirme üzerinde herhangi bir kısıtlama olmaksızın s ve t arasındaki toplam en kısa yol trafiğini temsil eder.
Formül
\sigma(s,t) = \text{number of shortest paths from } s \text{ to } tHer aday düğüm v (burada v ne s ne de t'dir) için, bu sigma(s, t) en kısa yollarından v'den geçenlerin sayısı sigma(s, t | v) olarak kaydedilir. sigma(s, t | v) / sigma(s, t) oranı, s ve t arasındaki en kısa yol trafiğinin v üzerinden yönlendirilen kesrini verir.
Formül
\sigma(s,t|v) = \text{shortest paths from } s \text{ to } t \text{ passing through } vBu kesirler, ham arakesme puanını C_B(v) üretmek için tüm geçerli (s, t) çiftleri üzerinden toplanır. Kaldırılması birçok çift-bazlı en kısa yolu ayıracak bir düğüm, yüksek bir toplam biriktirir, bu da yapısal olarak kritik bir aracılık pozisyonunu işaret eder.
Formül
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma(s,t|v)}{\sigma(s,t)}Ham puanlar ağ boyutuna göre artar, bu da farklı boyutlardaki ağlar arasında karşılaştırmaları anlamsız hale getirir. Yönlendirilmemiş graflar için (n-1)(n-2)/2 (veya yönlendirilmiş graflar için (n-1)(n-2)) ile normalleştirme, puanları [0, 1] aralığına yeniden ölçekler; burada 1.0, düğümün her en kısa yol üzerinde olduğu ve 0 ise hiçbirinde olmadığı anlamına gelir. Brandes (2001), her düğüm için aramayı tekrarlamak yerine tüm arakesme puanlarını eşzamanlı olarak hesaplayan bir O(VE) algoritması tanıtmıştır.
Formül
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}Sık yapılan hatalar
- Yüksek arakesmeyi yüksek derece ile eşdeğer kabul etmek, her ikisini de kontrol etmeden; çevresel bir düğüm arakesmede birinci sırada yer alırken derecede son sırada yer alabilir.
- Farklı boyutlardaki ağlar arasında (normalleştirilmemiş) ham arakesme puanlarını karşılaştırmak.
- Yönlendirilmiş ağlarda kenar yönünü göz ardı etmek, akışlar asimetrik olduğunda yanıltıcı aracı tanımlamasına neden olabilir.
- Ağırlıklı ağlara standart arakesme uygulamak, kenar ağırlıklarının en kısa yol algoritmasında benzerlikler (değil) olarak doğru yorumlandığını doğrulamadan.
- Büyük ağlar için yaklaşık arakesme yöntemlerini göz ardı etmek ve milyonlarca düğümde hesaplamayı durdurmak.
Sık sorulan sorular
Arakesme merkeziyeti, derece merkeziyetinden nasıl farklıdır?
Derece merkeziyeti doğrudan bağlantıları sayar; çok sayıda bağı olan bir merkez yüksek puan alır. Arakesme merkeziyeti, bir düğümün başkaları arasındaki en kısa yollar üzerinde ne sıklıkla bulunduğunu sayar; iki seyrek kümesini bağlayan bir köprü, az sayıda doğrudan bağı olsa bile yüksek puan alır. İki ölçüm, yapısal önemin dik olmayan yönlerini yakalar.
Normalleştirilmiş veya ham arakesme puanlarını kullanmalı mıyım?
Farklı boyutlardaki ağlar arasında düğümleri karşılaştırdığınızda veya sonuçları ağınızın ölçeğine aşina olmayan okuyuculara sunduğunuzda her zaman normalleştirilmiş puanları kullanın. Ham puanlar yalnızca paydanın sabit olduğu tek bir sabit ağ içindeki karşılaştırmalar için kabul edilebilirdir.
Ağırlıklı kenarları nasıl ele almalıyım?
Kenar ağırlıklarını benzerlik yerine mesafe veya maliyeti temsil edecek şekilde ayarlayın. Çoğu uygulama (NetworkX, igraph), mesafe olarak yorumlanan bir ağırlık parametresi kabul eder; ağırlıklarınız gücü veya benzerliği temsil ediyorsa, arakesmeyi hesaplamadan önce bunları ters çevirin (örneğin, ağırlık = 1/benzerlik).
Arakesme merkeziyeti bağlantısız ağlar için anlamlı mıdır?
Bağlantısız graflar için, farklı bileşenlerdeki düğümler arasındaki en kısa yollar tanımsızdır (sonsuz). Çoğu yazılım bu çiftleri toplama sıfır katkıda bulunan olarak ele alır, bu da puanları düşürebilir. Ya her bağlı bileşeni ayrı ayrı analiz edin ya da bağlantısız çiftlerin açık bir şekilde ele alınmasıyla stres merkeziyeti gibi bir varyant kullanın.
Ağım milyonlarca düğüme sahip - hala arakesme merkeziyetini hesaplayabilir miyim?
Brandes algoritması ile kesin hesaplama O(VE)'dir ve çok yavaş olabilir. NetworkX (k parametresi ile betweenness_centrality) veya yaklaştırılmış puanlar üzerinde güven aralıkları sağlayan graph-tool gibi grafik kütüphanelerinde bulunan rastgele yaklaşımları (örneğin, k kaynak düğüm örneklemesi) kullanın.
İlgili yöntemler
Kaynaklar
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1), 35–41.
DOI kaynağını açKopyalandı.Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.
DOI kaynağını açKopyalandı.