K-partitioning of Signed or Weighted Bipartite Graphs

Omeroglu N. B., TOROSLU İ. H., Gokalp S., Davulcu H.

ASE/IEEE International Conference on Social Computing (SocialCom), Washington, Kiribati, 8 - 14 Eylül 2013, ss.815-820 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1109/socialcom.2013.122
  • Basıldığı Şehir: Washington
  • Basıldığı Ülke: Kiribati
  • Sayfa Sayıları: ss.815-820
  • Anahtar Kelimeler: Social Networks, Bipartite Graphs, Graph Partitioning
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this work, K-partitioning of signed or weighted bipartite graph problem has been introduced, which appears as a real life problem where the partitions of bipartite graph represent two different entities and the edges between the nodes of the partitions represent the relationships among them. A typical example is the set of people and their opinions, whose strength is represented as signed numerical values. Using the 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. In the paper, we formally define the problem and compare different heuristics, and show through both real and simulated data the effectiveness of our approaches.