Computing Significant Cliques in Large Labeled Networks
- Publisher:
- Institute of Electrical and Electronics Engineers (IEEE)
- Publication Type:
- Journal Article
- Citation:
- IEEE Transactions on Big Data, 2022, pp. 1-13
- Issue Date:
- 2022-01-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| Computing_Significant_Cliques_in_Large_Labeled_Networks.pdf | Accepted version | 2.12 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
Mining cohesive subgraphs and communities is a fundamental problem in network analysis and has drawn much attention in the last decade. Most existing cohesive subgraph models mainly consider the structural cohesion but ignore the subgraph significance. In this paper, we formulate a new model, called statistically significant clique, to mine significant cohesive subgraphs in large vertex-labeled graphs. A statistically significant clique is a complete subgraph with a significance value exceeding a given threshold. The subgraph significance is evaluated by a widely used metric called chi-square statistic. We study the problem of enumerating all maximal statistically significant cliques. The problem is proved to be NP-hard. We propose an efficient branch-and-bound algorithm with several elegant pruning strategies to solve our problem. We conduct extensive experiments on seven large real-world datasets to show the practical efficiency of our algorithms. We also conduct a case study to evaluate the effectiveness of our proposed model.
Please use this identifier to cite or link to this item: