K?way partitioning of signed bipartite graphs

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2012

Öğrenci: NURETTİN BURAK ÖMEROĞLU

Danışman: İSMAİL HAKKI TOROSLU

Özet:

Clustering is the process in which data is differentiated, classified according to some criteria. As a result of partitioning process, data is grouped into clusters for specific purpose. In a social network, clustering of people is one of the most popular problems. Therefore, we mainly concentrated on finding an efficient algorithm for this problem. In our study, data is made up of two types of entities (e.g., people, groups vs. political issues, religious beliefs) and distinct from most previous works, signed weighted bipartite graphs are used to model relations among them. For the partitioning criterion, we use the strength of the opinions between the entities. Our main intention is to partition the data into k-clusters so that entities within clusters represent strong relationship. One such example from a political domain is the opinion of people on issues. Using the signed weights on the edges, these bipartite graphs can be partitioned into two or more clusters. In political domain, a cluster represents strong relationship among a group of people and a group of issues. After partitioning, each cluster in the result set contains like-minded people and advocated issues. Our work introduces a general mechanism for k-way partitioning of signed bipartite graphs. One of the great advantages of our thesis is that it does not require any preliminary information about the structure of the input dataset. The idea has been illustrated on real and randomly generated data and promising results have been shown.