Efficient critical relationships identification in bipartite networks

Bipartite graphs, which consist of two different types of entities, are widely used to model many real-world applications. In bipartite networks, (alpha, beta)-core is an essential model to measure the entity engagement. In this paper, we propose and investigate the problem of (alpha, beta)-core minimization, which aims to identify a set of b edges whose deletion can minimize the size of resulting collapsed (alpha, beta)-core. To our best knowledge, this is the first work to investigate the (alpha, beta)-core minimization problem in bipartite graph. We prove the problem is NP-hard and our object function is monotonic but not submodular. Then, we propose a baseline algorithm by invoking the greedy framework. To reduce the computation cost and candidate space, novel pruning techniques are devised. We further develop a group based algorithm to optimize the search. Finally, we conduct comprehensive experiments over 6 real-life bipartite networks to demonstrate the advantages of the proposed techniques.

Automated summary

This study investigates the problem of (alpha, beta)-core minimization in bipartite graphs, proposing a solution and proving the problem's NP-hardness. By optimizing the search process through algorithmic improvements and reducing computation costs through pruning techniques, the proposed techniques demonstrate advantages in comprehensive experiments on 6 real-life bipartite networks.