Discovering cliques in signed networks based on balance theory

Sun, R; Zhu, Q; Chen, C; Wang, X; Zhang, Y; Wang, X

Discovering cliques in signed networks based on balance theory

Sun, R Zhu, Q Chen, C Wang, X Zhang, Y

Wang, X

Permalink

Publisher:: Springer International Publishing
Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2020, 12113 LNCS, pp. 666-674
Issue Date:: 2020-01-01

Closed Access

	Filename	Description	Size
	Sun2020_Chapter_DiscoveringCliquesInSignedNetw.pdf	Published version	384.91 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Sun, R
dc.contributor.author	Zhu, Q
dc.contributor.author	Chen, C
dc.contributor.author	Wang, X
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Wang, X
dc.date.accessioned	2021-04-19T01:02:01Z
dc.date.available	2021-04-19T01:02:01Z
dc.date.issued	2020-01-01
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2020, 12113 LNCS, pp. 666-674
dc.identifier.isbn	9783030594152
dc.identifier.issn	0302-9743
dc.identifier.issn	1611-3349
dc.identifier.uri	http://hdl.handle.net/10453/148195
dc.description.abstract	Enumerating cohesive subgraphs is a fundamental problem for signed network analysis. In this paper, we propose a novel model, called maximal signed k-clique, which aims to find cohesive subgraphs in signed networks based on clique property and balance theory. Given a signed graph G, a set of nodes C is a maximal signed k-clique if (1) $$\|C\|\ge k$$ and C is a clique without any unbalanced triangle; and (2) C is maximal. We show the problem of enumerating all maximal signed k-cliques is NP-hard. Novel pruning techniques are proposed to significantly filter the searching space. An efficient algorithm, SKC, is developed to handle large networks. Comprehensive experiments on four real-world datasets are conducted to demonstrate the efficiency and effectiveness of the proposed algorithms.
dc.language	en
dc.publisher	Springer International Publishing
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.relation.isbasedon	10.1007/978-3-030-59416-9_43
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject.classification	Artificial Intelligence & Image Processing
dc.title	Discovering cliques in signed networks based on balance theory
dc.type	Conference Proceeding
utslib.citation.volume	12113 LNCS
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
dc.date.updated	2021-04-19T01:01:59Z
pubs.publication-status	Published
pubs.volume	12113 LNCS

Abstract:

Enumerating cohesive subgraphs is a fundamental problem for signed network analysis. In this paper, we propose a novel model, called maximal signed k-clique, which aims to find cohesive subgraphs in signed networks based on clique property and balance theory. Given a signed graph G, a set of nodes C is a maximal signed k-clique if (1) $$|C|\ge k$$ and C is a clique without any unbalanced triangle; and (2) C is maximal. We show the problem of enumerating all maximal signed k-cliques is NP-hard. Novel pruning techniques are proposed to significantly filter the searching space. An efficient algorithm, SKC, is developed to handle large networks. Comprehensive experiments on four real-world datasets are conducted to demonstrate the efficiency and effectiveness of the proposed algorithms.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/148195