A branch-and-cut algorithm for the maximum k-balanced subgraph of a signed graph

Figueiredo, Rosa; Frota, Yuri; Labbé, Martine

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1016/j.dam.2018.11.022

Titre :

A branch-and-cut algorithm for the maximum k-balanced subgraph of a signed graph

Auteur(s) :

Figueiredo, Rosa [Auteur]
Laboratoire Informatique d'Avignon [LIA]
Frota, Yuri [Auteur]
Instituto de Computação [Niteroi-Rio de Janeiro] [IC-UFF]
Labbé, Martine [Auteur]
Integrated Optimization with Complex Structure [INOCS]

Titre de la revue :

Discrete Applied Mathematics

Pagination :

164-185

Éditeur :

Elsevier

Date de publication :

2018

ISSN :

0166-218X

Mot(s)-clé(s) en anglais :

Balanced graph
Integer programming
Social networks
Graph partition
Signed graph

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

We are interested in the solution of the maximum k-balanced subgraph problem. Let G = (V, E, s) be a signed graph and k a positive scalar. A signed graph is k-balanced if V can be partitioned into at most k sets in such a ...
Lire la suite >We are interested in the solution of the maximum k-balanced subgraph problem. Let G = (V, E, s) be a signed graph and k a positive scalar. A signed graph is k-balanced if V can be partitioned into at most k sets in such a way that positive edges are found only within the sets and negative edges go between sets. The maximum k-balanced subgraph problem is the problem of finding a subgraph of G that is k-balanced and maximum according to the number of vertices. This problem has applications in clustering problems appearing in collaborative vs conflicting environments. The particular case k = 2 yields the problem of finding a maximum balanced subgraph in a signed graph and its exact solution has been addressed before in the literature. In this paper, we provide a representatives formulation for the general problem and present a partial description of the associated polytope, including the introduction of strengthening families of valid inequalities. A branch-and-cut algorithm is described for finding an optimal solution to the problem. An ILS metaheuristic is implemented for providing primal bounds for this exact method and a branching rule strategy is proposed for the representatives formulation. Computational experiments, carried out over a set of random instances and on a set of instances from an application, show the effectiveness of the valid inequalities and strategies adopted in this work.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.inria.fr/hal-01937015/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-01937015/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-01937015/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

kBPSG_BW-DAM.pdf
Accès libre
Accéder au document

kBPSG_BW-DAM.pdf
Accès libre
Accéder au document

document
Accès libre
Accéder au document

kBPSG_BW-DAM.pdf
Accès libre
Accéder au document

A branch-and-cut algorithm for the maximum ... BibTeX CSV Excel RIS

Fichiers

A branch-and-cut algorithm for the maximum ...

BibTeX

CSV

Excel

RIS