Finding k most influential edges on flow graphs

Petrie Wong; Cliz Sun; Eric Lo; Man Lung Yiu; Xiaowei Wu; Zhichao Zhao; T. H. Hubert Chan; Ben Kao

doi:10.1016/j.is.2016.12.002

Finding k most influential edges on flow graphs

Petrie Wong, Cliz Sun, Eric Lo, Man Lung Yiu, Xiaowei Wu, Zhichao Zhao, T. H. Hubert Chan, Ben Kao

Research output: Journal article publication › Journal article › Academic research › peer-review

13 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	93-105
Number of pages	13
Journal	Information Systems
Volume	65
DOIs	https://doi.org/10.1016/j.is.2016.12.002
Publication status	Published - 1 Apr 2017

Keywords

Graph

ASJC Scopus subject areas

Software
Information Systems
Hardware and Architecture

More information

10.1016/j.is.2016.12.002

Cite this

@article{a2e8c31df64b4474a1d34f48844682f8,

title = "Finding k most influential edges on flow graphs",

abstract = "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.",

keywords = "Graph",

author = "Petrie Wong and Cliz Sun and Eric Lo and Yiu, {Man Lung} and Xiaowei Wu and Zhichao Zhao and {Hubert Chan}, {T. H.} and Ben Kao",

year = "2017",

month = apr,

day = "1",

doi = "10.1016/j.is.2016.12.002",

language = "English",

volume = "65",

pages = "93--105",

journal = "Information Systems",

issn = "0306-4379",

publisher = "Elsevier Ltd",

}

TY - JOUR

T1 - Finding k most influential edges on flow graphs

AU - Wong, Petrie

AU - Sun, Cliz

AU - Lo, Eric

AU - Yiu, Man Lung

AU - Wu, Xiaowei

AU - Zhao, Zhichao

AU - Hubert Chan, T. H.

AU - Kao, Ben

PY - 2017/4/1

Y1 - 2017/4/1

N2 - 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.

AB - 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.

KW - Graph

UR - http://www.scopus.com/inward/record.url?scp=85007197299&partnerID=8YFLogxK

U2 - 10.1016/j.is.2016.12.002

DO - 10.1016/j.is.2016.12.002

M3 - Journal article

SN - 0306-4379

VL - 65

SP - 93

EP - 105

JO - Information Systems

JF - Information Systems

ER -

Finding k most influential edges on flow graphs

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this