25th International Conference on Database Systems for Advanced Applications

Sep. 24-27, 2020, Jeju, South Korea

Click following URL

http://dasfaa2020.sigongji.com

to visit DASFAA 2020 Online Event Site

Paper details

Title: Discovering Cliques in Signed Networks Based on Balance Theory

Authors: Renjie Sun, Qiuyu Zhu, Chen Chen, Xiaoyang Wang, Ying Zhang and Xun Wang

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| กร 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.

Video file:

Slide file:

Sponsors