Searching for polarization in signed graphs: A local spectral approach

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

4 Sitaatiot (Scopus)

Abstrakti

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.

AlkuperäiskieliEnglanti
OtsikkoThe Web Conference 2020 - Proceedings of the World Wide Web Conference, WWW 2020
KustantajaACM
Sivut362-372
Sivumäärä11
ISBN (elektroninen)9781450370233
DOI - pysyväislinkit
TilaJulkaistu - 20 huhtikuuta 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational World Wide Web Conference - Taipei, Taiwan
Kesto: 20 huhtikuuta 202024 huhtikuuta 2020
Konferenssinumero: 29

Conference

ConferenceInternational World Wide Web Conference
LyhennettäWWW
Maa/AlueTaiwan
KaupunkiTaipei
Ajanjakso20/04/202024/04/2020

Sormenjälki

Sukella tutkimusaiheisiin 'Searching for polarization in signed graphs: A local spectral approach'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä