Yazan : Şadi Evren ŞEKER
Bu yazının amacı karmaşık sistemlerdeki topluluk yapılarını bulmaya yarayan Girvan-Newman algoritmasını anlatmaktır. Algoritma, Michelle Girvan ve Mark Newman tarafından geliştirilmiş olup bu kişilerin soy ismi ile anılmaktadır.
Algoritma oldukça basit bir iddia üzerine kuruludur. Bir toplulukta birden fazla grup olduğunu kabul edelim. Buna göre grupların kendi içlerindeki ilişkileri yoğun, gruplar arası ilişkiler ise daha seyrek olur.
Örneğin telefon etme sıklıklarını ele alalım. Bir ülkedeki grupları tanımlarken aile kavramını kullanırsak, bir toplulukta aile içi telefonlaşmalar, aileler arası telefonlaşmalara göre daha sık olacaktır. Benzer şekilde grup tanımımız şirketler olursa bu durumda Girvan-Newman algoritması bize şirket içindeki bireylerin birbiri ile telefon görüşmelerinin, şirketler arası telefon görüşmelerine göre daha sık olduğunu söyler.
Şimdi soru, bu grupların nasıl bulunacağıdır. Örneğin size bir ülkedeki bütün telefon görüşmelerinin verildiğini ve bu görüşme sıklıklarından grupları çıkarmanız istendiğini düşünelim. Böyle bir problemin çözümünde kullanılacak bazı yollar aşağıdaki şekilde sıralanabilir:
-
Hiyerarşik bölütleme (hierarchical clustering)
-
k-klik araması (k-clique percolation)
-
Şekil parçalaması (graph partitioning)
Yukarıdaki bu yöntemlerin üzerinden geçip Girvan-Newman algoritmasının farkını açıklamaya çalışalım.
Örneğin hiyerarşik bölütleme (hierarchical clustering) yaklaşımında, bağlantılar öncelikle boş bir ağda tanımlanır ve ilk değer olarak 0 atanır. Ardından ilişkinin derecesine göre bu ilişkilere ağırlık verilir. En yüksek ağırlığa sahipten en zayıf ağırlığa doğru işlem yapılır. Genelde en yüksek ağırlığa sahip olan birey, merkezi olma özelliği gösterir. Ayrıca ilişki tipi zayıfladıkça hata miktarı da artar. Örneğin tek bir bağlantısı olan bireyin o grubun üyesi olduğunu söylemek çok da doğru olmayabilir.
Girvan-Newman algoritması yukarıda anlatılan hiyerarşik bölütlemenin tam tersini yapar. Merkezi bireylerden başlamak yerine, kenarda kalmış ve düşük ağırlığa sahip bağlantıları bulunan bireylerden başlar. Bu kenarda kalan bireyleri eleyerek çalışmaya devam eder. Bu işlem de hiyerarşik bölütlemenin tam tersidir çünkü hiyerarşik bölütlemede boş bir ağdan başlanarak her adımda yeni bireyler sisteme eklenmektedir, Girvan Newman algoritmasında ise her adımda ağdan bir birey çıkarılır.
Telefon görüşmesi örneğine dönecek olursak, hiyerarşik bölütleme yaklaşımında, ilk başta hiç birey yokken boş bir ağ ile başlanır ve bu ağa en çok görüşme yapan bireyler eklenerek algoritma ilerler. Girvan-Newman algoritmasında ise önce bütün bireylerin kimi aradığı ve kaç görüşme yaptığı gibi bilgilerin tutulduğu bir ağ ile başlanır, bu ağdan her adımda en az görüşme yapan veya en az kişi ile görüşme yapan birey elenerek ilerlenir.
Girvan-Newman algoritmasının getirdiği bir yenilik de orta birey değeri hesabındadır (vertex betweenness). Orta birey (vertex betweenness) kavramı, merkezilik adına uzun süre incelenmiş bir durumdur. Herhangi bir i bireyi için, bu bireyin orta bireylik değeri, bu birey üzerinden geçen en kısa yolların sayısıdır. Yani ağımızda (network) tanımla n adet düğüm için, bu düğümlerin ikili olarak ele alınması halinde, aralarındaki en kısa yollardan (shortest paths) kaç tanesi bu i bireyi üzerinden geçiyorsa, i bireyinin orta bireylik değeri budur.
Örneğin aşağıdaki şekil için durumu inceleyelim:
Şekildeki her düğüm ikilisi için en kısa yolun geçtiği düğümlerin listesini yazıyorum. Burada her kenar uzunluğunu 1 kabul ediyorum. Yani ağırlıklı bir şekil (weighted graph) olarak kabul edilirse, ağırlık değerleri her bağlantıda 1 olacak.
1-2 : {1,2}
1-3 : {1,3}
1-4 : {1,4}
1-5 : {1,4,5}
2-3 : {2,1,3} veya {2,4,3}
2-4 : {2,4}
2-5 : {2,4,5}
3-4 : {3,4}
3-5 : {3,4,5}
4-5 : {4,5}
Yukarıdaki listelerde her düğümün (node) kaçar kere geçtiğini listeleyecek olursak:
1 : 5 kere
2 : 4 kere
3 : 4 kere
4 : 7 veya 8 kere
5 : 4 kere
Listeden anlaşılacağı üzere en yüksek orta bireylik değerine sahip düğüm 4 olarak bulunmuştur.
Girvan-Newman algoritması, bu orta bireylik değerini biraz değiştirir ve orta bağlantı (edge betweenness) kavramını getirir. Buna göre iki bireyi bağlayan herhangi bir bağlantı için üzerinden geçen en kısa yol sayısı sayılarak bu bağlantının orta bağlantı değeri hesaplanır.
Bu değerin nasıl hesaplandığını, yine aynı örnek üzerinden kenarlara (edges) isim vererek görelim:
1-2 : {a}
1-3 : {b}
1-4 : {f}
1-5 : {f,e}
2-3 : {a,b} veya {d,c}
2-4 : {d}
2-5 : {d,e}
3-4 : {c}
3-5 : {c,e}
4-5 : {e}
Benzer şekilde her kenarın kaçar kere geçtiğini sayalım:
a: 2
b: 1 veya 2
c: 2 veya 3
d: 2 veya 3
e: 4
Görüldüğü üzere en yoğun bağlantımız e kenarıdır.
Şayet birden fazla bağlantı aynı değerlerle en kısa yol sayısına sahipse, bu bağlantılar birbiri ile ilişkilendirilerek daha uzun bir bağlantı elde edilebilir.
Örneğimize dönecek olursak e kenarı olmasaydı, c ve d kenarları eşit yoğunlukta olduğu için bu iki kenarı birleştirerek tek bir kenar gibi düşünebilirdik.
Girvan-Newman algoritması, tam bu noktada devreye girerek en yüksek değere sahip kenarları sistemden çıkarmaya başlar (okuyucu, en yüksek değere sahip kenarın aslında sistemin en kenarında kalmış bireyler olduğunu düşünerek bulabilir, nitekim örnekteki 5. düğüm bu şekilde bir düğümdür). Böylelikle şekildeki bazı bireyler veya birey grupları sistemden kopmaya başlar. Örneğimiz aşağıdaki şekilde olsaydı:
Bahsi geçen kopma, bu şekildeki e kenarının kaldırılması durumunda sistemde iki ayrı grup olmasıdır. İşte Girvan-Newman algoritması da bütün bu ağ yapısında birbiri ile yoğun ilişkisi olan iki grubu bulmayı amaçlamış ve bulmuştur. En baştaki örneğimize dönersek ve bu ağdaki telefon görüşmeleri ise (ve herkes birbirini 1 kere aramış dolayısıyla bütün bağlantılarda 1 ağırlığına sahip olunmuş kabul edileiblir) iki ayrı aileyi veya şirketi ağda bulmuş oluruz.
Algoritmanın adımları aşağıdaki şekilde sıralanabilir:
- Bütün kenarlar için orta bağlantı değeri hesaplanır
- En yüksek orta bağlantı değerine sahip bağlantı (veya aynı değere sahip birden fazla bağlantı varsa bunların tamamı) kaldırılır
- Kalıdrma işleminden sonra bütün orta bağlantı değerleri yeniden hesaplanır.
- Yukarıdaki 2. ve 3. adımlar hiçbir kenar kalmayana kadar tekrar edilir.
Girvan-Newman algoritmasına göre, şayet iki grubu bağlayan birden fazla bağlantı varsa, bu bağlantıların aynı anda en yüksek orta bağlantı değerine sahip olması beklenemez. Ancak bunlardan en az bir tanesinin en yüksek orta bağlantı değeri olduğu kesindir. Ayrıca bu en yüksek bağlantı kaldırıldıktan sonra bu iki grubu bağlayan bağlardan geri kalanlarından en az birisi yine en yüksek bağlantı değerini mutlaka taşır.
Girvan-Newman algoritmasının sonucu bir öbekağacı (dendrogram) olarak düşünülebilir. Girvan-Newman algoritması çalıştıkça her dönüşte (iteration) ağacı yukarıdan aşağıya (top-down) doğru oluşturmaktadır ve bu ağırlıkağacının yaprakları aslında ağdaki bireylerden oluşmaktadır.