Graph Theory (Çizge Kuramı) nedir?

Resmin kaynağı: polinode.com

“Anlamsal Ağ Nedir?” ve “Sosyal Anlamsal Ağ Nedir?” yazılarımızdan sonra tekrar merhabalar.

Bu hafta Çizge Kuramından bahsedeceğim. Bu teori, bize çeşitli ağları nasıl çizebileceğimizi, daha doğrusu nasıl yapılandırabileceğimizi artırıyor.

Peki Çizge Kuramı nerelerde kullanılıyor? Yani neden böyle bir şeyi öğrenmek isteyelim?

Bilişimde: algoritma yapımında, veri dopalamada, haberleşmede (telekomünikasyon), GPS’lerde

Dilbilimde: Sözdizimi kuralları çalışmalarında

Fizikte: Atomik yapıların incelenmesinde

Kimyada: Moleküler yapıların incelenmesinde

Nörolojide: Beyne benzer yapıların modellenmesinde

Sosyolojide: Sosyal grupların incelenmesinde, bilginin yayılmasının incelenmesinde

Biyolojide: Salgınların incelenmesinde

Matematikte: Topoloji alt dalında

kullanılıyor Çizge Kuramı.

Yani anlayacağınız epey bir yerde kullanılıyor :)

Çizge Kuramının giriş kavramlarını anlamak zor değil. Hemen bir örnekle giriş yapalım:

Kabataş Erkek Lisesi 12/C Sınıfını Çizge Kuramı ile Modellemek

Bu 10 öğrenci içinde belli arkadaş grupları var:

Kabataş Erkek Lisesi 12/C sınıfı

Bu arkadaş gruplarını Çizge Kuramıyla gösterelim:

Kabataş Erkek Lisesi 12/C sınıfı

Yani tüm bağlantılarımız şu şekilde:

  1. Grubun Bağlantıları

Ahmet<->Mehmet

Ahmet<->Ali

Ali<->Mehmet

2. Grubun Bağlantıları

Ece<->Gamze

Ece<->Leyla

Leyla<->Gamze

3. Grubun Bağlantıları

Özge<->Hasan

Özge<->Tolga

Özge<->Pınar

Pınar<->Tolga

Pınar<->Hasan

Hasan<->Tolga

Tüm “düğüm”lerimiz ise şunlar:

Ahmet, Mehmet, Ali , Ece, Gamze, Leyla, Hasan, Tolga, Pınar, Özge

İşte bu bağlantı ve düğüm bilgileri ile sınıfta kimlerin bulunduğunu ve kimin kim ile arkadaş olduğunu “Çizge”lemiş olduk.

Çizgesini çıkarmak demek, Ağ’ı çizmek demek değil. Ağdaki tüm “düğüm” ve “bağlantı” bilgilerini bir kağıda dökmek demek. Bir çizgede de önemli olan neyi nereye çizdiğimiz değil. Önemli olan kimin kim ile arkadaş olduğunu doğru gösterip göstermediğimiz.

Şimdi Çizge’miz üzerinden, Kabataş 12/C sınıfının bazı özelliklerini inceleyelim:

Yoğunluk:

Eğer çizgemizde kimse kimseyle arkadaş olmasaydı, çizgemizin hiç yoğunluğu olmayacaktı, yani 0 değerinde bir yoğunluğu olacaktı.

Şu anki çizgemizin yoğunluk değerini ise şöyle hesaplıyoruz:

T : Herkes arkadaş olsaydı, elimizde olacak toplam bağlantı sayısı,

B : Şu anki çizgemizde bulunan bağlantı sayısı,

Y : Çizgemizin yoğunluğu (biz bu değeri bulmak istiyoruz)

Y = B / T

Yani:

Yoğunluk = Şu anki bağlantı sayısı / Olabilecek maksimum bağlantı sayısı

Şu an çizgemizde 12 bağlantı var. Herkes herkesle arkadaş olsaydı çizgemizde 45 bağlantı olacaktı. Demek ki çizgemizin yoğunluğu 12/45.

Yani 0.26 gibi bir değer.

Unutmayın, yoğunluk değeri en fazla 1 olabiliyor.

Herkesin herkesle arkadaş olduğu durumdaki bağlantı sayısını nasıl hesapladım peki?

9 bağlantı. Çünkü sınıfta 10 kişi var, bunların biri zaten Ahmet’in kendisi. Ahmet kendisi dışında herkesle arkadaş olursa 9 bağlantısı oluyor.

Sınıftaki herkes için, yani 10 kişi için, Ahmet’e yaptığımız işlemin aynısını yaparsak, her bir kişinin 9 bağlantısı olur.

10 kişi * 9 bağlantı = 90 bağlantı

Ancak böyle yaptığımızda, herkesin bağlantılarını iki kere saymış oluruz. Örneğin Ahmet-Tolga bağlantısını bir kere Ahmet’in arkadaşlarında, bir kere de Tolga’nın arkadaşlarında saymış oluruz. Bu yüzden 90'ı ikiye bölmemiz gerekiyor.

90/2=45.

Yani herkes herkesle arkadaş olsaydı 45 bağlantı olurdu. Bu işlemin mantığı, şu formülle ifade ediliyor:

N: Ağdaki kişi sayısı

Olabilecek en fazla bağlantı sayısı = [N * (N-1)] / 2

Yoğunluğu anlamış isek, “Derece” kavramını inceleyelim.

Derece: Düğümün kaç komşusu olduğunu belirten sayı.

Yani bizim örneğimizde, öğrencinin kaç arkadaşı var ise, derecesi o sayı oluyor. Bu durumda Ahmet’in derecesi 2, Pınar’ın derecesi ise 3.

Ahmet ve Pınarın arkadaş sayıları. (dereceleri)

Şimdi daha karışık bir sınıf örneği ile, diğer kavramlardan da bahsedelim. Bu kez sınıfımızın adı 9/A sınıfı.

9/A sınıfını Çizge Kuramı ile Modellemek

9/A Sınıfı

Bir düğümün muhit’i (neighbourhood): Düğümün tüm komşularının oluşturduğu küme

Örnek: Emir’in Muhiti = {Orkan, Burak, Kerem}

Örnek: Emir’in 2. Dereceden Muhiti = {İlayda, Hatice, Yaren, Deniz, Orkan, Burak, Kerem}

2. Dereceden Muhiti dediğim zaman, Emir’e iki çizgi uzaklıkta olan kişileri de dahil etmiş oluyorum.

Walk: Bir düğümden başka bir düğüme herhangi bir şekilde giderken kullanılan herhangi bir yol.

Path: Bir düğümden başka bir düğüme, tekrar yapmamak (çember çizmemek, ileri geri yapmamak)koşulu ile giderken kullanılan herhangi bir yol.

Uzaklık: İki düğüm arasındaki en kısa yolun uzunluğu.

Betweenness (Arasındalık): Bir düğümün, diğer kaç düğümün arasına girdiğini gösteren birim.

Centrality (Merkezlik): Bir düğümün ne kadar merkezde olduğunu gösteren birim.

Centralization (Merkezillik): Bir Çizge’nin ne kadar toplu ve tek düğüme bağlanmış bir Çizge olduğunu gösteren birim.

İzole Düğüm: Diğer düğümlerle bağlantıları bulunmayan düğüm.

Örnekler:

Bu Path, aynı zamanda bir Walk özelliği gösteriyor.

Kerem’in “Arasındalık” Değeri:

Kerem, hangi düğüm çiftlerinin arasında bulunuyor? Yani kimden kime yürürken Kerem’in üzerinden geçmek zorundayız?

Cevap:

İlayda’dan: Deniz, Buse ve Can’a

Burak’tan: Deniz, Buse ve Can’a

Orkan’dan: Deniz, Buse ve Can’a

Emir’den: Deniz, Buse ve Can’a

Hatice’den:Deniz, Buse, Can, Yaren, Emir, Orkan, Burak ve İlayda’ya

Yaren’den:Deniz, Buse, Can, Hatice, Emir, Orkan, Burak ve İlayda’ya

Yürürken Kerem’in üzerinden geçmek zorundayız.

Yani Kerem’in Arasındalık değerinin oldukça yüksek olduğunu söyleyebiliriz.

Öte yandan İlayda’nın Arasındalık değeri sıfıra eşit.

İzole Nokta: 9/A sınıfında, Merve, izole noktaya bir örnek.

Merkezlik: Bunu ölçmenin birkaç yolu var, bu yollardan biri, direk olarak Arasındalık değerini kullanmak. Eğer Arasındalık değerini kullanarak Merkezliği bulmak istersek, merkezlik özelliği en yüksek olan düğümün Kerem olduğunu görürüz.

Merkezillik:

Soldaki ağ ve Sağdaki ağ arasındaki farkı hissedebiliyor musunuz?

Zincir tipine yaklaşan Ağların, Merkezillik değerleri az olur. Öte yandan bir ağ hem Yoğun’sa, hem de ağda Merkezliği çok yüksek bir düğüm var ise, o ağ Merkezillik değeri yüksek bir ağ oluyor.

Üstteki resimde soldaki Çizge’nin merkezilliği az iken, sağdaki Çizge’nin merkezilliği fazla. Unutmayın, merkezlik bir düğümün özelliğidir. Merkezillik, bir Ağ’ın özelliğidir.

Tekrar etmek gerekirse, bu yazıda Çizge Kuramına bir giriş yaptık. Düğüm, Bağlantı, Çizge, Yoğunluk, Derece, Muhit, Walk, Path, Uzaklık, Arasındalık, Merkezlik, Merkezillik ve İzole Düğüm gibi kavramların hakkında bir fikir sahibi olduk.

Eğer kendi Çizge’nizi oluşturmak ve onunla oynamak isterseniz, bu siteyi kullanabilirsiniz:

Önceden oluşmuş çeşitli çizgeleri incelemek ve onlarla oynamak, bazı ölçü değerlerini görmek isterseniz, yazının en üstündeki resmi aldığım siteyi, yani Polinode’u kullanabilirsiniz:

Bu linkte ise, IŞİD’in Türkiye’ye yaptığı saldırıları Çizge’ye dökülmüş biçimde görebilirsiniz:

Gelecek hafta görüşmek üzere!

NLP Engineer at PragmaCraft. Former Researcher at Bogazici University Medical Imaging Lab. twitter:ahmetmeleq /// website:ahmetmelek.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store