Efficient Reinforcement of Bipartite Networks at Billion Scale
- Publisher:
- IEEE
- Publication Type:
- Conference Proceeding
- Citation:
- 2022 IEEE 38th International Conference on Data Engineering (ICDE), 2022, 2022-May, pp. 446-458
- Issue Date:
- 2022
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
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
Please use this identifier to cite or link to this item: