Finding k most influential edges on flow graphs

详细信息    查看全文

• 作者：Petrie Wong^b ; ^{kfwong2@cs.hku.hk} ; Cliz Sun^a ; ^{csxzsun@comp.polyu.edu.hk} ; Eric Lo^a ; ^{ericlo@comp.polyu.edu.hk} ; Man Lung Yiu^a ; ^{csmlyiu@comp.polyu.edu.hk} ; Xiaowei Wu^b ; ^{xwwu@cs.hku.hk} ; Zhichao Zhao^b ; ^{zczhao@cs.hku.hk} ; T.-H. Hubert Chan^b ; ^{hubert@cs.hku.hk} ; Ben Kao^b ; ^{kao@cs.hku.hk}
• 关键词：Graph
• 刊名：Information Systems
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：65
• 期：Complete
• 页码：93-105
• 全文大小：1627 K
• 卷排序：65

文摘

We propose two graph problems: the k Most Beneficial New Edges (kMBNE), and the k Most Lethal Existing Edges (kMLEE). First, we prove that kMBNE and kMLEE are inapproximable. It is hard to find even an approximate solution (with constant approximation ratio), let alone find the exact solution. For both kMBNE and kMLEE, we develop polynomial-time heuristic algorithms that give high-quality solutions on real flow graphs. Moreover, we propose several pruning and optimization techniques to speedup our proposed algorithms.