Ağ Biliminde Ölçüm Nasıl Yapılır?
Becker Friedman Institute
- Özgün
- Grafik Teorisi
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. NN tane düğümü olan yönsüz bir ağda her ii düğümü için kik_
i derecesi şöyle gösterilir:
ki=∑j=1N Aijk_i =\sum\limits_{\substack{j=1}}^N \space 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 EE adet bağlantının 2E2E adet etki yönü vardır. Böylece 2E2E, tüm düğümlerin derecelerinin toplamına eşittir:
2E=∑i=1 ki2E =\sum\limits_{i=1} \space k_i
Toplam bağlantıların sayısı matristen elde edilmek istenirse
E=12∑i=1ki=12∑i=1N∑j=1NAijE = \frac{1}{2} \sum\limits_{i=1} k_i = \frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N A_{ij}
şeklinde ifade edilebilir. Ağdaki bir düğümün ortalama derecesi <k><k> aşağıdaki gibi gösterilir:
<k>=1N∑i=1Nki=2EN<k> = \frac{1}{N} \sum\limits_{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:
kiiç=∑j=1NAji, kidış=∑j=1NAijk_i^{iç} = \sum\limits_{j=1}^N A_{ji},\space k_i^{dış}= \sum\limits_{j=1}^N A_{ij}
Aslında maddi destek istememizin nedeni çok basit: Çünkü Evrim Ağacı, bizim tek mesleğimiz, tek gelir kaynağımız. Birçoklarının aksine bizler, sosyal medyada gördüğünüz makale ve videolarımızı hobi olarak, mesleğimizden arta kalan zamanlarda yapmıyoruz. Dolayısıyla bu işi sürdürebilmek için gelir elde etmemiz gerekiyor.
Bunda elbette ki hiçbir sakınca yok; kimin, ne şartlar altında yayın yapmayı seçtiği büyük oranda bir tercih meselesi. Ne var ki biz, eğer ana mesleklerimizi icra edecek olursak (yani kendi mesleğimiz doğrultusunda bir iş sahibi olursak) Evrim Ağacı'na zaman ayıramayacağımızı, ayakta tutamayacağımızı biliyoruz. Çünkü az sonra detaylarını vereceğimiz üzere, Evrim Ağacı sosyal medyada denk geldiğiniz makale ve videolardan çok daha büyük, kapsamlı ve aşırı zaman alan bir bilim platformu projesi. Bu nedenle bizler, meslek olarak Evrim Ağacı'nı seçtik.
Eğer hem Evrim Ağacı'ndan hayatımızı idame ettirecek, mesleklerimizi bırakmayı en azından kısmen meşrulaştıracak ve mantıklı kılacak kadar bir gelir kaynağı elde edemezsek, mecburen Evrim Ağacı'nı bırakıp, kendi mesleklerimize döneceğiz. Ama bunu istemiyoruz ve bu nedenle didiniyoruz.
Yönlü ağlarda toplam bağlantı sayısı tüm düğümlerin iç veya dış derecelerinin toplamıdır:
E=∑i=1Nkiiç=∑j=1Nkjdış=∑i=1N∑j=1NAijE= \sum\limits_{i=1}^N k_i^{iç}=\sum\limits_{j=1}^N k_j^{dış} = \sum\limits_{i=1}^N\sum\limits_{j=1}^N A_{ij}
Böylece iç ve dış derecelerin ortalamaları da birbirine eşit olur:
<kiç>=1N∑i=1Nkiiç=1N∑j=1Nkjdış=<kdış><k_{iç}> =\frac {1}{N} \sum\limits_{i=1}^N k_i^{iç}= \frac {1}{N} \sum\limits_{j=1}^N k_j^{dış} = <k_{dış}>
Ortalama derece de böylece yönsüz ağlardakinin yarısı olmaktadır:
<k>=EN<k> = \frac{E}N
Derece Dağılımı
Derece dağılımı P(k)P(k), seçilen bir düğümün kk 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,…,ξN(k), k=1, 2,…, \xi olmak üzere
P(1)=N(1)N,P(2)=N(2)N,...,P(ξ)=N(ξ)NP(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 NN yerine ξξ yazılmıştır. ξ=N+1 ξ = 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,...,NN(k)_{iç} , k=1, 2, ..., N olmak üzere,
P(1)iç=N(1)içN,P(2)iç=N(2)içN,...,P(N)iç=N(N)içNP(1)_{iç} = \frac{N(1)_{iç}}{N}, P(2)_{iç} = \frac{N(2)_{iç}}{N},..., P(N)_{iç} = \frac{N(N)_{iç}}{N}
N(k)dış,k=1,2,...,NN(k)_{dış} , k=1, 2, ...,Nolmak üzere,
P(1)dış=N(1)dışN,P(2)dış=N(2)dışN,...,P(N)dış=N(N)dışNP(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,
ii iç derece ve jj 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,...,Ni=1, 2,..., N, j=1, 2,..., N olmak üzere)
Pij=NijNP_{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 (PijP_{ij}'de hem ii hem de jj yüksek ise) bunun yansımasını kiçk_{iç} ve kdış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
s1s_1 düğümünden s2s_2'ye giden en kısa yol olan ls1s2l_{s_1s_2}, s2s_2'den s1s_1'e giden ls2s1l_{s_2s_1} yolundan genellikle farklıdır. Ortalama yol uzunluğu <l><l>, ağdaki bütün düğüm çiftleri arasındaki en kısa yolların bir ortalamasıdır.
<l>=∑i=1N∑j=1Nlij∑i=1N∑j=1N(bag˘lantı varsa lij=1)<l> = \frac{\sum\limits_{i=1}^N \sum\limits_{j=1}^N l_{ij}}{\sum\limits_{i=1}^N \sum\limits_{j=1}^N (bağlantı \space varsa \space l_{ij} =1)}
Yukarıdaki eşitlikte her ii'den her jj'ye olan yol uzunlukları ayrı ayrı hesaplanır ve eğer ilgili ii ile jj 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 s1s_1 ve s2s_2 düğümleri bağlı olup s2s_2 ve s3s_3 arasında bağlantı varsa, s1s_1 ve s3s_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 ii düğümü için kümelenme katsayısı şu şekildedir:
Ci=2niki(ki−1)C_i=\frac{2n_i}{k_i(k_i-1)}
Burada nin_i, ki k_i adet komşu arasındaki bağlantı sayısıdır. Başka bir deyişle CiC_i, ii düğümünün içinde yer aldığı üçgenleri verir ve maksimum sayısı ki(ki−1)/2k_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>=1N∑i=1N2niki(ki−1)<C> = \frac{1}{N}\sum\limits_{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:
Ci=niki(ki−1)C_i=\frac{n_i}{k_i(k_i-1)}
<C>=1N∑i=1Nniki(ki−1)<C> = \frac{1}{N}\sum\limits_{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 ii düğümü için lokal kümelenme katsayıları üzerinden olasılıklar şu şekilde hesaplanır:
PCi=Ci∑i=1NCi=1NCi<C>P_{C_i} = \frac{C_i}{\sum\limits_{i=1}^N}C_i =\frac{1}{N} \frac{C_i}{<C>}
Ortalama derece <k><k>, ortalama yol uzunluğu<l> <l> ve ortalama kümelenme katsayısı <C><C> ağdaki düğümlerin ve bağlantıların sayısına (N,E)(N, E) bağlıdır. Bu nicelikler ağın topolojisi hakkında kapsamlı bilgiler verebilmektedir.
İçeriklerimizin bilimsel gerçekleri doğru bir şekilde yansıtması için en üst düzey çabayı gösteriyoruz. Gözünüze doğru gelmeyen bir şey varsa, mümkünse güvenilir kaynaklarınızla birlikte bize ulaşın!
Bu içeriğimizle ilgili bir sorunuz mu var? Buraya tıklayarak sorabilirsiniz.
Soru & Cevap Platformuna Git-
4
-
3
-
1
-
0
-
0
-
0
-
0
-
0
-
0
-
0
-
0
-
0
- M. Newman. (2010). Networks. ISBN: 9780191500701. Yayınevi: OUP Oxford.
- M. E. J. Newman. (2004). Analysis Of Weighted Networks. Physical Review E, sf: 056131. doi: 10.1103/PhysRevE.70.056131. | Arşiv Bağlantısı
Evrim Ağacı'na her ay sadece 1 kahve ısmarlayarak destek olmak ister misiniz?
Şu iki siteden birini kullanarak şimdi destek olabilirsiniz:
kreosus.com/evrimagaci | patreon.com/evrimagaci
Çıktı Bilgisi: Bu sayfa, Evrim Ağacı yazdırma aracı kullanılarak 18/01/2025 17:07:23 tarihinde oluşturulmuştur. Evrim Ağacı'ndaki içeriklerin tamamı, birden fazla editör tarafından, durmaksızın elden geçirilmekte, güncellenmekte ve geliştirilmektedir. Dolayısıyla bu çıktının alındığı tarihten sonra yapılan güncellemeleri görmek ve bu içeriğin en güncel halini okumak için lütfen şu adrese gidiniz: https://evrimagaci.org/s/12907
İçerik Kullanım İzinleri: Evrim Ağacı'ndaki yazılı içerikler orijinallerine hiçbir şekilde dokunulmadığı müddetçe izin alınmaksızın paylaşılabilir, kopyalanabilir, yapıştırılabilir, çoğaltılabilir, basılabilir, dağıtılabilir, yayılabilir, alıntılanabilir. Ancak bu içeriklerin hiçbiri izin alınmaksızın değiştirilemez ve değiştirilmiş halleri Evrim Ağacı'na aitmiş gibi sunulamaz. Benzer şekilde, içeriklerin hiçbiri, söz konusu içeriğin açıkça belirtilmiş yazarlarından ve Evrim Ağacı'ndan başkasına aitmiş gibi sunulamaz. Bu sayfa izin alınmaksızın düzenlenemez, Evrim Ağacı logosu, yazar/editör bilgileri ve içeriğin diğer kısımları izin alınmaksızın değiştirilemez veya kaldırılamaz.
