Yakınlık merkeziliği - Closeness centrality

Bir de bağlı grafik , yakınlık Merkezilik (ya da yakınlık ) bir düğüm bir ölçüsüdür merkezî bir de şebeke uzunluğu toplamı ile karşılıklı olarak hesaplanır, en kısa yol düğüm ve grafikte, tüm diğer düğümler arasında. Bu nedenle, bir düğüm ne kadar merkeziyse, diğer tüm düğümlere o kadar yakındır .

Yakınlık olarak (1950) Bavelas tarafından tanımlanan karşılıklı bir farness olup:

${\displaystyle C(x)={\frac {1}{\sum _{y}d(y,x)}}.}$

burada bir mesafe uçları arasında ve . Yakınlık merkeziliğinden bahsederken, insanlar genellikle toplamları yerine en kısa yolların ortalama uzunluğunu temsil eden normalleştirilmiş biçimine atıfta bulunurlar. Genellikle ile çarpılır önceki formül ile verilir , grafikte düğüm sayısı. Büyük grafikler için bu fark önemsiz hale gelir, bu nedenle düşerek şu şekilde sonuçlanır: ${\görüntüleme stili d(y,x)}$${\görüntüleme stili x}$${\görüntüleme stili y}$${\görüntüleme stili N-1}$${\görüntüleme stili N}$${\görüntüleme stili -1}$

${\displaystyle C(x)={\frac {N}{\sum _{y}d(y,x)}}.}$

Normalleştirme, farklı boyutlardaki grafik düğümleri arasında karşılaştırmalara izin verir.

Mesafeleri alarak gelen veya hiç diğer tüm düğümler bunun tamamen farklı sonuçlar üretebilir oysa yönsüz grafiklerde alakasız yönlendirilmiş grafikler (giden bağlantısından yüksek yakınlık merkeziliğini olabilir mesela bir web sitesi, ancak gelen bağlantılardan düşük yakınlık merkeziyet).

Bağlantısı kesilmiş grafiklerde

Bir grafik güçlü bir şekilde bağlı olmadığında , Beauchamp 1965'te uzaklıkların toplamının tersi yerine mesafelerin karşılıklı toplamını kullanma fikrini şu kuralla ortaya koydu : ${\displaystyle 1/\infty =0}$

${\displaystyle H(x)=\sum _{y\neq x}{\frac {n-1}{d(y,x)}}.}$

Beauchamp'ın modifikasyonu (çok daha sonraları) Marchiori ve Latora (2000) tarafından önerilen , sonsuz mesafeli grafiklerde harmonik ortalamanın aritmetik ortalamadan daha iyi davrandığı genel prensibini takip eder . Aslında, Bavelas'ın yakınlığı, uzaklıkların aritmetik ortalamasının denormalize edilmiş karşılığı olarak tanımlanabilirken , Beauchamp'ın merkeziliği, mesafelerin harmonik ortalamasının karşılığıdır .

Bu fikir, literatürde, genellikle normalleştirme faktörü olmadan birkaç kez yeniden ortaya çıktı : Dekker (2005) tarafından değerli merkezilik adı altında ve adı altında yönsüz grafikler için${\görüntüleme stili n-1}$harmonik merkezilik , Rochat (2009); if, Garg (2009) tarafından aksiyomatize edilmiş ve daha sonra Opsahl (2010) tarafından bir kez daha önerilmiştir. Boldi ve Vigna (2014) tarafından genel yönlü grafikler üzerinde çalışılmıştır. Bu fikir aynı zamanda Harris'in (1954) önerdiği pazar potansiyeline de oldukça benzerdir ve bu da günümüzde sıklıkla pazara erişim terimiyle anılmaktadır.

Varyantlar

Dangalchev (2006), ağ güvenlik açığı üzerine bir çalışmasında, yönsüz grafikler için farklı bir tanım önermektedir:

${\displaystyle D(x)=\sum _{y\neq x}{\frac {1}{2^{d(y,x)}}}.}$

Bu tanım, bağlantısız grafikler için etkin bir şekilde kullanılır ve grafik işlemleri için uygun formüller oluşturmaya olanak tanır. Örneğin:

Bir grafiktir Eğer düğüm bağlayarak oluşturulan grafik düğüme grafiğin sonra birleştirilen yakınlığı: ${\displaystyle G_{1}+G_{2}}$${\görüntüleme stili p}$${\görüntüleme stili G_{1}}$${\görüntüleme stili q}$${\ Displaystyle G_{2}}$

${\displaystyle D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+(1+D(p))(1+D(q));}$

eğer bir grafik kullanıcı düğüm çöken oluşturulur grafik ve düğüm grafiğinin bir düğüme yakınlık sonra: ${\displaystyle G_{1}+G_{2}}$${\görüntüleme stili p}$${\görüntüleme stili G_{1}}$${\görüntüleme stili q}$${\ Displaystyle G_{2}}$

${\displaystyle D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+2D(p)D(q).}$

Eğer grafik , grafiğin düğümleri olan dikenli grafiği ise , yakınlık: ${\görüntüleme stili T(G)}$${\görüntüleme stili G}$${\görüntüleme stili n}$${\görüntüleme stili T(G)}$

${\displaystyle D(T(G))={\frac {9}{4}}D(G)+n.}$

Bu tanımın doğal genellemesi şudur:

${\displaystyle D(x)=\sum _{y\neq x}\ {\alpha ^{d(y,x)}},}$

burada (0,1) aittir. De 0 ile 1 arasında arttıkça, küresel (bağlı düğüm sayısı) yerel bir özelliğine (derece) genelleştirilmiş yakınlık değişiklikleri. ${\görüntüleme stili \alfa }$${\görüntüleme stili \alfa }$

Bilgi merkeziyet Stephenson ve Zelen (1989) ait hesaplar başka yakınlık ölçüsüdür harmonik ortalamasını bir köşe karşı direnç mesafeleri x , eğer daha küçük olan x diğer köşe bağlayarak küçük direniş birçok yolları vardır.

Yakınlığın merkeziliğinin klasik tanımında, bilginin yayılması en kısa yolların kullanılmasıyla modellenir. Bu model, tüm iletişim senaryoları için en gerçekçi olmayabilir. Bu nedenle, Noh ve Rieger (2004) tarafından tanıtılan rastgele yürüyüş yakınlık merkeziliği gibi yakınlığı ölçmek için ilgili tanımlar tartışılmıştır . Rastgele yürüyen mesajların grafiğin başka bir yerinden bir tepe noktasına ulaşma hızını ölçer - yakınlık merkeziliğinin bir tür rastgele yürüyüş versiyonu. Tran ve Kwon'un (2014) hiyerarşik yakınlığı , güçlü bir şekilde bağlantılı olmayan grafiklerdeki yakınlığın sınırlandırılmasıyla başka bir şekilde ilgilenmek için genişletilmiş bir yakınlık merkeziliğidir. Hiyerarşik yakınlık, verilen düğümden etkilenebilecek diğer düğümlerin aralığı hakkında açıkça bilgi içerir.

Ayrıca bakınız

• merkezilik
• Rastgele yürüyüş yakınlığı merkeziliği
• arasındalık merkeziliği

Referanslar