Discovering cliques in signed networks based on balance theory
- 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 |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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: