K-way partitioning of signed bipartite graphs

Download

index.pdf

Date

2012

Author

Ömeroğlu, Nurettin Burak

Metadata

Show full item record

Item Usage Stats

190
views

84
downloads

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.

Subject Keywords

Cluster analysis, Bipartite graphs., Graph theory., Graph algorithms., Computer algorithms.

URI

http://etd.lib.metu.edu.tr/upload/12614817/index.pdf
https://hdl.handle.net/11511/21976

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

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...
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...
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...
BB-graph: a new subgraph isomorphism algorithm for querying big graph databases Asiler, Merve; Yazıcı, Adnan; Department of Computer Engineering (2016) With the emergence of the big data concept, the big graph database model has become very popular since it provides very flexible and quick querying for the cases that require costly join operations in RDBMs. However, it is a big challenge to find all exact matches of a query graph in a big database graph, which is known as the subgraph isomorphism problem. Although many related studies exist in literature, there is not a perfect algorithm that works for all types of queries efficiently since it is an NP-har...

Citation Formats

N. B. Ömeroğlu, “K-way partitioning of signed bipartite graphs,” M.S. - Master of Science, Middle East Technical University, 2012.