Motivated by social balance theory, we develop a theory of link classification in signed networks using the correlation clustering index as measure of label regularity. We derive learning bounds in terms of correlation clustering within three fundamental transductive learning settings: online, batch and active. Our main algorithmic contribution is in the active setting, where we introduce a new family of efficient link classifiers based on covering the input graph with small circuits. These are the first active algorithms for link classification with mistake bounds that hold for arbitrary signed networks.

A correlation clustering approach to link classification in signed networks / N. Cesa-Bianchi, C. Gentile, F. Vitale, G. Zappella - In: Proceedings of the 25th annual Conference on Learning Theory : june 25-27, 2012, Edinburgh, Scotland / [a cura di] S. Mannor, N. Srebro, R.C. Williamson. - Brookline, USA : Microtome, 2012. - pp. 34.1-34.20 (( Intervento presentato al 25. convegno Annual Conference on Learning Theory tenutosi a Edinburgh nel 2012.

A correlation clustering approach to link classification in signed networks

N. Cesa-Bianchi
Primo
;
F. Vitale
Penultimo
;
G. Zappella
Ultimo
2012

Abstract

Motivated by social balance theory, we develop a theory of link classification in signed networks using the correlation clustering index as measure of label regularity. We derive learning bounds in terms of correlation clustering within three fundamental transductive learning settings: online, batch and active. Our main algorithmic contribution is in the active setting, where we introduce a new family of efficient link classifiers based on covering the input graph with small circuits. These are the first active algorithms for link classification with mistake bounds that hold for arbitrary signed networks.
Active learning; Online learning; Social balance theory; Transductive learning
Settore INF/01 - Informatica
Pattern Analysis, Statistical Modelling and Computational Learning 2
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
cesa-bianchi12.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 533.76 kB
Formato Adobe PDF
533.76 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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: http://hdl.handle.net/2434/177056
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact