We present a graph-based approach to support case vs control discrimination problems. The goal is to partition a given input graph in two sets, a clique and an independent set, such that there is no edge connecting a vertex of the clique with a vertex of the independent set. Following a parsimonious principle, we consider the problem that aims to modify the input graph into a most similar output graph that consists of a clique and an independent set (with no edge between the two sets). First, we present a theoretical result showing that the problem admits a polynomial-time approximation scheme. Then, motivated by the complexity of such an algorithm, we propose a genetic algorithm and we present an experimental analysis on simulated data.

Dondi, R., Mauri, G., Zoppis, I. (2016). Clique editing to support case versus control discrimination. In L.C. Jain, R.J. Howlett, I. Czarnowski, A.M. Caballero, L.C. Jain, L.C. Jain (a cura di), Intelligent Decision Technologies, Part I (pp. 27-36). Heidelberg : Springer Science and Business Media Deutschland GmbH [10.1007/978-3-319-39630-9_3].

Clique editing to support case versus control discrimination

Mauri, G;Zoppis, I
2016

Abstract

We present a graph-based approach to support case vs control discrimination problems. The goal is to partition a given input graph in two sets, a clique and an independent set, such that there is no edge connecting a vertex of the clique with a vertex of the independent set. Following a parsimonious principle, we consider the problem that aims to modify the input graph into a most similar output graph that consists of a clique and an independent set (with no edge between the two sets). First, we present a theoretical result showing that the problem admits a polynomial-time approximation scheme. Then, motivated by the complexity of such an algorithm, we propose a genetic algorithm and we present an experimental analysis on simulated data.
Capitolo o saggio
genetic algorithms; graph partitioning
English
Intelligent Decision Technologies, Part I
Jain, LC; Howlett, RJ; Czarnowski, I; Caballero, AM; Jain, LC; Jain, LC
2016
9783319396293
56
Springer Science and Business Media Deutschland GmbH
27
36
Dondi, R., Mauri, G., Zoppis, I. (2016). Clique editing to support case versus control discrimination. In L.C. Jain, R.J. Howlett, I. Czarnowski, A.M. Caballero, L.C. Jain, L.C. Jain (a cura di), Intelligent Decision Technologies, Part I (pp. 27-36). Heidelberg : Springer Science and Business Media Deutschland GmbH [10.1007/978-3-319-39630-9_3].
none
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/133819
Citazioni
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 7
Social impact