Searching for polarization in signed graphs: A local spectral approach

Han Xiao, Bruno Ordozgoiti, Aristides Gionis

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

22 Citations (Scopus)

Abstract

Signed graphs have been used to model interactions in social networks, which can be either positive (friendly) or negative (antagonistic). The model has been used to study polarization and other related phenomena in social networks, which can be harmful to the process of democratic deliberation in our society. An interesting and challenging task in this application domain is to detect polarized communities in signed graphs. A number of different methods have been proposed for this task. However, existing approaches aim at finding globally optimal solutions. Instead, in this paper we are interested in finding polarized communities that are related to a small set of seed nodes provided as input. Seed nodes may consist of two sets, which constitute the two sides of a polarized structure. In this paper we formulate the problem of finding local polarized communities in signed graphs as a locally-biased eigen-problem. By viewing the eigenvector associated with the smallest eigenvalue of the Laplacian matrix as the solution of a constrained optimization problem, we are able to incorporate the local information as an additional constraint. In addition, we show that the locally-biased vector can be used to find communities with approximation guarantee with respect to a local analogue of the Cheeger constant on signed graphs. By exploiting the sparsity in the input graph, an indicator-vector for the polarized communities can be found in time linear to the graph size. Our experiments on real-world networks validate the proposed algorithm and demonstrate its usefulness in finding local structures in this semi-supervised manner.

Original languageEnglish
Title of host publicationThe Web Conference 2020 - Proceedings of the World Wide Web Conference, WWW 2020
PublisherACM
Pages362-372
Number of pages11
ISBN (Electronic)9781450370233
DOIs
Publication statusPublished - 20 Apr 2020
MoE publication typeA4 Conference publication
EventInternational World Wide Web Conference - Taipei, Taiwan, Republic of China
Duration: 20 Apr 202024 Apr 2020
Conference number: 29

Conference

ConferenceInternational World Wide Web Conference
Abbreviated titleWWW
Country/TerritoryTaiwan, Republic of China
CityTaipei
Period20/04/202024/04/2020

Fingerprint

Dive into the research topics of 'Searching for polarization in signed graphs: A local spectral approach'. Together they form a unique fingerprint.

Cite this