Cohesive Subgraph Discovery Over Uncertain Bipartite Graphs

In this article, we propose the (alpha,beta,eta)-core model, which is the first cohesive subgraph model on uncertain bipartite graphs. To capture the uncertainty of relationships/edges, eta-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 eta. Given degree constraints alpha and beta, and a probability threshold eta, the (alpha,beta,eta)-core requires that each vertex on the upper or lower level have eta-degree no less than alpha or beta, respectively. An (alpha,beta,eta)-core can be obtained by iteratively removing the vertices with eta-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 (alpha,beta,eta)-core model. Extensive experiments are conducted on 13 datasets to validate the efficiency and effectiveness of our proposed techniques.

Automated summary

In this article, we propose the (alpha,beta,eta)-core model for uncertain bipartite graphs and present algorithms and index construction methods. The efficiency and effectiveness of our proposed techniques are validated through extensive experiments.