Finding Critical Links for Closeness Centrality

Alexander Veremyev (), Oleg A. Prokopyev () and Eduardo L. Pasiliao ()
Additional contact information
Alexander Veremyev: Industrial Engineering and Management Systems, University of Central Florida, Orlando, Florida 32816
Oleg A. Prokopyev: Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261
Eduardo L. Pasiliao: Munitions Directorate, Air Force Research Laboratory, Eglin AFB, Florida 32542

INFORMS Journal on Computing, 2019, vol. 31, issue 2, 367-389

Abstract: Closeness centrality is a class of distance-based measures in the network analysis literature to quantify reachability of a given vertex (or a group of vertices) by other network agents. In this paper, we consider a new class of critical edge detection problems, in which given a group of vertices that represent an important subset of network elements of interest (e.g., servers that provide an essential service to the network), the decision maker is interested in identifying a subset of critical edges whose removal maximally degrades the closeness centrality of those vertices. We develop a general optimization framework, in which the closeness centrality measure can be based on any nonincreasing function of distances between vertices, which, in turn, can be interpreted as communication efficiency between them. Our approach includes three well-known closeness centrality measures as special cases: harmonic centrality , decay centrality , and k -step reach centrality . Furthermore, for quantifying the centrality of a group of vertices we consider three different approaches for measuring the reachability of the group from any vertex in the network: minimum distance to a vertex in the group, maximum distance to a vertex in the group, and the average centrality of vertices in the group. We study the theoretical computational complexity of the proposed models and describe the corresponding mixed integer programming formulations. For solving medium- and large-scale instances of the problem, we first develop an exact algorithm that exploits the fact that real-life networks often have rather small diameters. Then we propose two conceptually different heuristic algorithms. Finally, we conduct computational experiments with real-world and synthetic network instances under various settings, which reveal interesting insights and demonstrate the advantages and limitations of the proposed models and algorithms.

Keywords: critical edge detection; network interdiction; closeness centrality; distance-based centrality; mixed integer programming (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0829 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:2:p:367-389

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().