Ağ Biliminde Ölçüm Nasıl Yapılır?

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 $k_i$ derecesi şöyle gösterilir:

$k_i=\sum _{\begin{array}{c}j=1\end{array}}^N{A}_{ij}$

Yönsüz ağlarda her bir bağlantının iki adet etki yönü vardır ($\leftrightarrow$. Diğer bir deyişle $E$ adet bağlantının $2E$ adet etki yönü vardır. Böylece $2E$, tüm düğümlerin derecelerinin toplamına eşittir:

$2E=\sum _{i=1}{k}_i$

Toplam bağlantıların sayısı matristen elde edilmek istenirse

$E=\frac{1}{2}\sum _{i=1}{k}_i=\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{A}_{ij}$

şeklinde ifade edilebilir. Ağdaki bir düğümün ortalama derecesi $<k>$ aşağıdaki gibi gösterilir:

$<k>=\frac{1}{N}\sum _{i=1}^N{k}_i=\frac{2E}{N}$

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:

$k_i^{iç}=\sum _{j=1}^N{A}_{ji},k_i^{dış}=\sum _{j=1}^N{A}_{ij}$

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

$E=\sum _{i=1}^N{k}_i^{iç}=\sum _{j=1}^N{k}_j^{dış}=\sum _{i=1}^N\sum _{j=1}^N{A}_{ij}$

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

$<k_{iç}>=\frac{1}{N}\sum _{i=1}^N{k}_i^{iç}=\frac{1}{N}\sum _{j=1}^N{k}_j^{dış}=<k_{dış}>$

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

$<k>=\frac{E}{N}$

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,\dots ,\xi$ olmak üzere

$P(1)=\frac{N(1)}{N},P(2)=\frac{N(2)}{N},...,P(\xi )=\frac{N(\xi )}{N}$

şeklinde ifade edilir.

Yukarıdaki denklemde, ağlarda bir veya daha fazla düğümün kendine bağlantısı varsa maksimum düğüm derecesi farklılık göstereceği için $N$ yerine $\xi$ yazılmıştır. $\xi =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.

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{)}_{iç},k=1,2,...,N$ olmak üzere,

$P(1{)}_{iç}=\frac{N(1{)}_{iç}}{N},P(2{)}_{iç}=\frac{N(2{)}_{iç}}{N},...,P(N{)}_{iç}=\frac{N(N{)}_{iç}}{N}$

Agora Bilim Pazarı

PALME 2.SINIF TEK YARIYIL TATİL EĞLENCEM

Devamını Göster

₺360.00

Satın Al Tüm Ürünler

$N(k{)}_{dış},k=1,2,...,N$olmak üzere,

$P(1{)}_{dış}=\frac{N(1{)}_{dış}}{N},P(2{)}_{dış}=\frac{N(2{)}_{dış}}{N},...,P(N{)}_{dış}=\frac{N(N{)}_{dış}}{N}$

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

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$ olmak üzere)

$P_{ij}=\frac{N_{ij}}{N}$

ş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 gösterilmelidir. 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.

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 ($P_{ij}$'de hem $i$ hem de $j$ yüksek ise) bunun yansımasını $k_{iç}$ ve $k_{dış}$'ı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 (İng: "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 (İng: "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

$s_1$ düğümünden $s_2$'ye giden en kısa yol olan $l_{s_1{s}_2}$, $s_2$'den $s_1$'e giden $l_{s_2{s}_1}$ 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.

$<l>=\frac{\sum _{i=1}^N\sum _{j=1}^N{l}_{ij}}{\sum _{i=1}^N\sum _{j=1}^N(ba\breve{g}lantıvarsa{l}_{ij}=1)}$

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.

Kümelenme Katsayısı

Çoğu ağda eğer $s_1$ ve $s_2$ düğümleri bağlı olup $s_2$ ve $s_3$ arasında bağlantı varsa, $s_1$ ve $s_3$ 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ına işaret etmektedir. Yönsüz ağlarda her $i$ düğümü için kümelenme katsayısı şu şekildedir:

$C_i=\frac{2n_i}{k_i(k_i-1)}$

Burada $n_i$, $k_i$ adet komşu arasındaki bağlantı sayısıdır. Başka bir deyişle $C_i$, $i$ düğümünün içinde yer aldığı üçgenleri verir ve maksimum sayısı $k_i(k_i-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.

$<C>=\frac{1}{N}\sum _{i=1}^N\frac{2n_i}{k_i(k_i-1)}$

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ı şu şekildedir:

$C_i=\frac{n_i}{k_i(k_i-1)}$

$<C>=\frac{1}{N}\sum _{i=1}^N\frac{n_i}{k_i(k_i-1)}$

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:

$P_{C_i}=\frac{C_i}{\sum _{i=1}^N}{C}_i=\frac{1}{N}\frac{C_i}{<C>}$

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.