Oct 10, 2018
Graph Theory (Çizge Kuramı) nedir?
“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
Kabataş Erkek Lisesinde, 12/C sınıfında toplam 10 öğrenci bulunsun.
Bu 10 öğrenci içinde belli arkadaş grupları var:
Bu arkadaş gruplarını Çizge Kuramıyla gösterelim:
Yani tüm bağlantılarımız şu şekilde:
- 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 ki çizgemizde herkes, herkesle arkadaş olsaydı, çizgemizin tam bir yoğunluğu olacaktı, yani 1 değerinde bir yoğunluğu olacaktı.
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?
Ahmet üzerine düşünelim, Ahmet herkesle arkadaş olsaydı, Ahmet’in kaç bağlantısı olacaktı?
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.
Ş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
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:
Burak’tan Can’a bir Path:
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:
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!
