Signed Network Structural Analysis and Applications with a Focus on Balance Theory

Show simple item record

dc.contributor.advisor Wilson, MC en Arefkashfi, S en 2019-02-24T22:21:01Z en 2019 en
dc.identifier.uri en
dc.description.abstract This research is an effort to understand small-scale properties of networks resulting in global structure in larger scales. Networks are modelled by graphs and graph-theoretic conditions are used to determine the structural properties exhibited by the network. Our focus is on signed networks which have positive and negative signs as a property on the edges. We analyse networks from the perspective of balance theory which predicts structural balance as a global structure for signed social networks that represent groups of friends and enemies. The vertex set of balanced signed networks can be partitioned into two subsets such that each negative edge joins vertices belonging to different subsets. The scarcity of balanced networks encouraged us to define the notion of partial balance in order to quantify the extent to which a network is balanced. We evaluate several numerical measures of partial balance and recommend using the frustration index, a measure that satisfieds key axiomatic properties and allows us to analyse graphs based on their levels of partial balance. The exact algorithms used in the literature to compute the frustration index, also called the line index of balance, are not scalable and cannot process graphs with a few hundred edges. We formulate computing the frustration index as a graph optimisation problem to find the minimum number of edges whose removal results in a balanced network given binary decision variables associated with graph nodes and edges. We use our first optimisation model to analyse graphs with up to 3000 edges. Reformulating the optimisation problem, we develop three more efficient binary linear programming models. Equipping the models with valid inequalities and prioritised branching as speed-up techniques allows us to process graphs with 15000 edges on inexpensive hardware. Besides making exact computations possible for large graphs, we show that our models outperform heuristics and approximation algorithms suggested in the literature by orders of magnitude. We extend the concepts of balance and frustration in signed networks to applications beyond the classic friend-enemy interpretation of balance theory in social context. Using a high-performance computer, we analyse graphs with up to 100000 edges to investigate a range of applications from biology and chemistry to finance, international relations, and physics. en
dc.publisher ResearchSpace@Auckland en
dc.relation.ispartof PhD Thesis - University of Auckland en
dc.relation.isreferencedby UoA99265119509102091 en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri en
dc.rights.uri en
dc.title Signed Network Structural Analysis and Applications with a Focus on Balance Theory en
dc.type Thesis en Computer Science en The University of Auckland en Doctoral en PhD en
dc.rights.holder Copyright: The author en
dc.rights.accessrights en
pubs.elements-id 763532 en
pubs.record-created-at-source-date 2019-02-25 en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace