Multi-centralidad de intermediación

Abstract

A network is a set of actors and relationships between them. A fundamental issue is to find the most important actor, or subset of actors, within the network. There exist several centrality indexes to find the most important actor of the network, according to several contexts. The betweenness centrality is one of these centralities, where the importance of an actor depends on the ratio of shortest paths between actors that go through that actor. Ulrik Brandes provided an efficient algorithm to compute the betweenness centrality of all the actors of a network. In this document, we study the obvious generalization of betweenness centrality for subsets. This means that the importance of a subset of actors depends on the ratio of shortest paths between actors that go through an actor of the subset. We provide an efficient algorithm to compute the betweenness centrality of a subset and an algorithm to find the subset of k actor with the biggest betweenness centrality.

Una red consiste en un conjunto de actores y relaciones entre ellos. Un problema fundamental en redes es encontrar el actor, o conjunto de actores, más importantes dentro de la red. Existe una gran variedad de índices de centralidad para encontrar el actor m as importante de la red en diversos contextos. Uno de estos índices de centralidad es la centralidad de intermediación, donde la importancia de un actor depende de la fracción de caminos mínimos entre actores que pasan por él. Ulrik Brandes proporcionó un algoritmo eficiente para calcular la centralidad de intermediación de todos los actores en una red. En el presente documento, se estudia la generalización obvia de centralidad de intermediación a subconjuntos. Es decir, la importancia de un subconjunto de actores depende de la fracción de caminos mínimos entre actores que pasan por algún vértice del subconjunto. Se propone un algoritmo eficiente para calcular la centralidad de intermediación de un subconjunto y un algoritmo para encontrar el subconjunto con k elementos de mayor centralidad de intermediación.