Edge connectivity is a crucial concept in graph theory, which often serves as a fundamental metric for analyzing and improving the robustness, efficiency, and reliability of various types of networks. A graph is k-connected if it is still connected after removing arbitrarily fewer than$k$edges. Sparse certificate is the lossless compression of a graph in terms of k-connectivity with a bounded size, which enables processing connectivity-driven queries in a more efficient way. Existing studies mainly focus on computing a sparse certificate in static graphs. Motivated by the prevalence of highly dynamic graphs, we aim to propose algorithms to maintain a sparse certificate when an edge is in-serted or deleted. We propose efficient algorithms to significantly improve the theoretical running time for both edge insertion and edge deletion compared with the baseline. We also propose a novel strategy for the search process in edge deletion. The strategy improves the efficiency compared with other potential methods with a theoretical guarantee. Extensive performance studies have been conducted on fourteen real-world datasets. The results demonstrate the significant advantages of our algorithms.

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.

Bipartite graphs are extensively used to model relationships between two different types of entities. In many real-world bipartite graphs, relationships are naturally uncertain due to various reasons such as data noise, measurement error and imprecision of data, leading to uncertain bipartite graphs. In this paper, 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 derived by iteratively removing a vertex with$\eta$-degree below the degree constraint and updating the$\eta$-degrees of its neighbors. This incurs prohibitively high cost due to the$\eta$-degree computation and updating, and is not scalable to large bipartite graphs. This motivates us to develop index-based approaches. We propose a basic full index that stores ($\alpha, \beta, \eta$)-core for all possible$\alpha, \beta$, and$\eta$combinations, thus supporting optimal retrieval of the vertices in any ($\alpha, \beta, \eta$)-core. Due to its long construction time and high space complexity, we further propose a probability-aware index to achieve a balance between time and space costs. To efficiently build the probability-aware index, we design a bottom-up index construction algorithm and a top-down index construction algorithm. Extensive experiments are conducted on real-world datasets with generated edge probabilities under different distributions, which show that (1) ($\alpha,\beta,\eta$)-core is an effective model; (2) index construction and query processing are significantly sped up by the proposed techniques.