Clustering in signed graphs by compatible paths

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].

Using the notion of structural balance, [Kouvatis et al, 2020] defined some compatibility relationships in a signal graph to reflect conditions that must be obeyed by each pair of members of the same team. The compatibility notion is based on the concept of a positive path in signed graphs, that is, a path with an even number of negative edges. Among the relationships defined by the authors, we highlight the following alternatives for defining compatibility between two vertices i and j:

[A-SP] all shortest paths between i and j are positive;
[M-SP] at least half of the shortest paths between i and j are positive;
[O-SP] there exists a shortest path between i and j that is positive;
[B-SP] there exists a path (not necessarily shortest) between i and j that is positive, and the subgraph induced by its vertices is balanced.

We say that a subgraph H of G is X-SP-compatible if each pair of vertices in this subgraph satisfies the X-SP condition above, considering the paths in G; and it is strict X-SP-compatible if the X-SP condition considers only paths in H. Similarly, we define X-P-compatible and strict X-P-compatible when considering any paths, not necessarily shortest.

[Kouvatis et al., 2020] considered the problem of determining an X-SP-compatible subgraph H in G. Defined in fact in terms of application, the problem consists of determining a set of individuals, pairwise compatible, that cover a set of desired competencies. The authors show that this problem is NP-Hard.

In this project, we will consider the following general problem: Determine k disjoint subgraphs H1,…,Hk of G such that

for every i, Hi is X-SP-compatible;
for every i and every c, |{v in V(Hi) such that c belongs to c(v)}| <= d(i,c).

Additionally, we can generate variations by replacing SP-compatible with P-compatible in (1) or by adding the condition of strict compatibility. Optimization versions will also be defined, introducing some objective function to rank feasible solutions.

For these problems, there are still no works in the literature, besides [Kouvatis et al., 2020]. Thus, we initially intend to develop complexity studies, particularly for restricted cases, propose and implement mathematical programming formulations are other objectives, as well as develop exact solution methods based on these formulations.

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

Clustering in signed graphs by compatible paths

References

Compartilhe: