Back to search

University of British Columbia

Random models and heuristic algorithms for correlation clustering problems on signed social networks

Abstract

dc:description

In social sciences, the signed directed networks are used to represent the mutual friendship and foe attitudes among the members of a social group. Recent studies show that different real-world properties (e.g. preferential attachment, copying etc.) can be observed in the web-based social networks. In this thesis, we study the positive/negative - in/out - degree distributions in three online signed directed social networks. We observe that all signed-directed degree distributions in the web-based social networks with multiple edges possibilities (in both directions) follow a power law with exponents in the range 2.0<= \gamma <= 3.5. We present three random models, which capture the preferential attachment and copying properties, for web-based signed directed social networks. The signed-directed degree distributions in the networks simulated by the proposed random models also indicate a power-law trait with an exponent in the range 2.0<= \gamma <= 3.5. We also present a heuristic algorithm for the Correlation Clustering (CC) which is a class of community detection problem in the signed network. The CC problem can be defined as follow: for a given signed network, finding an optimal partition in the vertices such that the edges inside a group are positives and the edges between two groups are negative. We present the algorithm based on the relaxing integer linear programming formulation of the minimum disagreement CC problem and rounding the approximate ultrametric distance matrix by using a given threshold. The experimental results show that, in the random signed G(n,e,p) network, the runtime of this algorithm is nearly independent for the cases e>= 0.4 and p<=0.6 , where e and p are the probabilities of connecting two vertices by an edge and an edge to be positive respectively. But this algorithm does not give any convincing argument in the variation of the minimum disagreements due to the changing of the given threshold. We also apply this algorithm to the International National Bilateral Tread Growth Network derived from the bilateral trading data in 2011-2015 from the International Trade Center (ITC) to identify the groups of countries with average positive trade growth.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wahid, Dewan Ferdous

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/61438

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Wahid, Dewan Ferdous. Random models and heuristic algorithms for correlation clustering problems on signed social networks. master's thesis, University of British Columbia, 2017. http://hdl.handle.net/2429/61438