Finding k most influential edges on flow graphs. (April 2017)

• Record Type: Journal Article
• Authors: Wong, Petrie; Sun, Cliz; Lo, Eric; Yiu, Man Lung; Wu, Xiaowei; Zhao, Zhichao; Hubert Chan, T.-H.; Kao, Ben
• Is Part Of: Information systems. Volume 65(2017)
• Page Start: 93
• Page End: 105
• Publication Date: 2017-04
• Subjects: Graph; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2016.12.002
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: In this paper, we formulate a novel question on maximum flow queries. Specifically, this problem aims to find which k edges would have the largest impact on a maximum flow query on a network. This problem has important applications in areas like social network and network planning. We show the inapproximability of the problems and present our heuristic algorithms. Experimental evaluations are carried out on real datasets and results show that our algorithms are scalable and return high quality solutions. Abstract : Highlights: We propose two graph problems: the k Most Beneficial New Edges ( k MBNE), and the k Most Lethal Existing Edges ( k MLEE). First, we prove that k MBNE and k MLEE are inapproximable. It is hard to find even an approximate solution (with constant approximation ratio), let alone find the exact solution. For both k MBNE and k MLEE, 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.