Lune

VLDB2021Top-tier venue

Towards an Efficient Weighted Random Walk Domination

Songsong Mo, Zhifeng Bao, Ping Zhang, Zhiyong Peng

Abstract

In this paper, we propose and study a new problem called the weighted random walk domination. Given a weighted graph G ( V, E ) and a budget B of the weighted random walk, it aims to find a k -size set S , which can minimize the total costs of the remaining nodes to access S through the weighted random walk, which is bounded by B. This problem is critical to a range of real-world applications, such as advertising in social networks and telecommunication base station selection in wireless sensor networks. We first present a dynamic programming based greedy method (DpSel) as a baseline. DpSel is time-consuming when | V | is huge. Thus, to overcome this drawback, we propose a matrix-based greedy method (MatrixSel), which can reduce the computation cost greatly. To further accelerate MatrixSel, we propose a BoundSel approach to reduce the number of the gain computations in each candidate selection by proactively estimating the upper bound of the marginal gain of the candidate node. Notably, all methods can achieve an approximation ratio of (1 - 1/ e ). Experiments on real datasets have been conducted to verify the efficiency, effectiveness, memory consumption and scalability of our methods.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound TightenedQintian Guo, Sibo Wang, Zhewei Wei, Ming ChenSIGMOD 2020 · 80 citations

Related papers

  1. Minimizing the Influence of Misinformation via Vertex BlockingJiadong Xie, Fan Zhang, Kai Wang, Xuemin Lin et al.ICDE 2023 · 20 citations
  2. Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update ApproachQintian Guo, Chen Feng, Fangyuan Zhang, Sibo WangSIGMOD 2024 · 15 citations
  3. Multi-layered Network Exploration via Random Walks: From Offline Optimization to Online LearningXutong Liu, Jinhang Zuo, Xiaowei Chen, Wei Chen et al.ICML 2021 · 17 citations
  4. Efficient Resistance Distance Computation: The Power of Landmark-based ApproachesMeihao Liao, Rong-Hua Li, Qiangqiang Dai, Hongyang Chen et al.SIGMOD 2023 · 13 citations
  5. Provable Sensor Sets for Epidemic Detection over Networks with Minimum DelayJack Heavey, Jiaming Cui, Chen Chen, B. Aditya Prakash et al.AAAI 2022 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines