109 FLINT HALL
80 NEWELL DRIVE
GAINESVILLE, FL 32611
Speaker: Dr. Oleg Prokopyev, Professor, Department of Industrial Engineering, University of Pittsburgh
Title: Finding Critical Links for Closeness Centrality
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 talk, we consider a new class of critical edge detection problems, where 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, where the closeness centrality measure can be based on any non-increasing 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 “small-world” property of real-life networks, and then 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. This research is a joint work with Alexander Veremyev and Eduardo Pasiliao, and is supported by U.S. Air Force Research Laboratory.
Bio: Dr. Oleg Prokopyev is a Professor in the Department of Industrial Engineering at the University of Pittsburgh. He received MS and PhD degrees in industrial and systems engineering from the University of Florida and BS and MS degrees in applied mathematics and physics from Moscow Institute of Physics and Technology (Moscow, Russia). Dr. Prokopyev’s research interests are in the areas of combinatorial optimization, bilevel programming, stochastic programming and applications of Operations Research in health care, bioinformatics, network analysis and military problems. His research has been supported by the National Science Foundation, Air Force Office of Scientific Research (AFOSR), Department of Veteran Affairs and the Defense Threat Reduction Agency. Dr. Prokopyev is a recipient of the AFOSR Young Investigator Program Award. He is the Co-Editor-in-Chief of Optimization Letters and serves on the editorial boards of IIE Transactions, Journal of Global Optimization and Omega.
Industrial & Systems Engineering