Classification of complex networks in terms of topological properties

Abstract

Sayısız gerçek sistemi, etkileşim halindeki düğümler ve aralarındaki ilişkileri kullanarak incelleyen karmaşık ağlar güçlü bir modelleme aracıdır. Bilgisayar bilimlerinden biyolojiye, sosyolojiden yönetim bilimlerine kadar pek çok farklı alanda kullanılmaktadır. Karmaşık ağ analizinde, uygulandığı sistemin ilk bakışta belirlenemeyecek özellikleri ortaya çıkarılmaya çalışılır. Bu kapsamda derece dağılımı, geçişlilik veya ortalama uzaklık gibi çeşitli ölçekler kullanarak ağ yapıları karakterize edilmeye çalışılmaktadır. Küçük Dünya etkisi ya da Ölçeksiz ağ gibi bazı karakteristik karmaşık ağ özellikleri bu şekilde tespit edilir. Önceki çalışmalar farklı alanlardaki karmaşık ağların benzer karakteristik özellikler taşıdığını göstermiştir. Ancak bunlar, genel olarak az sayıda ağ üzerinde ve az sayıda ölçekğe odaklanarak gerçekleştirimiştir. Bu çalışmada önceki çalışmalardan farklı olarak daha sistematik bir yaklaşım kullanılması hedeflenmiştir. Bu doğrultuda Bimoleküler, Sosyal, Ekolojik, Bilgisayar, Ulaşım, Alıntı ve İletişim olmak üzere 7 farklı alandan toplamda 152 tane yayınlanmış ağ toplanarak bir ağ havuz oluşturulmuştur. Havuzu oluşturan ağların, mümkün olan en detaylı şekilde karakterize edilebilmesi için 14 farklı topolojik ölçek kullanılmıştır. Ardından, standart veri madenciliği algoritmaları kullanılarak ölçümler arasındaki korelasyon belirlenmiştir. Tukey testi ile tamamlanan Varyans Analizi sonucunda havuzda bulunan ağ alanları iki gruba ayrılmıştır. Bu şekilde bir guruplaşmaya sebep olan ölçekler ortalama uzaklık, geçişlilik, modülerlik ve ıolarak belirlenmiştir. Bu sonucu doğrulamak için uygulanan kümeleme algoritmaları sonucunda da, önceki testi doğrular şekilde, 7 farklı alanın bir kümede 4(Biomoleküler, Ulaşım, Alıntı, Bilgisayar) ve diğerinde 3 (Sosyal, İletişim and Ekoloji) alan olacak şekilde 2 kümede gruplandığı gözlenmiştir. Kümeler ile yapılan ek bir Varyans Analizi de önceki analizin belirttiği ölçekleri doğrularken, bunu yanı sıra ağ çapı, ortalama mesafe, yakınlık merkezi konumu, yerel geçişlilik ve bağlantı merkeziliği ölçeklerini işaret etmiştir.

Complex networks are a powerful modeling tool, allowing the study of countless real-world systems. They have been used in very different domains such as computer science, biology, sociology, management, etc. Authors try to characterize them using various measures such as degree distribution, transitivity or average distance. Their goal is to detect certain properties such as the small-world or scale free properties. Previous works have shown some of these properties are present in many different systems, while others are characteristic of certain types of systems. However, each one of these studies generally focuses on a very small number of measures and networks. In this work, we aim at using a more systematic approach. We first constitute a corpus of 152 publicly available networks, spanning over 7 different domains. We then process 14 different topological measures to characterize them in the most possible complete way. We apply standard data mining tools to study correlation between the properties and identify which ones are discriminant or non-discriminant. An ANOVA completed by Tukey?s test reveals two groups of domains can be distinguished in terms of average degree, modularity, transitivity and density. We apply cluster analysis tools to confirm these results, and find two more precisely defined clusters, in which the 7 domains are clearly separated (3 in a cluster, 4 in the other). An additional ANOVA confirms the previously mentioned measures are discriminant indeed, and additionally identifies diameter, average distance, closeness centrality, local transitivity and edgebetweenness centrality.