Clique Identification in Signed Graphs: A Balance Theory Based Model
Renjie Sun, Yanping Wu, Xiaoyang Wang, Chen Chen, Wenjie Zhang, Xuemin Lin
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 article, we propose a novel clique model, called signed <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -clique, which aims to find cohesive subgraphs in signed networks based on the classic clique model and balance theory. Given a signed graph <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> , an induced subgraph <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> is a signed <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -clique if <inline-formula><tex-math notation="LaTeX">$|S| \geq k$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> is a clique without any unbalanced triangle. Moreover, we propose and investigate two fundamental problems, i.e., maximal signed <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -clique enumeration and maximum signed <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -clique identification, both of which are shown to be NP-hard. For maximal signed <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -clique enumeration, novel balance graph based search framework and optimization techniques are proposed to eliminate the limitations in the developed baseline. For maximum signed <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -clique identification, different upper bound based techniques are developed to early terminate the search. Furthermore, the support of finding top- <inline-formula><tex-math notation="LaTeX">$\gamma$</tex-math></inline-formula> 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.