aalto1 untyped-item.component.html
Finding large balanced subgraphs in signed networks
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
11
Series
The Web Conference 2020 - Proceedings of the World Wide Web Conference, WWW 2020, pp. 1378-1388
Abstract
Signed networks are graphs whose edges are labelled with either a positive or a negative sign, and can be used to capture nuances in interactions that are missed by their unsigned counterparts. The concept of balance in signed graph theory determines whether a network can be partitioned into two perfectly opposing subsets, and is therefore useful for modelling phenomena such as the existence of polarized communities in social networks. While determining whether a graph is balanced is easy, finding a large balanced subgraph is hard. The few heuristics available in the literature for this purpose are either ineffective or non-scalable. In this paper we propose an efficient algorithm for finding large balanced subgraphs in signed networks. The algorithm relies on signed spectral theory and a novel bound for perturbations of the graph Laplacian. In a wide variety of experiments on real-world data we show that our algorithm can find balanced subgraphs much larger than those detected by existing methods, and in addition, it is faster. We test its scalability on graphs of up to 34 million edges.
Description
| openaire: EC/H2020/654024/EU//SoBigData
Other note
Citation
Ordozgoiti, B, Matakos, A & Gionis, A 2020, Finding large balanced subgraphs in signed networks. in The Web Conference 2020 - Proceedings of the World Wide Web Conference, WWW 2020. ACM, pp. 1378-1388, International World Wide Web Conference, Taipei, Taiwan, Republic of China, 20/04/2020. https://doi.org/10.1145/3366423.3380212