Random-walk domination in large graphs

Rong Hua Li, Jeffrey Xu Yu, Xin Huang, Hong Cheng

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

27 Citations (Scopus)


We introduce and formulate two types of random-walk domination problems in graphs motivated by a number of applications in practice (e.g., item-placement problem in online social networks, Ads-placement problem in advertisement networks, and resource-placement problem in P2P networks). Specifically, given a graph G, the goal of the first type of random-walk domination problem is to target k nodes such that the total hitting time of an L-length random walk starting from the remaining nodes to the targeted nodes is minimized. The second type of random-walk domination problem is to find k nodes to maximize the expected number of nodes that hit any one targeted node through an L-length random walk. We prove that these problems are two special instances of the submodular set function maximization with cardinality constraint problem. To solve them effectively, we propose a dynamic-programming (DP) based greedy algorithm which is with near-optimal performance guarantee. The DP-based greedy algorithm, however, is not very efficient due to the expensive marginal gain evaluation. To further speed up the algorithm, we propose an approximate greedy algorithm with linear time complexity w.r.t. the graph size and also with near-optimal performance guarantee. The approximate greedy algorithm is based on carefully designed random walk sampling and sample-materialization techniques. Extensive experiments demonstrate the effectiveness, efficiency and scalability of the proposed algorithms.

Original languageEnglish
Title of host publication2014 IEEE 30th International Conference on Data Engineering, ICDE 2014
Number of pages12
ISBN (Electronic)9781479925551
ISBN (Print)9781479925544
Publication statusPublished - Mar 2014
Event30th IEEE International Conference on Data Engineering, ICDE 2014 - Chicago, IL, United States
Duration: 31 Mar 20144 Apr 2014

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1063-6382
ISSN (Electronic)2375-026X


Conference30th IEEE International Conference on Data Engineering, ICDE 2014
Country/TerritoryUnited States
CityChicago, IL
Internet address

Scopus Subject Areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Random-walk domination in large graphs'. Together they form a unique fingerprint.

Cite this