Maximum k-balanced induced/spanning subgraph with vertex labeling
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 maximum k-balanced induced subgraph problem (k-MBIS) consists in, given G and k, determining an induced subgraph of the signed graph G that is k-balanced and has the largest number of vertices. This problem is related to the vertex-index for balance, defined in [Harary, 1959]. The maximum k-balanced spanning subgraph problem (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].
Consider problems k-MBIS and k-MBSS defined above. In addition to G=(V,E,sigma) and k > 0, let us be given a set of labels (colors) C and two functions c and d, such that c(u) is the subset of colors of vertex u and d(i,c) is the minimum demand of vertices with color c in subset Vi. The set of colors represents the skills/competencies considered for team composition in our application.
With this, we can define a capacitated version of k-MBIS or k-MBSS, adding the following constraints on the partition V1, V2, …, Vk of the vertex set of the chosen subgraph:
- for each v in the union of Vi with i=1 to k, choose a unique color c* from c(v);
- for every i in {1,…,k} and every color c, it must hold that | {v in Vi | c*=c(v) }| is greater than or equal to d(i,c).
In terms of applications, condition (1) requests that every individual participating in a team is performing only one of his/her competencies. Condition (2) ensures that the demand for competencies is satisfied in each team.
The above problem models the application called Competitive Team Formation [Figueiredo et al., 2021]. In this thesis, guided by the proponent of this project, the problem was introduced an integer programming formulation was presented, as well as families of valid inequalities and heuristic procedures for generating some of these inequalities.
We intend to continue this work on different fronts. First, to conduct a study on these inequalities, to understand how they can be strengthened and under what conditions they induce facets. Second, to solve larger instances, improve the procedures for generating inequalities, develop separation procedures, and use the inequalities in a branch-and-cut algorithm.
We also aim to consider a variant of the problem where constraint (1) is ignored and, in condition (2), a member of a team could simultaneously perform all of his skills required by the team.
References
- N. Arinik, R. Figueiredo, and V. Labatut. Signed graph analysis for the interpretation of voting behavior. International Workshop on Recommender Systems and Social Network Analysis, 2017.
- J. J. Bartholdi. A good submatrix is hard to find. Operations Research Letters, 1(5):190–193, 1982.
- F. Barahona and A. R. Mahjoub. Facets of the balanced (acyclic) induced subgraph polytope. Mathematical Programming, 45(1):21–33, 1989.
- D. Cartwright and F. Harary. Structural balance: A generalization of heiders theory. Psychological Review, 63:277–293, 1956.
- R. M. V. Figueiredo, M. Labbé, and C. C. d. Souza. An exact approach to the problem of extracting an embedded network matrix. Computers & Operations Research, 38(11):1483–1492, 2011.
- R. Figueiredo and G. Moura. Mixed integer programming formulations for clustering problems related to structural balance. Social Networks, 35(4):639 – 651, 2013
- R. Figueiredo and Y. Frota. The maximum balanced subgraph of a signed graph: Applications and solution approaches. European Journal of Operational Research, 236(2):473–487, 2014.
- R. Figueiredo, Y. Frota, and M. Labbé. A branch-and-cut algorithm for the maximum k-balanced subgraph of a signed graph. Discrete Applied Mathematics, 261:164–185, 2019
- N. Gulpinar, G. Gutin, G. Mitra, and A. Zverovitch. Extracting pure network submatrices in linear programs using signed graphs. Discrete Applied Mathematics, 137(3):359–372, 2004.
- F. Harary. On the measurement of structural balance. Behavioral Science, 4(4):316–323, 1959.
- F. Heider. Attitudes and cognitive organization. Journal of Psychology, 21:107–112, 1946.
- T. Inohara. On conditions for a meeting not to reach a deadlock. Applied Mathematics and Computation, 90:1–9, 1998.
- J. L. Moreno. Foundations of sociometry: An introduction. Sociometry, 4(1):15–35, 1941.
- S. Poljak and D. Turzík. On a facet of the balanced subgraph polytope (english). Casopis proPestov ́án ́í Matematiky, 112(4):373–380, 1987.
- L. Stockmeyer. Planar 3-colorability is polynomial complete. SIGACT News, 5(3):19–25, 1973.
