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

Yakınlık Merkezi̇lli̇ği̇

Ortaya koyan
Bavelas, A.; formalized by Freeman, L. C.
Yıl
1950 (formalized 1979)
Tür
Node-level centrality index
Aile
Network science

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

Yazı boyutu

Ne işe yarar?

Yakınlık merkezi̇lli̇ği̇, bir düğümün ağdaki diğer tüm düğümlere ne kadar hızlı ulaşabileceğini, her bir diğer düğüme olan ortalama en kısa yol mesafesinin tersini hesaplayarak ölçer.

İlk olarak Bavelas (1950) tarafından tanımlanmış ve Freeman (1979) tarafından biçimsel olarak birleştirilmiş olup, yalnızca çok sayıda doğrudan temasa sahip düğümleri değil, bilgiyi veya kaynakları tüm grafik boyunca verimli bir şekilde yayabilen düğümleri tanımlar.

Yöntemin mantığı

Bir düğüme bir mesaj bırakıp ağın her köşesine ne kadar hızlı ulaştığını izlediğinizi hayal edin. Yüksek yakınlığa sahip bir düğüm, bağlantı ağının merkezine yakın oturur: herkese ulaşmak için ortalama olarak daha az atlama gerektirir. Çok sayıda komşusu olan çevresel bir düğüm, ağın büyük bölümlerinden hala uzak olabilir. Yakınlık, bu ağ coğrafyası fikrini yakalar: kısa ortalama mesafe yüksek yakınlık anlamına gelir ve yüksek yakınlık verimli yayın yapma veya grafik boyunca akan bilgilere hızlı erişim anlamına gelir.

Tarih

Alex Bavelas, 1950'de MIT'deki grup problem çözme verimliliği üzerine çalışırken en kısa yollara dayanan iletişim merkezi̇lli̇ği̇ kavramını tanıttı. Linton Freeman'ın dönüm noktası olan 1979 tarihli Social Networks makalesi, derece ve aracılık merkezi̇lli̇ği̇ ile birlikte yakınlık merkezi̇lli̇ği̇ni̇ üç kanonik düğüm düzeyindeki merkezi̇lli̇k ölçüsünden biri olarak biçimselleştirdi ve modern sosyal ağ analizinin temelini oluşturan birleşik bir matematiksel çerçeve sağladı.

Ne zaman kullanılır?

Bilgiyi en verimli şekilde yayınlayabilen, kaynakları harekete geçirebilen veya minimum aracılarla ağın geri kalanına erişebilen düğümleri belirlemek istediğinizde yakınlık merkezi̇lli̇ği̇ni̇ kullanın — örneğin, optimal yayılma tohumlarını, etkili iletişimcileri veya transit merkezlerini belirlemek için. Herhangi bir boyuttaki bağlı veya neredeyse bağlı grafikler için uygundur. Ağın oldukça parçalanmış olduğu (çok sayıda bağlantısız bileşen) durumlarda birincil merkezi̇lli̇k ölçüsü olarak kullanmayın, çünkü ham yakınlık puanları sıfıra yakın ve anlamsız hale gelir; Wasserman-Faust normalizasyonunu uygulayın veya bileşenleri ayrı ayrı analiz edin. Yakınlığı derece ile karıştırmaktan kaçının: bir düğümün çok sayıda doğrudan bağı olabilir ancak yine de küresel erişimde çevresel olabilir.

Sınırlar ve dikkat edilmesi gerekenler

  • Grafik bağlantısına duyarlıdır: bağlantısız ağlarda ham ölçü çöker ve normalleştirme ayarlamaları gerektirir.
  • Tüm en kısa yolları eşit derecede önemli kabul eder; trafiğin hacmini veya belirli bir yolun aslında kullanılma olasılığını dikkate almaz.
  • Yaklaşım algoritmaları olmadan tüm-çift en kısa yol hesaplamasının ölçeklenmesi zayıf olduğundan, çok büyük grafiklerde (milyonlarca düğüm) hesaplama açısından pahalıdır.
  • Birçok zayıf bağa yakın olan bir düğüm ile birkaç güçlü, stratejik olarak önemli bağa yakın olan bir düğüm arasında ayrım yapmaz.

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

Güçlü yönleri

  • Yalnızca yerel bağlantıdan ziyade küresel erişilebilirliği yakalar, bu da bilgi akışı ve yayılmasının incelenmesi için idealdir.
  • Normalleştirilmiş puan (0 ila 1) farklı boyutlardaki ağlar arasında karşılaştırma yapmayı sağlar.
  • Sosyoloji, epidemiyoloji ve bilgisayar bilimlerinde onlarca yıllık doğrulamaya sahip köklü teorik temel.
  • Düğüm rollerinin daha zengin bir resmini sunmak için derece ve aracılık merkezi̇lli̇ği̇ni̇ tamamlar.
  • Çoğu ampirik ağ için BFS (ağırlıksız) veya Dijkstra (ağırlıklı) ile verimli bir şekilde hesaplanabilir.

Uygulama alanları

  • Kurumsal ve sosyal ağlarda kilit bilgi aracılarının veya fikir liderlerinin belirlenmesi.
  • Bilgi veya hastalık yayılmasının hızını en üst düzeye çıkarmak için optimal tohum düğümlerinin seçilmesi.
  • Ulaşım ağlarında genel erişilebilirliklerine göre transit istasyonlarının veya yol kavşaklarının sıralanması.
  • Biyolojik etkileşim ağlarında etkili proteinlerin veya genlerin yerelleştirilmesi.
  • Teknoloji yayılma çalışmalarında etkili erken benimseyenlerin tespiti.
  • Halk sağlığı temas ağlarında salgın yayılmasını yavaşlatmak için müdahale hedeflerinin önceliklendirilmesi.

Nasıl çalışır?

Nasıl çalışır?

1

Ağı, düğümlerin aktörler (insanlar, kuruluşlar, web sayfaları, genler vb.) olduğu ve kenarların ilişkileri veya etkileşimleri kodladığı bir grafik olarak temsil edin. Grafik yönlü veya yönsüz olabilir; kenarlar ağırlıksız (her atlama 1 maliyetlidir) veya ağırlıklı (maliyet kenar ağırlığına eşittir, mesafe veya ters güç olarak yorumlanır) olabilir.

2

Her bir v düğümü için, ağırlıksız grafikler için Genişlik-Öncelikli Arama (Breadth-First Search) veya ağırlıklı grafikler için Dijkstra'nın algoritmasını kullanarak diğer ulaşılabilir her bir u düğümüne olan en kısa yol mesafesini d(u, v) hesaplayın. Yönlü grafikler için yalnızca kenar yönünü izleyen yollar geçerlidir, bu nedenle iç-yakınlık ve dış-yakınlık farklılık gösterebilir.

Formül
d(u,v) = \text{shortest path length between nodes } u \text{ and } v
3

Bir v düğümünün ağın geri kalanına ortalama olarak yakın olduğunu gösteren küçük bir uzaklık; çevreselliği gösteren büyük bir uzaklık elde etmek için v'den diğer her düğüme olan tüm en kısa yol mesafelerini toplayın.

Formül
\text{farness}(v) = \sum_{u \neq v} d(u, v)
4

Ortalama en kısa yol mesafesinin tersini alın: C(v) = (n-1) / toplam d(u,v). (n-1) ile çarpmak, farklı boyutlardaki ağlardaki düğümlerin karşılaştırılabilmesi için (0, 1] aralığında normalleştirilmiş bir puan verir. Daha yüksek değerler daha merkezi, ulaşılabilir bir konumu gösterir.

Formül
C(v) = \frac{n-1}{\sum_{u \neq v} d(u, v)}
5

Bağlantısız grafiklerde bir düğüm diğer tüm düğümlere ulaşamaz, bu nedenle ham yakınlık ulaşılamayan çiftler için sıfır veya tanımsızdır. Wasserman-Faust normalizasyonu, yalnızca ulaşılabilir düğümler üzerinden toplayıp grafiğin ulaşılabilir kısmıyla yeniden ölçeklendirerek bağlantısız grafiklere yakınlığı genişletir ve izole bileşenler için sahte sıfıra yakın puanları önler.

Sık yapılan hatalar

  • Wasserman-Faust normalizasyonunu uygulamadan, bağlantısız bileşenlere sahip bir ağda ham yakınlığın raporlanması, yanıltıcı sıfıra yakın puanlar üretir.
  • Yakınlık ve derece merkezi̇lli̇ği̇ni̇ değiştirilebilir olarak ele almak — yüksek derece yüksek yakınlık anlamına gelmez ve bunun tersi de geçerlidir.
  • Kenarların yönlü olup olmadığını göz ardı etmek: yönlü ağlarda, yakınlık her iki yönde ayrı ayrı hesaplanmalıdır.
  • Ağırlıkların anlamlı mesafeleri kodladığı ağırlıklı bir ağa ağırlıksız yakınlık uygulamak, ilişki gücü hakkındaki bilgiyi kaybetmek.
  • n'yi kontrol etmeden farklı boyutlardaki ağlar arasında ham (normalleştirilmemiş) yakınlık puanlarını karşılaştırmak.

Sık sorulan sorular

Yakınlık, derece merkezi̇lli̇ği̇nden nasıl farklıdır?

Derece merkezi̇lli̇ği̇ yalnızca doğrudan komşuları sayar, bu nedenle bir düğüm, tüm bağlantıları ağın bir köşesinde kümelenmiş olsa bile çok sayıda bağlantısı varsa yüksek puan alabilir. Yakınlık, grafikteki her düğüme olan en kısa yolu dikkate alır, bu nedenle küresel erişilebilirliği ödüllendirir. Çevresel bir klik merkezi yüksek dereceye ancak düşük yakınlığa sahip olabilir.

Ağım bağlantısız bileşenlere sahip olduğunda ne yapmalıyım?

Yalnızca ulaşılabilir çiftleri toplayıp ağın ulaşılabilir oranına göre yeniden ölçeklendiren Wasserman-Faust (1994) harmonik veya ulaşılabilirlik ayarlı normalizasyonu uygulayın. Alternatif olarak, en büyük bağlı bileşeni ayrı ayrı analiz edin veya harmonik merkezi̇lli̇ği̇ (karşılıklı mesafelerin toplamı) kullanın, bu da ulaşılamayan çiftleri doğal olarak sıfır katkısı atayarak ele alır.

Yakınlık ağırlıklı ağlarda çalışır mı?

Evet. Ağırlıksız BFS yerine kenar ağırlıklarını mesafe olarak (veya daha yüksek ağırlık daha yakın anlamına geliyorsa güç/benzerlik ağırlıklarının tersini) kullanarak Dijkstra'nın algoritmasını kullanın. Ortaya çıkan ağırlıklı yakınlık, hem topolojiyi hem de bağlantıların kalitesini yansıtır.

Normalleştirilmiş yakınlık puanını nasıl yorumlamalıyım?

1'e yakın bir puan, düğümün diğer tüm düğümlere ortalama olarak yaklaşık bir atlamada ulaşabileceği anlamına gelir — ağın merkezinde yer alır. 0'a yakın bir puan, düğümün çok çevresel olduğu anlamına gelir. Genellikle yaklaşık 0,6'nın üzerindeki puanlar, çoğu ampirik ağda gerçekten merkezi konumları gösterir.

Yakınlık yönlü ağlar için uygun mudur?

Evet, ancak her yönde ayrı ayrı hesaplayın. İç-yakınlık, başkalarının odak düğüme ne kadar kolay ulaşabileceğini (düğüm prestijini veya alıcılığını incelemek için kullanışlıdır) ölçerken, dış-yakınlık odak düğümün başkalarına ne kadar kolay ulaşabileceğini (yayın kapasitesini incelemek için kullanışlıdır) ölçer.

İlgili yöntemler

Kaynaklar

  1. Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215–239.

    DOI kaynağını aç
    Kopyalandı.
  2. Bavelas, A. (1950). Communication patterns in task-oriented groups. Journal of the Acoustical Society of America, 22(6), 725–730.

    DOI kaynağını aç
    Kopyalandı.