Efficient Reinforcement of Bipartite Networks at Billion Scale

Bipartite networks, which model relationships between two different types of entities, are prevalent in many real-world applications. On bipartite networks, the cascading node departure undermines the networks' ability to provide sustainable services, which makes reinforcing bipartite networks a vital problem. Although network reinforcement is extensively studied on unipartite networks, it remains largely unexplored on bipartite graphs. On bipartite networks, ( $\alpha, \beta$ ) -core is a stable structure that ensures different minimum engagement levels of the vertices from different layers, and we aim to reinforce bipartite networks by maximizing the ( $\alpha, \beta$ ) -core. Specifically, given a bipartite network $G$ , degree constraints $\alpha$ and $\beta$ , budgets $b_{1}$ and $b_{2}$ , we aim to find $b_{1}$ upper layer vertices and $b_{2}$ lower layer vertices as anchors and bring them into the ( $\alpha, \beta$ ) -core s.t. the number of non-anchor vertices entering in the ( $\alpha, \beta$ ) -core is maximized. We prove the problem is NP-hard and propose a heuristic algorithm FILVER to solve the problem. FILVER runs $b_{1}+b_{2}$ iterations and choose the best anchor in each iteration. Under a filter-verification framework, it reduces the pool of candidate anchors (in the filter stage) and computes the resulting ( $\alpha, \beta$ ) - core for each anchor vertex more efficiently (in the verification stage). In addition, filter-stage optimizations are proposed to further reduce “dominated” anchors and allow computation-sharing across iterations. To optimize the verification stage, we explore the cumulative effect of placing multiple anchors, which effectively reduces the number of running iterations. Extensive experiments on 18 real-world datasets and a billion-scale synthetic dataset validate the effectiveness and efficiency of our proposed techniques.