Popüler BilimFizikMatematik

Ağ Bilimi – 1: Giriş

Ağ bilimini ifade edebilmek için, öncelikle ağ ile neyi kast ettiğimiz anlaşılmalıdır. Bir ağ (network), en basit şekliyle çizgiler ile birbirlerine bağlanmış noktalar demektir. Matematiksel ifadeleriyle ağ çizge, nokta köşe, çizgi de kenar olarak adlandırılır. Bu niceliklerin bilgisayar bilimlerindeki karşılığı ise ağ, düğüm ve bağlantıdır. Fiziksel, biyolojik ve sosyal bilimlerdeki birçok sistem ağlar şeklinde ifade edilebilir. Düğüm ve bağlantıların çeşitli sistemlerdeki karşılıkları aşağıda gösterilmiştir.

Belirli ağlardaki düğüm ve bağlantıların örnekleri.

Çoğu ağda iki düğüm arasında tek bağlantı bulunur. Bazı durumlarda çoklu bağlantı da görülebilmektedir. Bununla birlikte bazı düğümler kendilerine de bağlantı yapabilirler.

Tanımlar

Ağ biliminde, bir ağda çoklu bağlantı veya kendine bağlantı yoksa bu ağ basit ağ olarak adlandırılır. Eğer çoklu bağlantı varsa, ağa çoklu bağlantılı ağ, eğer kendine bağlantı varsa, ağa kendine bağlantılı ağ adı verilir.

Basit ağa örnek (solda), hem çoklu bağlantı hem de kendine bağlantı içeren ağa bir örnek (sağda). Düğümler sayılarla isimlendirilmiştir.

Ağ biliminde ağların matematiksel olarak ifade edilebilmeleri için farklı yollar vardır. Bir ağın bitişiklik matrisi A,
kare bir matristir ve her bir elemanı Aij olacak şekilde şöyle açıklanabilir:

Çoklu bağlantılar veya kendine bağlantılar da bitişiklik matrisinde yer alabilir. Yukarıdaki ağların bitişiklik matrisi aşağıdaki gibidir:

Soldaki bitişiklik matrisinin köşegeni sıfırdır ve matris simetriktir. Sağda ise simetri olmasına rağmen, ağ kendine bağlantı içerdiği için köşegeni sıfır değildir. Kendine bağlantıları içeren köşegen değerlerinin neden 1 değil de 2 olduğu bize, ağlarda bağlantı türlerinin en başta iki gruba ayrılacağını söyler.

Yönsüz Ağlar ve Yönlü Ağlar

Ağ biliminde bir sistemin ağ yapısı altında incelenmesinde ilk belirlenmesi gereken ağın yönsüz mü yoksa yönlü mü olduğudur. Yönsüz ağlar N adet düğüm ve E adet çift yönlü kabul edilen bağlantı ile G=(N,E) şeklinde tanımlanır. Örneğin yukarıdaki şekilde 1 ve 4 düğümleri arasındaki bağlantı çift yönlüdür (↔ şeklinde düşünülebilir). Yönsüz ağlarda kendine bağlantı varsa, bağlantı yine çift yönlü olduğu için ilgili düğümün matris köşegen değeri 2 olmaktadır.

Yönlü ağlarda ise bağlantılar tek yönlüdür. Yönlü bağlantılar olarak da adlandırılırlar ve uçlarında ok işareti olan çizgiler ile gösterilirler (→). N adet düğüm ve E adet tek yönlü bağlantı ile yine G=(N,E) şeklinde tanımlanırlar. Yönlü ağlarda bitişiklik matrisinin elemanları

şeklinde tanımlanır. G=(N,E) olarak ifade edilen yönlü ağlarda düğümlerin kümesi N=N(G), bağlantıların kümesi E=E(G) şeklinde tanımlanır. s1 N düğümünden s2 N düğümüne giden e E bağlantısında s1 e’nin kuyruğu, s2 de e’nin başıdır. Eğer ağ çoklu bağlantılar içermiyorsa s1 ve s2 arasında birden fazla bağlantı olamaz ve olan tek bağlantı s1s2 şeklindedir. Ağ biliminde yönsüz ağlar ve yönlü ağlara aşağıda örnekler verilmiştir.

İzmir için otoyol haritası. Düğümler ilçe ve şehir merkezleri, bağlantılar yollardır. Otoyollar gidiş-geliş olarak çift yönlüdür ve ağ yönsüzdür.
ağ bilimi internet ağı
Dünya’daki internet ağı (World Wide Web) bir sayfadan diğerine tek yönlü
bağlantı (köprü) esasına göre çalıştığı için yönlü ağ yapısındadır.

Doğada ve geliştirdiğimiz teknolojilerde, yönlü ağlar ile ifade edilebilecek sistemlerin sayısı oldukça fazladır. Yönsüz ağlardaki gibi, yönlü ağlarda da çoklu bağlantılar ve kendine bağlantılar olabilir. Ancak kendine bağlantılarda artık çift yönlülük olmayacağından bitişiklik matrisinde ilgili köşegen değeri 1 olmalıdır. Bununla birlikte yönsüz ağların bitişiklik matrisleri simetrikken yönlü ağların simetrik olmak zorunda değildir.

Yönlü bir ağ ve bitişiklik matrisi. Matris simetrik değildir ve 5. düğümün
köşegen değeri 1’dir.

Ağırlıklı Ağlar

Ağ biliminde buraya kadar yönsüz veya yönlü ağlarda, düğümler arası bağlantıların hep var olup olmamaları ile ilgili değinmeler yapılmıştır. Ancak bazı durumlarda bağlantılar gerçel sayılar kümesinde bazı değerler alırlar. Her bir bağlantı için 1 veya diğer pozitif tamsayılardan olma zorunluluğu yoktur. Buna bağlantının ağırlığı, büyüklüğü veya kuvveti denilebilir. Bu tip ağlara ağırlıklı ağlar denir. Gösterimlerinde bağlantının büyüklüğüne göre kalınlığı oranlanmıştır. Yönsüz ve yönlü ağ yapıları ağırlıklı olabilir.

Bir Eurovision şarkı yarışması oylamalarının yönlü ve ağırlıklı ağı.

Ağırlıklı ağlar için örnek bir bitişiklik matrisine bakarsak

Bir ve ikinci düğümler arasındaki bağlantının (matrisin 1. satır, 2. sütun değeri veya tam tersi olan 2. satır, 1. sütun değeri) 1. ve 3. düğümler arasındakinden iki kat, 2. ve 3. düğümler arasındakinden dört kat daha büyük olduğunu görebiliriz.

Ağırlıklı ağlar için tüm topolojik ve dinamik hesaplar, ilgili eşitliklere bağlantı ağırlığının eklenmesiyle farklılaşır. Bununla birlikte ağırlıklı bağlantılar çoklu bağlantılar şeklinde ifade edilerek, çoklu bağlantılı bir ağa dönüştürülebilir. Ağırlıklı olarak modellenen bazı ağlarda ağırlıksız bağlantılara normalizasyon da vardır.


Hazırlayan: Emir Haliki

Referanslar
1. Newman, M. E. J., 2010, Networks: An introduction, Oxford University Press,
New York, 740p.
2. Newman, M. E. J., 2004, Analysis of weighted networks, Physical Review E,
70:056131 pp.
3. Huber, K. T. and Moulton, V., 2006, Phylogenetic networks from multi-labelled
trees, Journal of Mathematical Biology, 52:613-632 pp.
4. Karayolları Genel Müdürlüğü, 2015, Otoyollar Haritası – İzmir,
<http://www.kgm.gov.tr/Sayfalar/KGM/SiteTr/Otoyollar/Otoyollar.aspx>
5. CCNR, 2007, Map of Internet: colored by IP addresses,
<http://www3.nd.edu/~networks/Image%20Gallery/gallery.htm#Internet>

Emir Haliki

Ege Üniversitesi Fen Fakültesi - Fizik Bölümünde Doktor Araştırma Görevlisi. Ağ bilimi, astrobiyoloji, genetik düzenlenme mekanizmaları, karmaşık sistemler ve astronomik cisimler çalışma alanı. Aynı zamanda matematik ve sayısal çözümleme de ilgi alanları. Bunların yanında amatör olarak, gözlemsel astronomi, doğa yürüyüşleri, satranç ve robotik kodlama ile ilgileniyor.
Başa dön tuşu
Bilim dünyasındaki önemli gelişmelerden haberdar olmak için haftalık/aylık bültenimize abone olun.
Devam ederek gizlilik politikasını kabul etmiş olursunuz.