thumb|300px|Ejemplo de un mismo grafo donde se visualizan distintas medidas de centralidad:A) intermediaciónB) cercaníaC) vector propioD) gradoE) centralidad armónicaF) centralidad de KatzLas tonalidades van del rojo (más centrales) al azul (más periféricos). En teoría de grafos y análisis de redes sociales, el concepto de centralidad refiere a la importancia o prominencia de los vértices (o nodos o actores) dentro de un grafo o red social. Existen cientos de medidas o índices de centralidad, para determinar y comparar cuantitativamente la importancia relativa de un actor dentro de la estructura definida por la red. El listado más completo de estas medidas está documentado en el catálogo en línea CentralityZoo. Usualmente estas medidas se normalizan para retornar valores entre 0 y 1, de modo de poder hacer comparaciones entre distintas redes y casos de estudio.

La centralidad no es un atributo intrínseco de los nodos o actores de una red, como podrían serlo la autoestima, la temperatura, el ingreso monetario, etc. sino un atributo estructural, es decir, un valor asignado que depende de las relaciones del actor con los demás actores de la red. Intuitivamente (aunque dependerá de la medida de centralidad utilizada), en un grafo estrella o red egocéntrica el nodo central debería tener la mayor centralidad, mientras que los nodos periféricos compartirían todos un mismo valor de centralidad, inferior al del centro.

El concepto fue introducido inicialmente por Alex Bavelas en 1948. Es uno de los conceptos más estudiados en el análisis de redes sociales, y muchos de los conceptos relacionados con las medidas de centralidad reflejan su origen sociológico.

En ocasiones, en el caso de relaciones dirigidas o asimétricas, esto es, redes representadas como grafos dirigidos, en lugar de hablar de «centralidad» se suele también hablar de medidas de prestigio o estatus, aunque dependiendo del tipo de relaciones consideradas, también se podría hablar de «rango», «deferencia», «popularidad», etc. En el análisis de redes sociales se suele distinguir también entre centralidad de actor y centralidad de grupo, siendo lo primero equivalente a la noción de centralidad utilizada en este artículo, mientras que la centralidad de grupo, al concepto asociado a la centralización.

Historia El estudio de la centralidad en los sociogramas y las redes sociales se inició a fines de los años 1940 e inicios de los años 1950, de forma paralela a los primeros estudios formales de cliques o camarillas en sociomatrices. Más concretamente, el concepto de centralidad se le adjudica al psicosociólogo Alex Bavelas, por un trabajo de 1948 en que presentó un modelo matemático para grupos en estructuras sociales. A partir de este tipo de estudios es que se introdujo la teoría de grafos como herramienta clave para el análisis de redes sociales.

Definiciones y caracterizaciones de centralidad Una medida (o índice) de centralidad es una fórmula o algoritmo que permite medir la importancia o prominencia de los vértices o actores en un grafo o red social. Sin embargo, para decidir acerca de la validez de un índice de centralidad, es necesario definir primero el significado de esa «importancia» o «prominencia» que se busca medir. En este sentido, y de manera muy general, los actores más centrales o prominentes se pueden definir como aquellos que están ampliamente implicados en relaciones con otros actores. Por lo tanto, un actor central es uno que está implicado (no necesariamente de forma directa) en muchos lazos. Para el caso de grafos dirigidos (o redes asimétricas), un actor prestigioso (o con estatus, rango, deferencia o popularidad, dependiendo de lo que representen las relaciones) es un actor que es objeto o receptor de muchos lazos.

Medidas de centralidad

Las medidas de centralidad se pueden agrupar en dos categorías: medidas radiales (radial measures) y mediales (medial measures). Las primeras toman como punto de referencia un nodo dado que inicia o termina recorridos por la red, mientras que las segundas toman como referencia los recorridos que pasan a través de un nodo dado. Las medidas radiales a su vez se pueden clasificar en medidas de volumen y de longitud, según el tipo de recorridos que consideran. Las primeras miden el volumen (o el número) de recorridos limitados a dicha longitud prefijada, en tanto que las segundas miden la longitud de los recorridos necesarios para alcanzar un volumen prefijado.

Desde la formulación realizada por , se han propuesto diversas medidas de centralidad de un nodo. Existen cuatro medidas clásicas que son ampliamente usadas en el análisis de redes sociales:

nombre de medida nombre en inglés categoría de la medidaradial medialde volumen de longitud centralidad de grado degree centrality centralidad de cercanía closeness centrality centralidad de intermediación betweenness centrality centralidad de vector propio eigenvector centrality

Para algunas de estas medidas existen a su vez versiones más generales o bien generalizaciones para las redes con pesos. Adicionalmente, se puede distinguir entre las medidas «absolutas» de centralidad, que indican un valor no comparable y aquellas que están normalizadas, denominadas medidas «relativas» de centralidad.

En lo que sigue de esta sección, se define formalmente un grafo como un par ordenado , donde es su conjunto de nodos o vértices y su conjunto de aristas. El número de vértices se denota como . Un grafo también se puede representar como una matriz de adyacencia, donde cada posición asume el valor 1 cuando existe la arista , y el valor 0 cuando no existe.

Centralidad de grado

La centralidad de grado (en inglés, degree centrality) es la primera y más simple de las medidas de centralidad. Corresponde sencillamente al grado de un nodo o actor, esto es, al número de aristas o lazos que posee un nodo con los demás.

Formalmente, para un grafo no dirigido (o red social de relaciones simétricas), si para cada nodo , denota el grado de dicho nodo, entonces su centralidad de grado se define como:

Si se tiene la matriz de adyacencia del grafo, entonces la centralidad de grado de un nodo se puede definir como:

Para normalizar esta medida, lo usual es dividir el grado de cada nodo por el número total de nodos de la red. En caso de que la red considerada sea un grafo simple (sin bucles), entonces basta con dividir por el número total de nodos menos 1. En caso de que el grado máximo para un grafo sea demasiado bajo, también se podría dividir por dicho grado máximo. Así, las siguientes son medidas de grado con normalizaciones aceptables: , , o bien

Para grafos dirigidos (o redes sociales con relaciones asimétricas), se pueden definir dos medidas de centralidad de grado diferentes, correspondientes al grado de entrada y al grado de salida, es decir, respectivamente: y

y como matrices de adyacencia: y

Ambas se consideran medidas de prestigio. Dependiendo del contexto, en análisis de redes sociales el grado de entrada podría interpretarse como una medida de popularidad, mientras que el grado de salida como una de actividad o sociabilidad.

En complejidad computacional, el cálculo de esta medida toma para un grafo denso, y para un grafo disperso.

Variantes del grado El grado de un nodo puede verse como el número de caminos de longitud 1 que lo conectan con otros nodos. Una generalización natural a la centralidad de grado, es la centralidad de camino-k (en inglés, k-path centrality) que para cada nodo mide el número de caminos de largo «a lo más » que lo conectan a otros nodos. En un grafo no dirigido, esta medida equivale a la cardinalidad de la vecindad del nodo, considerando una profundidad .

Otra variante es la densidad de ego, donde en lugar de normalizar por el número de nodos o el máximo grado, se escoge el máximo número de aristas posible de la red. Así, para un grafo no dirigido, dependiendo de si el grafo no admite bucles o sí los permite, se tiene, respectivamente: o bien

Si el grafo es dirigido, entonces se tiene, sin bucles y con bucles, respectivamente: o bien

En caso de que solo se divida por el número de aristas del grafo en cuestión, entonces se obtiene el alcance (en inglés, span) del nodo:

También para grafos dirigidos, se define un índice de sociación como la diferencia entre la densidad o media de la «intensidad» total de la red, y el grado de salida o «elecciones» realizadas por el actor:

Centralidad de cercanía

La centralidad de cercanía, o simplemente cercanía (en inglés, closeness), es la más conocida y utilizada de las medidas radiales de longitud. Se basa en calcular la suma o bien el promedio de las distancias geodésicas (o longitudes de los caminos más cortos) desde un nodo hacia todos los demás. Note que mientras mayor sea la «distancia» entre dos vértices, menor será la «cercanía» entre estos. Por lo tanto, la cercanía se define como el inverso multiplicativo de la «lejanía» entre dos vértices.

Formalmente, para un grafo (dirigido o no dirigido), sea la distancia geodésica entre los nodos y , la cercanía de un nodo se define como:

Note que en algunas referencias puede cambiar por .

Sea la matriz de distancias de la red, es decir, aquella matriz cuyos elementos corresponden a la distancia geodésica desde el nodo hasta el nodo , entonces una definición alternativa es la siguiente:

Para normalizar esta medida, se considera el mayor valor posible que podría asumir la medida para un nodo. Si el grafo no admite bucles, entonces un nodo a lo más puede conectarse directamente a los nodos restantes; si admite bucles (y asumimos que no es un multigrafo), entonces podrá conectarse directamente con los nodos de la red. Por lo tanto, la medida normalizada queda definida formalmente, para ambos casos, respectivamente:

o bien

En una red de flujo esta medida se puede interpretar como el tiempo de llegada a destino de algo que fluye a través de la red. También puede interpretarse como la rapidez que tomará la propagación de la información desde un nodo a todos los demás. La cercanía mide de alguna forma la accesibilidad de un nodo en la red. Este concepto es utilizado también de manera similar en topología, donde se define como un espacio métrico.

Note que en un grafo disconexo, la cercanía de todos los vértices será siempre igual a 0, dado que siempre existirá algún otro nodo para el cual la distancia geodésica con él resulta infinita. Por lo tanto, la centralidad de cercanía tiene la desventaja de que solo se puede aplicar, en el caso de redes no dirigidas, sobre grafos conexos o componentes conexos, y para redes dirigidas, sobre componentes fuertemente conexos.

Variantes de la cercanía

En lugar de considerar la suma de las distancias geodésicas de un nodo hacia todos los demás, existe una variante que se enfoca únicamente en hallar la menor de estas distancias geodésicas. La excentricidad de un nodo es la mayor distancia entre ese nodo y cualquier otro del grafo. El centro de Jordan refiere al subconjunto de nodos con menor excentricidad dentro del grafo. Este centro puede encontrarse fácilmente a partir de la matriz de distancias del grafo, seleccionando aquellos nodos que comparten el menor valor máximo de sus respectivas filas en la matriz. Un concepto relacionado muy antiguo es el de centroide, más apropiado específicamente para árboles. La idea es que para cada nodo del árbol, se considera el peso de cada una de sus ramas o caminos que parten desde dicho nodo, donde el peso de una rama es su número de aristas. El nodo se queda con el mayor de los pesos resultantes de entre todas sus ramas. El centroide corresponde así al subconjunto de nodos que comparten el peso final más pequeño.