Research Project – CNPq (International Cooperation)
Title: Optimization problems in signed graphs with applications in social networks.
Coordinator: Manoel Campêlo
Abstract
This project focuses on determining subgraphs of a signed graph that respect constraints of balance or compatibility. These two concepts originate in the social balance theory, which studies relationships between individuals in a social network. Those concepts are strongly related to team formation problems. In this sense, constraints on relationships will be combined with requirements on the desired skills for team members to be formed. Thus, we can obtain different variations of the same central problem, opening a broad field for research involving studies of computational complexity, algorithm development, and optimization methods.
Here, we select four main problems:
- Maximum k-balanced induced subgraph (k-MBIS)
- Maximum k-balanced spanning subgraph (k-MBSS)
- Versions of the two previous problems with vertex labeling
- Clustering in signed graphs by compatible paths.
As the main tool for solving these problems, we will use mathematical programming. Starting from integer programming formulations, we will seek to develop efficient solution algorithms, using properties of each problem, polyhedral results, and decomposition strategies. Computational experiments will complement theoretical studies.
Team
 |
Ana Cláudia dos Santos Ferreira Universidade Federal Rural do Rio de Janeiro, Brasil Researcher Lattes |
 |
Diego Delle Donne ESSEC Business School of Paris (IDS department), France Researcher ORCID |
|
Felipe Albuquerque Brito da Silva Avignon Université, França Researcher Lattes |
|
Fernanda Vieira Dias Couto Universidade Federal Rural do Rio de Janeiro, Brasil Researcher Lattes ORCID |
|
Gabriel Hellen de Sousa Universidade Federal do Ceará, Brasil Researcher Lattes |
 |
Javier Leonardo Marenco Universidad Torcuato Di Tellal, Argentina Researcher ORCID |
 |
Jesus Ossian Cunha Universidade Federal do Ceará, Brasil Researcher Lattes ORCID |
|
Jhonata Adam Silva Matias Universidade Federal do Ceará, Brasil Researcher Lattes ORCID |
|
João Victor Fonseca Sombra Universidade Federal do Ceará, Brasil Researcher Lattes ORCID |
|
Jose Robertty de Freitas Costa Universidade Federal do Ceará, Brasil Researcher Lattes |
|
Leonardo Cavalcante de Abreu Universidade Federal do Ceará, Brasil Researcher Lattes ORCID |
 |
Manoel Bezerra Campêlo Neto (Coordenador) Universidade Federal do Ceará, Brasil Researcher Lattes ORCID |
|
Manuela Blaum Ackermann Universidad Nacional de General Sarmiento, Argentina Researcher ORCID |
|
Marcelo Ezequiel Mydlarz Universidad Nacional de General Sarmiento, Argentina Researcher ORCID |
|
Marcio Costa Santos Universidade Federal de Minas Gerais, Brasil Researcher Lattes ORCID |
|
Mónica Andres Braga Universidad Nacional de General Sarmiento, Argentina Researcher ORCID |
|
Pablo Luiz Braga Soares Universidade Federal do Ceará, Brasil Researcher Lattes ORCID |
 |
Paulo Henrique Macêdo de Araújo Universidade Federal do Ceará, Brasil Researcher Lattes ORCID |
|
Phablo Fernando Soares Moura KU Leuven, Bélgica Researcher Lattes ORCID |
|
Philippe Yves Paul Michelon Avignon Université, França Researcher ORCID |
 |
Rafael Castro de Andrade Universidade Federal do Ceará, Brasil Researcher Lattes ORCID |
|
Ricardo Cordeiro Corrêa Universidade Federal Rural do Rio de Janeiro, Brasil Researcher Lattes ORCID |
|
Rommel Dias Saraiva Universidade de Fortaleza, Brasil Researcher Lattes ORCID |
 |
Rosa Maria Videira de Figueiredo Avignon Université, França Researcher Lattes ORCID CV HAL |
 |
Serigne Gueye Avignon Université, França Researcher ORCID CV HAL |
|
Tatiane Fernandes Figueiredo Universidade Federal do Ceará, Brasil Researcher Lattes ORCID |
Institutions Involved
- Universidade Federal do Ceará – UFC, Brasil
- Universidad Torcuato Di Tellal, Argentina
- Universidad Nacional de General Sarmiento – UNGS, Argentina
- KU Leuven – Faculty of Economics and Business (FEB), Brussels Campus – KU Leuven, Bélgica
- Avignon Université, França
- Universidade de Fortaleza – UNIFOR, Brasil
- Universidade Federal de Minas Gerais – UFMG, Brasil
- Universidade Federal Rural do Rio de Janeiro – UFRRJ, Brasil
Research Areas
- Theory of Computation
- Linear, Nonlinear, Mixed, and Dynamic Programming
- Graph Theory
Repository
Publications
