Cohesive Subgraph Discovery Over Uncertain Bipartite Graphs
- Publisher:
- IEEE COMPUTER SOC
- Publication Type:
- Journal Article
- Citation:
- IEEE Transactions on Knowledge and Data Engineering, 2023, 35, (11), pp. 11165-11179
- Issue Date:
- 2023-11-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| Cohesive_Subgraph_Discovery_Over_Uncertain_Bipartite_Graphs.pdf | Published version | 2.29 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
In this article, we propose the (α,β,η)-core model, which is the first cohesive subgraph model on uncertain bipartite graphs. To capture the uncertainty of relationships/edges, η-degree is adopted to measure the vertex engagement level, which is the largest integer k such that the probability of a vertex having at least k neighbors is not less than η. Given degree constraints α and β, and a probability threshold η, the (α,β,η)-core requires that each vertex on the upper or lower level have η-degree no less than α or β, respectively. An (α,β,η)-core can be obtained by iteratively removing the vertices with η-degrees below the degree constraints. Apart from the online computation algorithm, we propose a probability-aware index to strike a balance between time and space costs. To efficiently build such an index, we design a top-down index construction algorithm to allow computation sharing. Then, we show how to parallelize our query algorithms and index construction algorithms. In addition, we study community search on uncertain bipartite graphs by adopting the (α,β,η)-core model. Extensive experiments are conducted on 13 datasets to validate the efficiency and effectiveness of our proposed techniques.
Please use this identifier to cite or link to this item: