Signed Clique Search in Signed Networks: Concepts and Algorithms
- Publisher:
- IEEE COMPUTER SOC
- Publication Type:
- Journal Article
- Citation:
- IEEE Transactions on Knowledge and Data Engineering, 2021, 33, (2), pp. 710-727
- Issue Date:
- 2021-02-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| 08665929.pdf | 2.01 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 1989-2012 IEEE. Mining cohesive subgraphs from a network is a fundamental problem in network analysis. Most existing cohesive subgraph models are mainly tailored to unsigned networks. In this paper, we study the problem of seeking cohesive subgraphs in a signed network, in which each edge can be positive or negative, denoting friendship or conflict, respectively. We propose a novel model, called maximal (α, k)(α,k)-clique, that represents a cohesive subgraph in signed networks. Specifically, a maximal (α, k)(α,k)-clique is a clique in which every node has at most kk negative neighbors and at least ⌈ α k ⌈αk⌉ positive neighbors (α ≥q 1α≥1). We show that the problem of enumerating all maximal (α, k)(α,k)-cliques in a signed network is NP-hard. To enumerate all maximal (α, k)(α,k)-cliques efficiently, we first develop an elegant signed network reduction technique to significantly prune the signed network. Then, we present an efficient branch and bound enumeration algorithm with several carefully-designed pruning rules to enumerate all maximal (α, k) (α,k)-cliques in the reduced signed network. In addition, we also propose an efficient algorithm with three novel upper-bounding techniques to find the maximum (α, k) (α,k)-clique in a signed network. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.
Please use this identifier to cite or link to this item: