Maximum k-balanced induced subgraph.
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 postive edge is within a same set whereas the endpoints of a negative edge belong to different sets.
The problem of finding the maximum k-balanced induced subgraph 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].
[Gulpinar et al., 2024] showed that 2-MBIS is equivalent to the DMERN problem and therefore NP-Hard [Bartholdi, 1982]. For each k > 2, k-MBIS generalizes the problem of determining the maximum k-partite induced subgraph, also being NP-Hard [Stockmeyer, 1973]. [Gulpinar et al., 2024] also proposed a heuristic for 2-MBIS that finds the optimum when the input graph is balanced.
[Barahona and Mahjoub, 1989] studied the polytope defined by the convex hull of the incidence vectors of vertex subsets that induce a 2-balanced subgraph. The relationship between 2-MBIS and DMERN was explored in [Figueiredo et al., 2011] to obtain results on this polytope. The authors present a branch-and-cut algorithm for the problem, refined in [Figueiredo et al., 2013]. Heuristics and a GRASP meta-heuristic were presented in [Figueiredo and Frota, 2014]. For k > 2, the problem was only recently studied with a mathematical programming approach [Figueiredo et al., 2019]. The authors proposed a formulation based on the concept of representatives and presented a partial description of the associated polytope, as well as a branch-and-cut and an ILS meta-heuristic.
As far as we know, there is still no study similar to that of [Barahona, 1989] for k > 2, that is, considering directly the polytope defined by the incidence vectors of vertex subsets that induce a k-balanced subgraph. Studying such a polytope is one of the objectives of this project, which also includes the development of a branch-and-cut algorithm that uses the obtained inequalities as well as the possible adaptation of these inequalities to strengthen the formulation proposed in [Figueiredo et al., 2019]. We also aim to develop approximate algorithms or FPT algorithms for the problem, in general graphs or subclasses.
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.
