kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Testing Cluster Properties of Signed Graphs
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS. HIIT, University of Helsinki Helsinki, Finland.
Université de Paris, CNRS, IRIF Paris, France.
Number of Authors: 22023 (English)In: ACM Web Conference 2023: Proceedings of the World Wide Web Conference, WWW 2023, Association for Computing Machinery (ACM) , 2023, p. 49-59Conference paper, Published paper (Refereed)
Abstract [en]

This work initiates the study of property testing in signed graphs, where every edge has either a positive or a negative sign. We show that there exist sublinear query and time algorithms for testing three key properties of signed graphs: balance (or 2-clusterability), clusterability and signed triangle freeness. We consider both the dense graph model, where one queries the adjacency matrix entries of a signed graph, and the bounded-degree model, where one queries for the neighbors of a node and the sign of the connecting edge. Our algorithms use a variety of tools from unsigned graph property testing, as well as reductions from one setting to the other. Our main technical contribution is a sublinear algorithm for testing clusterability in the bounded-degree model. This contrasts with the property of k-clusterability in unsigned graphs, which is not testable with a sublinear number of queries in the bounded-degree model. We experimentally evaluate the complexity and usefulness of several of our testers on real-life and synthetic datasets.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM) , 2023. p. 49-59
Keywords [en]
clustering, property testing, random walks, signed graphs, social networks
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-333333DOI: 10.1145/3543507.3583213Scopus ID: 2-s2.0-85159313460OAI: oai:DiVA.org:kth-333333DiVA, id: diva2:1785000
Conference
2023 World Wide Web Conference, WWW 2023, Austin, United States of America, Apr 30 2023 - May 4 2023
Note

Part of ISBN 9781450394161

QC 20230801

Available from: 2023-08-01 Created: 2023-08-01 Last updated: 2023-08-01Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Adriaens, Florian

Search in DiVA

By author/editor
Adriaens, Florian
By organisation
Theoretical Computer Science, TCS
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 37 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf