K-way partitioning of signed bipartite graphs

Download
2012
Ömeroğlu, Nurettin Burak
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.

Suggestions

Fuzzy querying im XML databases
Üstünkaya, Ekin; Yazıcı, Adnan; Department of Computer Engineering (2004)
Real-world information containing subjective opinions and judgments has emerged the need to represent complex and imprecise data in databases. Additionally, the challenge of transferring information between databases whose data storage methods are not compatible has been an important research topic. Extensible Markup Language (XML) has the potential to meet these challenges since it has the ability to represent complex and imprecise data. In this thesis, an XML based fuzzy data representation and querying s...
Apply Quantitative Management Now
TARHAN, AYÇA; Demirörs, Onur (Institute of Electrical and Electronics Engineers (IEEE), 2012-05-01)
The Assessment Approach for Quantitative Process Management (A2QPM) helps identify software process measures for quantitative analysis even when organizations lack formal systems for process measurement. A2QPM is the first approach to quantitative management that offers software organizations a well-defined, detailed guideline for assessing their software processes and applying beneficial quantitative techniques to improve them. All the A2QPM applications we've described resulted in quantitative analysis im...
Mask Combination of Multi-Layer Graphs for Global Structure Inference
Bayram, Eda; Thanou, Dorina; Vural, Elif; Frossard, Pascal (2020-01-01)
Structure inference is an important task for network data processing and analysis in data science. In recent years, quite a few approaches have been developed to learn the graph structure underlying a set of observations captured in a data space. Although real-world data is often acquired in settings where relationships are influenced by a priori known rules, such domain knowledge is still not well exploited in structure inference problems. In this paper, we identify the structure of signals defined in a da...
Clustering of manifold-modeled data based on tangent space variations
Gökdoğan, Gökhan; Vural, Elif; Department of Electrical and Electronics Engineering (2017)
An important research topic of the recent years has been to understand and analyze data collections for clustering and classification applications. In many data analysis problems, the data sets at hand have an intrinsically low-dimensional structure and admit a manifold model. Most state-of-the-art clustering methods developed for data of non-linear and low-dimensional structure are based on local linearity assumptions. However, clustering algorithms based on locally linear representations can tolerate diff...
Co-clustering signed 3-partite graphs
Koç, Sefa Şahin; Toroslu, İsmail Hakkı; Department of Computer Engineering (2017)
Real world data is complex and multi-related among itself. Considering a social media, multiple users can interact with same item such as commenting, liking etc. Data composed of these actions contains many nodes from different types (user, item, sentiment). Therefore, clustering nodes with same type will not be sufficient to analyze it. It will ignore relations between nodes from different types. Such data should be dealt with heterogeneous multi-partite clustering methods. Thus, clustering does not ignore...
Citation Formats
N. B. Ömeroğlu, “K-way partitioning of signed bipartite graphs,” M.S. - Master of Science, Middle East Technical University, 2012.