Clique Identification in Signed Graphs: A Balance Theory Based Model
- Publisher:
- Institute of Electrical and Electronics Engineers (IEEE)
- Publication Type:
- Journal Article
- Citation:
- IEEE Transactions on Knowledge and Data Engineering, 2023, 35, (12), pp. 12513-12527
- Issue Date:
- 2023-12-01
Closed Access
Filename | Description | Size | |||
---|---|---|---|---|---|
Clique_Identification_in_Signed_Graphs_A_Balance_Theory_Based_Model.pdf | Published version | 2.27 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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 κ-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 κ-clique if |S| ≥ k|S|≥k and S is a clique without any unbalanced triangle. Moreover, we propose and investigate two fundamental problems, i.e., maximal signed κ-clique enumeration and maximum signed κ-clique identification, both of which are shown to be NP-hard. For maximal signed κ-clique enumeration, novel balance graph based search framework and optimization techniques are proposed to eliminate the limitations in the developed baseline. For maximum signed κ-clique identification, different upper bound based techniques are developed to early terminate the search. Furthermore, the support of finding top-γ 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.
Please use this identifier to cite or link to this item: