MatematikFizik

Ağ Bilimi – 2: Ağ Biliminde Ölçümler

Bir ağın analizi, içerisindeki düğüm, bağlantı ve düğüm gruplarını anlayabilmek için çeşitli ölçümlerden oluşur. Nicel ölçümlerin ve görselleştirmenin bir araya gelmesi, düğümler ve bağlantılar arasındaki ilişkileri anlamak için çok önemlidir. Bu yazıda ağlar için bazı temel ölçümler ve bunların gösterimleri incelenecektir.

Düğümün Derecesi

Bir ağdaki bir düğümün yaptığı bağlantı sayısı, o düğümün derecesini verir. N tane düğümü olan yönsüz bir ağda her i düğümü için ki derecesi

CodeCogsEqn Ağ Bilimi - 2: Ağ Biliminde Ölçümler

şeklindedir. Yönsüz ağlarda her bir bağlantının iki adet etki yönü vardır (CodeCogsEqn 1 Ağ Bilimi - 2: Ağ Biliminde Ölçümler). Diğer bir deyişle E adet bağlantının 2E adet etki yönü vardır. Böylece

eq2 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

tüm düğümlerin derecelerinin toplamına eşittir. Toplam bağlantıların sayısı matristen elde edilmek istenirse

eq3 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

şeklinde ifade edilebilir. Ağdaki bir düğümün ortalama derecesi <k> aşağıdaki gibidir:

eq4 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

Yönlü ağlarda ise düğümlerin dereceleri daha karmaşıktır. Bir düğüme gelen bağlantılar iç dereceyi, giden bağlantılar da dış dereceyi meydana getirir. İç ve dış dereceler aşağıdaki gibi ifade edilir:

eq5 1 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

Yönlü ağlarda toplam bağlantı sayısı tüm düğümlerin iç veya dış derecelerinin toplamıdır.

eq6 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

Böylece iç ve dış derecelerin ortalamaları da birbirine eşit olur.

eq7 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

Ortalama derece de böylece yönsüz ağlardakinin yarısı olmaktadır.

eq8 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

Derece Dağılımı

Derece dağılımı P(k), seçilen bir düğümün k adet bağlantısının olma olasılığıdır. Aynı dereceye sahip düğümlerin sayısının toplam düğüm sayısına oranı ile olasılıklar ve dağılım elde edilir. N(k), k=1, 2,…, ξ olmak üzere

eq9 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

şeklinde ifade edilir.

Not: Yönsüz ağlarda bir veya daha fazla düğümün kendine bağlantısı varsa maksimum düğüm derecesi farklılık gösterdiği için N yerine ξ yazılmıştır. ξ = N+1 gibi düşünülebilir. Çünkü yönsüz ağlardaki kendine bağlantıların matris köşegen değeri 2’dir.

Aşağıda örnek bir derece dağılımı gösterilmektedir.

fig1 Ağ Bilimi - 2: Ağ Biliminde Ölçümler
Zachary Karate Kulübü olarak bilinen ve sosyal ağlar sınıfına giren bir yönsüz ağın gösterimi (üstte) ve derece dağılımı (altta).

Yönlü ağlarda derece dağılımı, iç derece dağılımı ve dış derece dağılımı olmak üzere iki biçimdedir. Olasılıklar iç ve dış dereceler için ayrı ayrı hesaplanmalıdır.

N(k) , k=1, 2, …, N olmak üzere

eq10 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

N(k)dış , k=1, 2, …, N olmak üzere

eq11 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

Yönlü bir ağın iç ve dış derece dağılımları aşağıda gösterilmiştir.

icderece disderece Ağ Bilimi - 2: Ağ Biliminde Ölçümler
Zachary Karate Kulübü yönsüz ağında bağlantılara rastgele yön verilmesi ile elde edilen yönlü ağ ve a) iç derece, b) dış derece dağılımları.

Eğer iç ve dış derece dağılımları, daha sofistike bir şekilde, tek grafikte görülmek istenirse ortak bir dağılım elde edilebilir. Burada olasılıklar, i iç derece ve j dış derece olacak şekilde iki indislidir. Bu durumda tüm olasılık değerleri, tüm olası durumlar üzerinden (i=1, 2,…, N, j=1, 2,…, N)

eq12 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

şeklinde hesaplandığında, yönlü ağların bütünleşik derece dağılımı ortaya çıkmaktadır. Dağılımın kendisi iki boyutludur bu nedenle basit bir histogram olarak çizilemez. İki boyutlu bir renk haritası veya üç boyutlu bir grafik şeklinde olmalıdır. Yukarıdaki Zachary Karate Kulübü’nün yönlü ağının olasılık değerleri hesaplanarak üç boyutlu bütünleşik derece dağılımı çizilmiştir.

butunlesik derecedagilimi Ağ Bilimi - 2: Ağ Biliminde Ölçümler
Zachary yönlü ağının oluşturulan bütünleşik derece dağılımı. Olasılıkların maksimum değeri iç derece ve dış derece dağılım grafiklerindeki maksimumlardan daha azdır. Çünkü örneklem kümesi büyümüştür (tüm Pij değerleri) ve her bir iç veya dış derece işin koşullu olasılık geçerlidir.

Bütünleşik derece dağılımı kullanılarak iç ve dış dereceler arasında bir korelasyonun olup olmadığı incelenebilir. Örneğin yüksek iç dereceye sahip düğümler aynı zamanda yüksek dış dereceye sahip ise (Pij‘de hem i hem de j yüksek) bunun yansımasını k ve kdış‘ın büyük değerlerinde yükseltiler olarak görebiliriz. Bu durumun tam tersi de geçerlidir ve her ikisi de yukarıdaki şekilde görülmektedir. Eğer iç ve dış dereceler bütünleşik diyagram yerine ayrı ayrı ifade edilirlerse yönlü ağın derece korelasyonu içerip içermediğine bakılamamaktadır.

Bir ağın derece dağılımı ağ hakkında önemli bilgiler vermektedir. Örneğin derece dağılımı kuvvet yasası formundaysa, yani düşük olasılık değerlerindeki yüksek derecelerin sıfırdan farklı olması durumu varsa, ağlarda merkez düğümlerin (hub) olduğuna işaret eder. Bununla birlikte normal dağılım gibi tepeye sahip dağılımlarda düşük ya da yüksek dereceler benzer olasılıklardadır ve merkez düğümlerin olmadığı bir ağ söz konusudur. Ancak aynı derece dağılımına sahip çok fazla sayıda farklı ağ olabilir. Bu nedenle bir ağın tüm yapısı sadece derece dağılımı bulunarak elde edilememektedir.

En Kısa Yol ve Ortalama Yol Uzunluğu

Ağın içindeki iki düğüm arasındaki mesafe yol uzunluğu (path length) olarak ifade edilir. İki düğüm arasında çok sayıda farklı yol olabileceği için en kısa yol bunlar içinde ayrı bir öneme sahiptir. En az bağlantı ile hedefe ulaşmayı ifade eder. Yönlü ağlarda s1 düğümünden s2‘ye giden en kısa yol olan ls1s2, s2‘den s1‘e giden ls2s1 yolundan genellikle farklıdır. Ortalama yol uzunluğu <l>, ağdaki bütün düğüm çiftleri arasındaki en kısa yolların bir ortalamasıdır.

eq13 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

Yukarıdaki eşitlikte her i‘den her j‘ye olan yol uzunlukları ayrı ayrı hesaplanır ve eğer ilgili i ile j arasında ulaşım varsa paydaya 1 eklenir. Ortalama yol uzunluğu, ağın düğümleri arasındaki ulaşılabilirliğin bir ölçüsüdür. Yönsüz ağlarda her düğümün arasında bir şekilde bağlantı varken yönlü ağlarda durum farklıdır.

en kisa yol Ağ Bilimi - 2: Ağ Biliminde Ölçümler
Örnek yönlü ağda 1. düğümden 3.’ye giden en kısa yol ile 3.’den 1.’ye giden en kısa yolar farklıdır. l13=2 ve l31=1’dir. Ortalama yol uzunluğu <l>=9/8=1.125’tir.

Kümelenme Katsayısı

Çoğu ağda eğer s1 ve s2 düğümleri bağlı olup s2 ve s3 arasında bağlantı varsa, s1 ve s3 arasında da bağlantı olması olası bir durumdur. Eğer düğümler arası bağlantılar kapalı bir alan oluşturursa, ki en küçüğü üç düğüm arası bağlantıların oluşturduğu üçgendir, bu durum kümelenme katsayısı ile karakterize edilir.

Kümelenme katsayısı bir düğümün komşularının aralarındaki bağlantıların ölçüsüdür. Gerçel ağlarda düğümlerin dereceleri ile ters orantılıdır ve bir ağın hiyerarşik yapısını da işaret etmektedir. Yönsüz ağlarda her i düğümü için kümelenme katsayısı

eq14 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

şeklindedir. Burada ni, ki adet komşu arasındaki bağlantı sayısıdır. Başka bir deyişle Ci, i düğümünün içinde yer aldığı üçgenleri verir ve maksimum sayısı da ki(ki-1)/2’dir. Her bir düğümün kümelenme katsayısı lokal kümelenme katsayılarını oluşturur ve ağın kümelenme katsayısını elde etmek için ortalaması alınmalıdır.

eq15 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

Yönlü ağlarda bir düğümün kümelenme katsayısı yönsüz ağlardakinin yarısıdır. Çünkü yönsüz ağların bağlantıları çift yönlü oldukları için iki adet yönlü bağlantı varmış gibi düşünülebilir. Bu nedenle her bir düğüm için lokal kümelenme katsayıları ve tüm ağın ortalama kümelenme katsayısı

eq16 Ağ Bilimi - 2: Ağ Biliminde Ölçümler
eq17 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

şeklindedir. Yönlü ve yönsüz ağlar için bu genel ifadelerin özel durumları da vardır. Kümelenme katsayısı 0 ile 1 aralığında değerler alır. Kapalı bir bağlantısı bulunmayan (veya hiç bağlantısı bulunmayan) ağlarda 0, her bir düğümün birbirine bağlı olduğu ağlarda ise 1’dir.

Ağın yapısı ile ilgili önemli bir ölçüm de kümelenme katsayısından ortaya çıkmaktadır. Bazı durumlarda kümelenme katsayısının tüm düğümler üzerinden dağılımına bakılması gerekebilir. Bu da kümelenme katsayısı dağılımıdır. Örneğin bir ağın sıkı kümelenmiş ve az kümelenmiş bölgeleri olabilir. İstatistiksel ölçüm olarak, her i düğümü için lokal kümelenme katsayıları üzerinden olasılıklar şu şekilde hesaplanır

eq18 Ağ Bilimi - 2: Ağ Biliminde Ölçümler

Ortalama derece <k>, ortalama yol uzunluğu <l> ve ortalama kümelenme katsayısı <C> ağdaki düğümlerin ve bağlantıların sayısına (N, E) bağlıdır. Bu nicelikler ağın topolojisi hakkında kapsamlı bilgiler verebilmektedir.


Ağ Bilimi – 1: Giriş


Hazırlayan: Dr. Emir Haliki
Editör: Ögetay Kayalı

Referanslar
1. Newman, M. E. J., 2010, Networks: An introduction, Oxford University Press, New York, 740p.
2. Newman, M. E. J., 2004, Analysis of weighted networks, Physical Review E, 70:056131 pp.

Emir Haliki

Ege Üniversitesi Fen Fakültesi - Fizik Bölümünde Doktor Araştırma Görevlisi. Ağ bilimi, astrobiyoloji, genetik düzenlenme mekanizmaları, karmaşık sistemler ve astronomik cisimler çalışma alanı. Aynı zamanda matematik ve sayısal çözümleme de ilgi alanları. Bunların yanında amatör olarak, gözlemsel astronomi, doğa yürüyüşleri, satranç ve robotik kodlama ile ilgileniyor.
Back to top button

Destek Ol!


Neden desteğinize ihtiyacımız var: Çünkü Rasyonalist'in tek destekçisi sizlersiniz.

Rasyonalist'in masraflarını karşılamak, gelişimini sağlamak, profesyonel ekipmanlara ulaşarak bunlarla sizlere daha iyi hizmetler verebilmek için desteğiniz gerekiyor.

 

Bağışta bulunmakla ilgili soru işaretlerinizi yanıtlayabilmek için, hakkımızda sayfamıza göz atmanızı öneriyoruz.