Back to Search
Start Over
Efficient critical relationships identification in bipartite networks
- Source :
- World Wide Web. 25:741-761
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
Abstract
- Bipartite graphs, which consist of two different types of entities, are widely used to model many real-world applications. In bipartite networks, (α,β)-core is an essential model to measure the entity engagement. In this paper, we propose and investigate the problem of (α,β)-core minimization, which aims to identify a set of b edges whose deletion can minimize the size of resulting collapsed (α,β)-core. To our best knowledge, this is the first work to investigate the (α,β)-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.
Details
- ISSN :
- 15731413 and 1386145X
- Volume :
- 25
- Database :
- OpenAIRE
- Journal :
- World Wide Web
- Accession number :
- edsair.doi...........2aa19f5bf44a1f97508680800fd6f24f