← volver

Ciclo Seminarios Management Science Invitado: Oleg Prokopyev, Universidad de Pittsburgh

13:30 – 14:25 horas, Sala 401 – 4º pis, Beauchef 851

Invitado: Oleg Prokopyev, Profesor de la Universidad de Pittsburgh

Título de la conferencia: “Finding Critical Links for Closeness Centrality”Abstract

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 describe 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. 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 talk is based on a joint work with Alexander Veremyev (University of Central Florida) and Eduardo Pasiliao (Air Force Research
Laboratory).

Organizan: Ingeniería Industrial U. Chile e Instituto Sistemas Complejos de Ingeniería (ISCI)

Contacto: Pamela Tapia / ptapia@dii.uchile.cl

El seminario incluye almuerzo según disponibilidad, inscripciones AQUÍ