## Abstract

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 language | English |
---|---|

Title of host publication | 2014 IEEE 30th International Conference on Data Engineering, ICDE 2014 |

Publisher | IEEE |

Pages | 736-747 |

Number of pages | 12 |

ISBN (Electronic) | 9781479925551 |

ISBN (Print) | 9781479925544 |

DOIs | |

Publication status | Published - Mar 2014 |

Event | 30th IEEE International Conference on Data Engineering, ICDE 2014 - Chicago, IL, United States Duration: 31 Mar 2014 → 4 Apr 2014 https://ieeexplore.ieee.org/xpl/conhome/6811095/proceeding |

### Publication series

Name | Proceedings - International Conference on Data Engineering |
---|---|

ISSN (Print) | 1063-6382 |

ISSN (Electronic) | 2375-026X |

### Conference

Conference | 30th IEEE International Conference on Data Engineering, ICDE 2014 |
---|---|

Country/Territory | United States |

City | Chicago, IL |

Period | 31/03/14 → 4/04/14 |

Internet address |

## Scopus Subject Areas

- Software
- Signal Processing
- Information Systems