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.

(2016). Clique editing to support case versus control discrimination . Retrieved from http://hdl.handle.net/10446/78470

Clique editing to support case versus control discrimination

DONDI, Riccardo;
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.
Dondi, Riccardo; Mauri, Giancarlo; Zoppis, Italo
File allegato/i alla scheda:
File Dimensione del file Formato  
idt16-024.pdf

embargo fino al 02/02/2017

Versione: postprint - versione referata/accettata senza referaggio
Licenza: Licenza default Aisberg
Dimensione del file 262.54 kB
Formato Adobe PDF
262.54 kB Adobe PDF Visualizza/Apri
chp_10.1007_978-3-319-39630-9_3.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 284.95 kB
Formato Adobe PDF
284.95 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/78470
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 5
social impact