Community detection in complex networks using local methods and information flow

Abstract

Gerçek hayattaki birçok sistem ağ gösterimi kullanılarak temsil edilebilir. Ağ gösteriminde, sistemi oluşturan bileşenler düğümlerle; bu bileşenlerin arasındaki ilişkiler ise bağlantılarla gösterilir. Özel bir ağ tipi olan karmaşık ağlar ise sistemin bileşenlerinin birbiriyle etkileşimi sonucu ortaya çıkan özelliklere sahiptir. Ağlardaki küme yapısı bu özelliklerden biridir. Bir ağ içindeki kümelenme, birbiriyle daha sıkı bağlarla bağlanmış düğümlerden oluşur; bu düğümlerin ağ içindeki diğer düğümlerle ise daha az bağlantısı bulunmaktadır. Bir ağ içinde bu tip kümelenmeleri bulmak, ağ içinde benzer özellik veya fonksiyona sahip alanların tespiti, bilginin dağılımı veya hastalık yayılımı gibi birçok alanda önemli kullanım alanına sahiptir. Bu tezde, karmaşık ağlardaki kümeleri yerel yaklaşımlı algoritmalarla (ör: ortak arkadaşlar üzerinden benzerlik) ve bilgi yayılımı yöntemleriyle (ör: dedikodu yayılımı) tespit etme üzerinde çalışmalar yaptık. Mevcutta kullanılan algoritmaları inceleyerek bunların yetersiz kaldığı alanları tespit ettik. Tüm ağ üzerinde bir değeri iyileştirmeye çalışan küresel yaklaşımlı algoritmaların uzun çalışma sürelerine sahip olduklarını gördük. Yerel yaklaşım kullanarak, düğümlerin benzerlikleri ve dedikodu yayılımını baz alan algoritmalar geliştirdik. Yerel yaklaşımlı algoritmaların çalışması için, bir düğüm etrafındaki kısıtlı bilgi yeterli olmaktadır. Bu sayede, küme işlemi paralel ve dağıtık şekilde ağın farklı yerlerinde eşzamanlı yapılabilmektedir. Bununla birlikte, bilinen bir küme bulma algoritmasını baz alarak (etiket yayılım algoritması), algoritmada gereksiz yapılan adımları ortadan kaldıran bir yaklaşımla, çalışma zamanını kısaltan yeni bir algoritma geliştirdik. Tez çalışmaları sırasında tanımladığımız bu algoritmaların tanımlanması sürecinde yeni bir geliştirme altyapısı da oluşturduk.

Many real world systems can be represented using networks or graphs where elements of system are denoted by nodes and their relations by edges. Complex networks are special kinds of these networks with their emergent features created by interactions among nodes. One such emergent feature is the community structure. A community is a group of nodes where nodes within same community have more connections (i.e., edges) with each other than with the nodes in the rest of the network. Identifying such communities is the task of community detection that can be used to identify nodes with similar functions or features, densely connected regions in networks, information flow patterns and spreading of a disease or information in a network.In this thesis, we work on community detection on complex networks using local approach and information diffusion. We investigate current algorithms and try to understand the limitations of them. We especially focus on high time-complexity of algorithms because of using global approach, i.e., try to optimize a global metric or perform computations regarding the whole network repeatedly. We propose new algorithms using local approach (i.e., similarity based on common friends) and information diffusion (i.e., gossip spreading). Local approach uses locally available or computable information around a node to identify its community. With this, community detection task can be seen as a set of distributed and parallel tasks running simultaneously on different parts of the network. We also propose a variant of label propagation algorithm which decreases its overall execution time by eliminating unnecessary steps. During these studies, we develop a community detection framework which simplifies the task of defining, testing and comparing a new community detection algorithm.