Open Collections

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

University of British Columbia

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.

Text

2017-05-02

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/61438

Computer Science

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/