Universidade Federal do Ceará
ParGO – Paralelismo, Grafos e Otimização

Online social networks have been extensively used by a large portion of the global population and have emerged as a fertile environment for disseminating information, sharing various contents, and providing leisure and entertainment activities, thus facilitating the creation of connections among people around the globe. The social relationships established through networks constitute an endless source for studying behavior and interactions among individuals and groups. Even networks restricted to corporate environments serve this purpose.

In this context, a convenient representation of social networks is through signed graphs, where each edge is associated with a signal + or -. The vertices represent the set of individuals; the edges, the links between them; and the signal function describes antithetical relationships, such as liking/not liking, trusting/not trusting, for/against [Arinik, 2017], or any binary weighted connections defined by edges, such as that suggested by sociometry to quantify interpersonal relationships [Moreno, 1941].

Signed graphs were introduced by Heider [Heider, 1947] with the aim of modeling social relationships between groups and formalizing concepts of social balance in social sciences. In recent decades, these graphs have become attractive to social network researchers for modeling relationships among participants in these networks [Inohara,1998; Yang, 2007].

An important concept in signed graphs is balance. This concept was introduced by Cartwright et al. [Cartwright, 1956]. In a balanced signed graph, we can partition the vertices into two sets such that the endpoints of every positive edge is in a same set (each set is supportative) and the endpoints of every negative edge belong to different sets (the two sets are hostile to each other).

The problem of maximum k-balanced spanning subgraph (k-MBSS) consists in, given G and k, determining a spanning subgraph of the signed graph G that is k-balanced and that has the largest number of edges. This problem is associated with the edge-index for balance defined by [Harary, 1959].

[Doreian, 1996] considered the following equivalent problem: given G and k, partition the set of vertices into at most k disjoint subsets, in order to minimize the number of intra-cluster negative edges and inter-cluster positive edges. Motivated by an application in machine learning and without establishing a connection with structural balance theory, [Bansal, 2004] formalized a variant of the problem in which k is not an input, known in the literature as Correlation Clustering (CC).

Just like for k-MBIS, one of the goals of the project is to conduct a study of the polytope associated with k-MBSS or some formulation of the problem. So far, we are unaware of results in this line. Additionally, designing and evaluating exact algorithms that make use of the theoretical results obtained is another objective.