Discovering conflicting groups in signed networks

Loading...
Thumbnail Image

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A4 Artikkeli konferenssijulkaisussa

Date

2020

Major/Subject

Mcode

Degree programme

Language

en

Pages

Series

Advances in Neural Information Processing Systems 33 pre-proceedings (NeurIPS 2020), Advances in neural information processing systems

Abstract

Signed networks are graphs where edges are annotated with a positive or negative sign, indicating whether an edge interaction is friendly or antagonistic. Signed networks can be used to study a variety of social phenomena, such as mining polarized discussions in social media, or modeling relations of trust and distrust in online review platforms. In this paper we study the problem of detecting k conflicting groups in a signed network. Our premise is that each group is positively connected internally and negatively connected with the other k−1 groups. An important aspect of our formulation is that we are not searching for a complete partition of the signed network, instead, we allow other nodes to be neutral with respect to the conflict structure we are searching. As a result, the problem we tackle differs from previously studied problems, such as correlation clustering and k-way partitioning. To solve the conflicting-group discovery problem, we derive a novel formulation in which each conflicting group is naturally characterized by the solution to the maximum discrete Rayleigh's quotient (\maxdrq) problem. We present two spectral methods for finding approximate solutions to the \maxdrq problem, which we analyze theoretically. Our experimental evaluation shows that, compared to state-of-the-art baselines, our methods find solutions of higher quality, are faster, and recover ground truth conflicting groups with higher accuracy.

Description

| openaire: EC/H2020/654024/EU//SoBigData | openaire: EC/H2020/834862/EU//REBOUND

Keywords

Other note

Citation

Tzeng, R-C, Ordozgoiti Rubio, B & Gionis, A 2020, Discovering conflicting groups in signed networks . in Advances in Neural Information Processing Systems 33 pre-proceedings (NeurIPS 2020) . Advances in neural information processing systems, Morgan Kaufmann Publishers, Conference on Neural Information Processing Systems, Vancouver, Canada, 06/12/2020 . < https://proceedings.neurips.cc/paper/2020/hash/7cc538b1337957dae283c30ad46def38-Abstract.html >