Clique Identification in Signed Graphs: A Balance Theory based Model
Publication Name
IEEE Transactions on Knowledge and Data Engineering
Abstract
Clique, as a fundamental model for graph analysis, is widely investigated in the literature. However, with the emergence of various graph data, such as signed graph, novel clique model is desired to better capture the cohesiveness within these graphs. Different from unsigned graphs, where only one type of edge exists, in signed graphs, nodes can be connected either positively or negatively (e.g., friend or enemy). In this paper, we propose a novel clique model, called signed $k$-clique, which aims to find cohesive subgraphs in signed networks based on the classic clique model and balance theory. Given a signed graph $G$, an induced subgraph $S$ is a signed $k$-clique if $|S| \ge k$ and $S$ is a clique without any unbalanced triangle. Moreover, we propose and investigate two fundamental problems, i.e., maximal signed $k$-clique enumeration and maximum signed $k$-clique identification, both of which are shown to be NP-hard. For maximal signed $k$-clique enumeration, novel balance graph based search framework and optimization techniques are proposed to eliminate the limitations in the developed baseline. For maximum signed $k$-clique identification, different upper bound based techniques are developed to early terminate the search. Furthermore, the support of finding top-$\gamma$ results is also discussed. Finally, comprehensive experiments on seven real-world datasets are conducted to demonstrate the efficiency and effectiveness of the proposed techniques. Compared with the baseline, the optimized algorithm can achieve up to four orders of magnitude speedup.
Open Access Status
This publication is not available as open access