K-partitioning of Signed or Weighted Bipartite Graphs

Date

2013-09-14

Author

Omeroglu, Nurettin B.
Toroslu, İsmail Hakkı
Gokalp, Sedat
Davulcu, Hasan

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

104
views

0
downloads

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.

Subject Keywords

Social networks, Bipartite graphs, Graph partitioning

URI

https://hdl.handle.net/11511/36279

DOI

https://doi.org/10.1109/socialcom.2013.122

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Local search versus Path Relinking in metaheuristics: Redesigning Meta-RaPS with application to the multidimensional knapsack problem Arin, Arif; Rabadi, Ghaith (Elsevier BV, 2016-09-01) Most heuristics for discrete optimization problems consist of two phases: a greedy-based construction phase followed by an improvement (local search) phase. Although the best solutions are usually generated after the improvement phase, there is usually a high computational cost for employing a local search algorithm. This paper seeks another alternative to reduce the computational burden of a local search while keeping solution quality by embedding intelligence in metaheuristics. A modified version of Path ...
Improving search result clustering by integrating semantic information from Wikipedia Çallı, Çağatay; Üçoluk, Göktürk; Şehitoğlu, Onur Tolga; Department of Computer Engineering (2010) Suffix Tree Clustering (STC) is a search result clustering (SRC) algorithm focused on generating overlapping clusters with meaningful labels in linear time. It showed the feasibility of SRC but in time, subsequent studies introduced description-first algorithms that generate better labels and achieve higher precision. Still, STC remained as the fastest SRC algorithm and there appeared studies concerned with different problems of STC. In this thesis, semantic relations between cluster labels and documents ar...
Efficient performance computations for trellis-coded modulation Abou Rajab, H; Yucel, MD (1999-06-01) In this letter, the algorithm given by Rouanne and Costello for the computation of the distance spectrum is improved for trellis-coded modulation schemes having uncoded bits, i.e., for trellis diagrams having parallel paths, It is shown that, when through a trellis corresponding to such kind of codes, all parallel transitions (labeled by signal selectors) between states are considered as a single branch labeled by a subset, then defining subset selector distance polynomials makes the computational complexit...
Integer programming approaches to the dominating Tree problem Akifoğlu, Selin; Tural, Mustafa Kemal; Department of Industrial Engineering (2016) Let G=(V,E) be a simple undirected edge-weighted graph, where V and E denote the set of vertices and edges of G, respectively. The Dominating Tree Problem (DTP) searches for a minimum weighted tree in G, say DT, such that each vertex either belongs to DT or is one-hop away from DT. This problem is an NP-hard but a practical problem. The solution of the DTP is used to construct a backbone for wireless sensor networks, which have a wide usage in many industrial and consumer applications. In this thesis, diffe...
Reevaluating Spectral Partitioning for Unsymmetric Matrices Oktay, Eda; Manguoğlu, Murat; Yücel, Hamdullah; Department of Scientific Computing (2020-9) Parallel solutions to scientific problems having graph representation require efficienttasks and partitioning data. In this thesis, various parallel graph partitioning algorithms are studied. While these algorithms are applicable to both directed and undirected graphs, we focus on the directed case whose matrix representations are sparse and unsymmetric arising in linear system of equations representing various application domains such as computational fluid dynamics and thermal problems. Strategies inspec...

Citation Formats

N. B. Omeroglu, İ. H. Toroslu, S. Gokalp, and H. Davulcu, “K-partitioning of Signed or Weighted Bipartite Graphs,” 2013, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/36279.