SPONGE: A generalized eigenproblem for clustering signed networks

Cucuringu, Mihai; Davies, Peter; Glielmo, Aldo; Tyagi, Hemant

Document type :

Communication dans un congrès avec actes

Permalink :

http://hdl.handle.net/20.500.12210/29274

Title :

SPONGE: A generalized eigenproblem for clustering signed networks

Author(s) :

Cucuringu, Mihai [Auteur]
Davies, Peter [Auteur]
Glielmo, Aldo [Auteur]
Tyagi, Hemant [Auteur]

Conference title :

AISTATS

City :

Okinawa

Country :

Japon

Start date of the conference :

2019-04-16

Publication date :

2019-04-16

HAL domain(s) :

Statistiques [stat]/Autres [stat.ML]

English abstract : [en]

We introduce a principled and theoretically sound spectral method for k-way clustering in signed graphs, where the affinity measure between nodes takes either positive or negative values. Our approach is motivated by social ...
Show more >We introduce a principled and theoretically sound spectral method for k-way clustering in signed graphs, where the affinity measure between nodes takes either positive or negative values. Our approach is motivated by social balance theory, where the task of clustering aims to decompose the network into dis-joint groups, such that individuals within the same group are connected by as many positive edges as possible, while individuals from different groups are connected by as many negative edges as possible. Our algorithm relies on a generalized eigenproblem formulation inspired by recent work on constrained clustering. We provide theoretical guarantees for our approach in the setting of a signed stochastic block model, by leveraging tools from matrix perturbation theory and random matrix theory. An extensive set of numerical experiments on both synthetic and real data shows that our approach compares favorably with state-of-the-art methods for signed clustering , especially for large number of clusters and sparse measurement graphs.Show less >

Language :

Anglais

Audience :

Internationale

Popular science :

Non

Collections :

METRICS : Evaluation des technologies de santé et des pratiques médicales - ULR 2694

Submission date :

2020-06-08T14:10:45Z
2020-06-09T09:20:09Z

Files

documen
Open access
Access the document

Version	Link	Modification date
2	20.500.12210/29274*	2020-06-09T09:19:56Z
1	20.500.12210/29274.1	2020-06-08T14:10:45Z

SPONGE: A generalized eigenproblem for ...

BibTeX

CSV

Excel

RIS

Files

Version history

SPONGE: A generalized eigenproblem for ... BibTeX CSV Excel RIS

Files

Version history

SPONGE: A generalized eigenproblem for ...

BibTeX

CSV

Excel

RIS