Title: The analysis of split graphs in social networks based on the k-cardinality assignment problem

Authors: Ivan Belik

Addresses: Norwegian School of Economics, Helleveien 30, 5045 Bergen, Norway

Abstract: In terms of social networks, split graphs correspond to the variety of interpersonal and intergroup relations. In this paper, we analyse the interaction between cliques (socially strong and trusty groups) and independent sets (fragmented and non-connected groups) as the basic components of any split graph. Based on the semi-Lagrangean relaxation for the k-cardinality assignment problem, we show the way of minimising socially risky interactions between cliques and independent sets within social networks.

Keywords: social networks; split graphs; cliques; independent sets; assignment problem; semi-Lagrangean relaxation; network science; k-cardinality assignment; socially risky interactions.

DOI: 10.1504/IJNS.2016.073557

International Journal of Network Science, 2016 Vol.1 No.1, pp.53 - 62

Received: 25 Oct 2014
Accepted: 19 Dec 2014
Published online: 12 Dec 2015 *