Community detection using agents in complex networks
Yazılım ajanları kullanarak karmaşık ağlarda alttopluluk bulma
- Tez No: 181309
- Danışmanlar: DR. HALUK BİNGÖL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2006
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bu çalışma karmaşık ağların incelenmesine yönelik bir çalışmadır. Temel olarak, birağdaki alttoplulukları yazılım ajanları kulanılarak bulmayı sağlayan yeni bir algoritmatanıtılacak, ilgili altyapı detaylı olarak verilecek ve çeşitli ağlar için algoritma performansıgözlenecektir.Öncelikle, karmaşık ağlarda temel kavramlar tanıtılacak ve yazılım ajanlarınınkullanımına ilişkin bilgiler verilecektir. Daha sonra, karmaşık ağlarda alttopluluk yapısınıortaya çıkaran mevcut algoritmalar tanıtılacaktır. Bir karmaşık ağda, kendi elemanlarıaralarında yoğun olarak bağlı olan, ancak diğer elemanlarla seyrek olarak bağlı olan altgruplar, alttopluluk olarak tanımlanır. Bugüne kadar, alttopluluk yapısını ortaya çıkarmakiçin çok çeşitli algoritmalar sunulmuştur, ancak bu algoritmaların da bir takım eksikliklerivardır. Örnek olarak, bu algoritmaların bir çoğu, doğru şekilde çalışabilmek için ağhakkında bazı ön bilgilere ihtiyaç duyar ki, bu gerçek hayatta çok uygulanabilir bir yoldeğildir. Ayrıca, zaman karmaşıklığı yüksek olan bazı algoritmalar ise sadece küçük ağlarauygulanabilmektedir. Geliştirdiğimiz algoritma, karmaşık ağlarda alttopluluk bulmak içinyeni bir yöntem önermekte ve bu sorunlara çözüm getirmektedir.Algoritmamız, ağ hakkında bilgi edinmek için yazılım ajanlarını, altopluluklara kararvermek içinse ağ modülerliğini (network modularity) temel almaktadır. Algoritmayı testederken, sonuçların doğruluğunu görebilmek için Zachary'nin Karate Kulübü ağı gibialttopluluk yapısı bilenen ağlarla, karmaşıklığını ve ölçeklenebilirliğini test etmek içinseReuters ağı gibi büyük ağlarla çalışıldı. Ayrıca, kendi oluşturduğumuz ve internetsitelerinin ziyaret edilme bilgilerinden oluşan internet ağı için de algoritmamızı test edildi.Bunun yaninda algoritma performansı, bilgisayar tarafından üretilen yapay ağlar için detest edildi. Sonuç olarak, algoritmanın kabul edilebilir zamanda, optimuma yakınalttoplulukları ortaya çıkardığını söyleyebiliriz.
Özet (Çeviri)
The main purpose of this work is analyzing the complex networks. Mainly, a newcommunity detection algorithm based on using software agents will be introduced. Thetechnical background will be given in details and the performance of the algorithm fordifferent networks will be examined.First, the main concepts in complex networks and the information about usage of thesoftware agents will be introduced. Then, the current methods finding the communities incomplex networks will be presented. The community is defined to be the group of nodeswhich are densely connected within the group but rarely connected to the outside. Therehave been many algorithm proposed so far to detect the communities in complex networks.However, most of them have some weaknesses. For instance, some algorithms need someprior information about the network to find the communities such as number ofcommunities. There are also some algorithms with higher complexity values. Yet, thesealgorithms are not feasible or applicable to the real world complex networks. Ouralgorithm proposes a new algorithm to detect the communities in complex networks andaddresses these issues.An algorithm is developed that utilizes software agents for gathering informationabout the network and uses network modularity to decide on the community amongcandidates. To test the accuracy of the algorithm, the networks with known communitystructure like Zachary Karate Club network are used. The large networks such as web sitesnetwork that we created by observing a proxy server are also used to test the complexityand scalability of the algorithm. Besides, the performance with a computer generatednetwork is also presented. Finally, it can be said that the algorithm is able to reveal thenearly optimum communities with acceptable complexity.
Benzer Tezler
- Veri merkezleri için makine öğrenmesi temelli izleme sistemi tasarımı
Machine learning based monitoring system design for data centers
METEHAN HAN
- Konut bölgelerinde parsel düzeni uygulamasının kent topraklarının rasyonel kullanımı çerçevesinde mimari açıdan değerlendirilmesi
An Architeet's Criticism of the Currently Practised method of plot formation in residential areas from the point of View of rational utilization of urban deatories
SUZAN ESİRGEN
