Centralidad

Para el concepto estadístico, consulte Tendencia central .

Ciencia de la red
Teoría
Grafico Red compleja Contagio Mundo pequeño Sin escamas Estructura de la comunidad Filtración Evolución Controlabilidad Dibujo gráfico Capital social Análisis de enlaces Mejoramiento Reciprocidad Cierre Homofilia Transitividad Apego preferencial Teoría del equilibrio Efecto de red Influencia social
Tipos de redes
Informativo (informática) Telecomunicación Transporte Social Colaboración científica Biológico Neural artificial Interdependiente Semántico Espacial Dependencia Flujo en chip
Gráficos
Características Camarilla Componente Cortar Ciclo Estructura de datos Borde Círculo Vecindario Camino Vértice Lista  / matriz de adyacencia Lista  / matriz de incidencia Tipos Bipartito Completo Dirigido Hiper Multi Aleatorio Ponderado
MétricaAlgoritmos
Centralidad La licenciatura Motivo Agrupación Distribución de titulaciones Assortividad Distancia Modularidad Eficiencia
Modelos
Topología Gráfico aleatorio Erdős – Rényi Barabási – Albert Modelo de fitness Watts – Strogatz Exponencial aleatorio (ERGM) Geométrico aleatorio (RGG) Hiperbólico (HGN) Jerárquico Bloque estocástico Entropía máxima Configuración suave Benchmark LFR Dinámica Red booleana basado en agente Epidemia / SIR
LizaCategorias
Temas Software Científicos de la red Categoría: Teoría de redes Categoría: Teoría de grafos
v t mi

En la teoría de grafos y el análisis de redes , los indicadores de centralidad identifican los vértices más importantes dentro de un gráfico. Las aplicaciones incluyen la identificación de las personas más influyentes en una red social , nodos de infraestructura clave en Internet o redes urbanas , superpropagadores de enfermedades y redes cerebrales. ^{[1] [2] Los} conceptos de centralidad se desarrollaron por primera vez en el análisis de redes sociales , y muchos de los términos utilizados para medir la centralidad reflejan su origen sociológico . ^[3] No deben confundirse conmétricas de influencia de nodo , que buscan cuantificar la influencia de cada nodo de la red.

Definición y caracterización de índices de centralidad

Los índices de centralidad son respuestas a la pregunta "¿Qué caracteriza a un vértice importante?" La respuesta se da en términos de una función de valor real en los vértices de un gráfico, donde se espera que los valores producidos proporcionen una clasificación que identifique los nodos más importantes. ^{[4] [5] [6]}

La palabra "importancia" tiene un amplio número de significados, lo que lleva a muchas definiciones diferentes de centralidad. Se han propuesto dos esquemas de categorización. La "importancia" se puede concebir en relación con un tipo de flujo o transferencia a través de la red. Esto permite clasificar las centralidades por el tipo de flujo que consideran importante. ^[5] Alternativamente, la "importancia" puede concebirse como la participación en la cohesión de la red. Esto permite clasificar las centralidades en función de cómo miden la cohesión. ^[7] Ambos enfoques dividen las centralidades en distintas categorías. Una conclusión adicional es que una centralidad que sea apropiada para una categoría a menudo "se equivocará" cuando se aplique a una categoría diferente. ^[5]

Cuando las centralidades se clasifican por su enfoque de la cohesión, se hace evidente que la mayoría de las centralidades habitan una categoría. El recuento del número de caminatas que comienzan desde un vértice determinado difiere solo en cómo se definen y cuentan las caminatas. Restringir la consideración a este grupo permite una caracterización suave que coloca las centralidades en un espectro que va desde los recorridos de longitud uno ( centralidad de grado ) hasta los recorridos infinitos ( centralidad de valores propios ). ^{[4] [8]} La observación de que muchas centralidades comparten estas relaciones familiares quizás explique las correlaciones de alto rango entre estos índices.

Caracterización por flujos de red

Una red puede considerarse una descripción de las rutas por las que fluye algo. Esto permite una caracterización basada en el tipo de flujo y el tipo de camino codificado por la centralidad. Un flujo puede basarse en transferencias, donde cada elemento indivisible pasa de un nodo a otro, como una entrega de paquete que va desde el lugar de entrega a la casa del cliente. Un segundo caso es la duplicación en serie, en la que se replica un elemento para que tanto el origen como el destino lo tengan. Un ejemplo es la propagación de información a través del chisme, con la información que se propaga de forma privada y con los nodos de origen y destino informados al final del proceso. El último caso es la duplicación paralela, con el elemento duplicado en varios enlaces al mismo tiempo,como una transmisión de radio que proporciona la misma información a muchos oyentes a la vez.^[5]

Asimismo, el tipo de ruta se puede restringir a geodésicas (rutas más cortas), rutas (ningún vértice se visita más de una vez), senderos (los vértices se pueden visitar varias veces, ningún borde se recorre más de una vez) o caminatas (vértices y los bordes se pueden visitar / atravesar varias veces). ^[5]

Caracterización por estructura de paseo

Se puede derivar una clasificación alternativa de cómo se construye la centralidad. Esto nuevamente se divide en dos clases. Las centralidades son radiales o medial. Las centralidades radiales cuentan los paseos que comienzan / terminan desde el vértice dado. Las centralidades de grado y valor propio son ejemplos de centralidades radiales, contando el número de caminatas de longitud uno o longitud infinita. Las centralidades mediales cuentan los paseos que pasan por el vértice dado. El ejemplo canónico es la centralidad de intermediación de Freeman , el número de caminos más cortos que pasan por el vértice dado. ^[7]

Asimismo, el conteo puede capturar el volumen o la duración de las caminatas. El volumen es el número total de paseos del tipo dado. Los tres ejemplos del párrafo anterior entran en esta categoría. Longitud captura la distancia desde el vértice dado a los vértices restantes en el gráfico. La centralidad de proximidad de Freeman , la distancia geodésica total desde un vértice dado a todos los demás vértices, es el ejemplo más conocido. ^[7] Tenga en cuenta que esta clasificación es independiente del tipo de caminata contada (es decir, caminata, sendero, camino, geodésico).

Borgatti y Everett proponen que esta tipología proporciona información sobre la mejor manera de comparar las medidas de centralidad. Las centralidades colocadas en el mismo cuadro en esta clasificación 2 × 2 son lo suficientemente similares como para hacer alternativas plausibles; uno puede comparar razonablemente cuál es mejor para una aplicación determinada. Sin embargo, las medidas de diferentes cajas son categóricamente distintas. Cualquier evaluación de aptitud relativa solo puede ocurrir dentro del contexto de predeterminar qué categoría es más aplicable, haciendo que la comparación sea discutible. ^[7]

Existen centralidades de volumen radial en un espectro

La caracterización por estructura de paso muestra que casi todas las centralidades de uso amplio son medidas de volumen radial. Estos codifican la creencia de que la centralidad de un vértice es una función de la centralidad de los vértices con los que está asociado. Las centralidades se distinguen por cómo se define la asociación.

Bonacich demostró que si la asociación se define en términos de caminatas , entonces se puede definir una familia de centralidades en función de la longitud de la caminata considerada. ^{[4] La} centralidad de grado cuenta los recorridos de longitud uno, mientras que la centralidad de valor propio cuenta los recorridos de longitud infinita. También son razonables definiciones alternativas de asociación. La centralidad alfa permite que los vértices tengan una fuente de influencia externa. La centralidad del subgrafo de Estrada propone contar solo caminos cerrados (triángulos, cuadrados, etc.).

El corazón de tales medidas es la observación de que las potencias de la matriz de adyacencia del gráfico dan el número de recorridos de longitud dados por esa potencia. De manera similar, la matriz exponencial también está estrechamente relacionada con el número de caminatas de una longitud determinada. Una transformación inicial de la matriz de adyacencia permite una definición diferente del tipo de paseo contado. Bajo cualquier enfoque, la centralidad de un vértice se puede expresar como una suma infinita, ya sea

${\displaystyle \sum _{k=0}^{\infty }A_{R}^{k}\beta ^{k}}$

para potencias matriciales o

${\displaystyle \sum _{k=0}^{\infty }{\frac {(A_{R}\beta )^{k}}{k!}}}$

para matrices exponenciales, donde

• ${\displaystyle k}$ es la longitud de la caminata,
• ${\displaystyle A_{R}}$ es la matriz de adyacencia transformada, y
• ${\displaystyle \beta }$ es un parámetro de descuento que asegura la convergencia de la suma.

La familia de medidas de Bonacich no transforma la matriz de adyacencia. La centralidad alfa reemplaza la matriz de adyacencia con su resolutivo . La centralidad del subgrafo reemplaza la matriz de adyacencia con su traza. Una conclusión sorprendente es que, independientemente de la transformación inicial de la matriz de adyacencia, todos estos enfoques tienen un comportamiento limitante común. A medida que se acerca a cero, los índices convergen en grados de centralidad . A medida que se acerca a su valor máximo, los índices convergen hacia la centralidad del valor propio . ^[8]${\displaystyle \beta }$${\displaystyle \beta }$

Centralidad de la teoría de juegos

La característica común de la mayoría de las medidas estándar mencionadas anteriormente es que evalúan la importancia de un nodo centrándose solo en el papel que desempeña un nodo por sí mismo. Sin embargo, en muchas aplicaciones, este enfoque es inadecuado debido a las sinergias que pueden ocurrir si el funcionamiento de los nodos se considera en grupos.

Por ejemplo, considere el problema de detener una epidemia. Mirando la imagen de arriba de la red, ¿qué nodos debemos vacunar? Sobre la base de las medidas descritas anteriormente, queremos reconocer los nodos que son los más importantes en la propagación de la enfermedad. Los enfoques basados ​​únicamente en centralidades, que se centran en las características individuales de los nodos, pueden no ser una buena idea. Los nodos en el cuadrado rojo, individualmente no pueden detener la propagación de la enfermedad, pero teniendo en cuenta como un grupo, vemos claramente que pueden detener la enfermedad si se ha iniciado en los nodos , y . Las centralidades de la teoría de juegos intentan consultar los problemas y oportunidades descritos, utilizando herramientas de la teoría de juegos. El enfoque propuesto en ^[9] utiliza el valor de Shapley${\displaystyle v_{1}}$${\displaystyle v_{4}}$${\displaystyle v_{5}}$. Debido a la dureza de la complejidad del tiempo del cálculo del valor de Shapley, la mayoría de los esfuerzos en este dominio se dirigen a implementar nuevos algoritmos y métodos que se basan en una topología peculiar de la red o en un carácter especial del problema. Este enfoque puede llevar a reducir la complejidad del tiempo de exponencial a polinomio.

De manera similar, la distribución de autoridad del concepto de solución ( ^[10] ) aplica el índice de poder de Shapley-Shubik , en lugar del valor de Shapley , para medir la influencia directa bilateral entre los jugadores. La distribución es de hecho un tipo de centralidad engenvector. Se utiliza para clasificar objetos de big data en Hu (2020), ^[11] como la clasificación de universidades estadounidenses.

Limitaciones importantes

Los índices de centralidad tienen dos limitaciones importantes, una obvia y otra sutil. La limitación obvia es que una centralidad óptima para una aplicación suele ser subóptima para una aplicación diferente. De hecho, si no fuera así, no necesitaríamos tantas centralidades diferentes. Una ilustración de este fenómeno es proporcionada por el gráfico de cometas de Krackhardt , para el cual tres nociones diferentes de centralidad dan tres opciones diferentes del vértice más central. ^[12]

La limitación más sutil es la falacia comúnmente sostenida de que la centralidad de los vértices indica la importancia relativa de los vértices. Los índices de centralidad están diseñados explícitamente para producir una clasificación que permita indicar los vértices más importantes. ^{[4] [5]} Esto lo hacen bien, bajo la limitación que acabamos de señalar. No están diseñados para medir la influencia de los nodos en general. Recientemente, los físicos de redes han comenzado a desarrollar métricas de influencia de nodos para abordar este problema.

El error es doble. En primer lugar, un ranking solo ordena los vértices por importancia, no cuantifica la diferencia de importancia entre los diferentes niveles del ranking. Esto puede mitigarse aplicando la centralización de Freeman a la medida de centralidad en cuestión, lo que proporciona una idea de la importancia de los nodos en función de las diferencias de sus puntuaciones de centralización. Además, la centralización de Freeman permite comparar varias redes comparando sus puntuaciones de centralización más altas. ^[13] Este enfoque, sin embargo, rara vez se ve en la práctica. ^{[ cita requerida ]}

En segundo lugar, las características que identifican (correctamente) los vértices más importantes en una red / aplicación determinada no se generalizan necesariamente a los vértices restantes. Para la mayoría de los otros nodos de la red, las clasificaciones pueden no tener sentido. ^{[14] [15] [16] [17]} Esto explica por qué, por ejemplo, solo los primeros resultados de una búsqueda de imágenes de Google aparecen en un orden razonable. El pagerank es una medida muy inestable, que muestra frecuentes cambios de rango después de pequeños ajustes del parámetro de salto. ^[18]

Si bien el hecho de que los índices de centralidad no se generalicen al resto de la red puede parecer al principio contrario a la intuición, se deriva directamente de las definiciones anteriores. Las redes complejas tienen una topología heterogénea. En la medida en que la medida óptima dependa de la estructura de la red de los vértices más importantes, una medida que sea óptima para tales vértices es subóptima para el resto de la red. ^[14]

Centralidad de grado

Artículo principal: Grado (teoría de grafos)

Ejemplos de A) Centralidad de intermediación , B) Centralidad de proximidad , C) Centralidad de vector propio , D) Centralidad de grado , E) Centralidad armónica y F) Centralidad de Katz del mismo gráfico.

Históricamente, el primero y conceptualmente más simple es el grado de centralidad , que se define como el número de enlaces incidentes sobre un nodo (es decir, el número de enlaces que tiene un nodo). El grado se puede interpretar en términos del riesgo inmediato de un nodo de contraer cualquier cosa que fluya a través de la red (como un virus o alguna información). En el caso de una red dirigida (donde los lazos tienen dirección), generalmente definimos dos medidas separadas de centralidad de grado, a saber, grado y grado.. En consecuencia, grado inferior es un recuento del número de vínculos dirigidos al nodo y grado externo es el número de vínculos que el nodo dirige a otros. Cuando los lazos se asocian a algunos aspectos positivos como la amistad o la colaboración, el grado de grado se suele interpretar como una forma de popularidad y el grado de grado como gregarismo.

El grado de centralidad de un vértice , para un gráfico dado con vértices y aristas, se define como${\displaystyle v}$${\displaystyle G:=(V,E)}$${\displaystyle |V|}$${\displaystyle |E|}$

${\displaystyle C_{D}(v)=\deg(v)}$

El cálculo de la centralidad de grados para todos los nodos en un gráfico toma una representación de matriz de adyacencia densa del gráfico, y para los bordes toma una representación de matriz dispersa . Θ ( V 2 ) {\displaystyle \Theta (V^{2})} ${\displaystyle \Theta (E)}$

La definición de centralidad a nivel de nodo se puede extender a todo el gráfico, en cuyo caso estamos hablando de centralización de gráficos . ^[19] Sea el nodo con mayor grado de centralidad en . Sea el gráfico conectado por nodos que maximiza la siguiente cantidad ( siendo el nodo con mayor grado de centralidad en ):${\displaystyle v*}$${\displaystyle G}$${\displaystyle X:=(Y,Z)}$${\displaystyle |Y|}$${\displaystyle y*}$${\displaystyle X}$

${\displaystyle H=\sum _{j=1}^{|Y|}[C_{D}(y*)-C_{D}(y_{j})]}$

En consecuencia, la centralización de grados del gráfico es la siguiente:${\displaystyle G}$

${\displaystyle C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})]}{H}}}$

El valor de se maximiza cuando el gráfico contiene un nodo central al que están conectados todos los demás nodos (un gráfico de estrella ), y en este caso${\displaystyle H}$${\displaystyle X}$

${\displaystyle H=(n-1)\cdot ((n-1)-1)=n^{2}-3n+2.}$

Entonces, para cualquier gráfico ${\displaystyle G:=(V,E),}$

${\displaystyle C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})]}{|V|^{2}-3|V|+2}}}$

Además, una nueva medida global extensa para la centralidad del grado llamada Tendency to Make Hub (TMH) define lo siguiente: ^[2]

${\displaystyle TMK={\frac {\sum _{i=1}^{|V|}[deg(v)]^{2}}{\sum _{i=1}^{|V|}deg(v)}}}$

donde TMH aumenta por aparición de grado de centralidad en la red.

Centralidad de cercanía

Artículo principal: Centralidad de cercanía

En un gráfico conectado , la centralidad de cercanía normalizada (o cercanía ) de un nodo es la longitud promedio de la ruta más corta entre el nodo y todos los demás nodos del gráfico. Por lo tanto, cuanto más central es un nodo, más cerca está de todos los demás nodos.

La cercanía fue definida por Alex Bavelas (1950) como el recíproco de la lejanía , ^{[20] [21]} es decir:

${\displaystyle C(x)={\frac {1}{\sum _{y}d(y,x)}}}$

donde es la distancia entre vértices y . Sin embargo, cuando se habla de centralidad de cercanía, la gente suele referirse a su forma normalizada, generalmente dada por la fórmula anterior multiplicada por , donde está el número de nodos en el gráfico. Este ajuste permite comparaciones entre nodos de gráficos de diferentes tamaños.${\displaystyle d(y,x)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle N-1}$${\displaystyle N}$

Tomar distancias desde o hacia todos los demás nodos es irrelevante en gráficos no dirigidos, mientras que puede producir resultados totalmente diferentes en gráficos dirigidos (por ejemplo, un sitio web puede tener una centralidad de cercanía alta desde el enlace saliente, pero una centralidad de proximidad baja desde los enlaces entrantes).

Centralidad armónica

En un gráfico (no necesariamente conectado), la centralidad armónica invierte la suma y las operaciones recíprocas en la definición de centralidad de proximidad:

${\displaystyle H(x)=\sum _{y\neq x}{\frac {1}{d(y,x)}}}$

donde si no hay camino de a . La centralidad armónica se puede normalizar dividiendo por , donde está el número de nodos en el gráfico.${\displaystyle 1/d(y,x)=0}$${\displaystyle y}$${\displaystyle x}$${\displaystyle N-1}$${\displaystyle N}$

La centralidad armónica fue propuesta por Marchiori y Latora (2000) ^[22] y luego de forma independiente por Dekker (2005), utilizando el nombre "centralidad valorada", ^[23] y por Rochat (2009). ^[24]

Centralidad de intermediación

Artículo principal: centralidad de intermediación

El tono (de rojo = 0 a azul = máx.) Muestra la intermediación del nodo.

La intermediación es una medida de centralidad de un vértice dentro de un gráfico (también existe la intermediación de bordes , que no se analiza aquí). La centralidad de intermediación cuantifica el número de veces que un nodo actúa como puente a lo largo del camino más corto entre otros dos nodos. Fue introducido como una medida para cuantificar el control de un humano sobre la comunicación entre otros humanos en una red social por Linton Freeman . ^[25] En su concepción, los vértices que tienen una alta probabilidad de ocurrir en un camino más corto elegido aleatoriamente entre dos vértices elegidos aleatoriamente tienen una alta intermediación.

La intermediación de un vértice en un gráfico con vértices se calcula de la siguiente manera:${\displaystyle v}$${\displaystyle G:=(V,E)}$${\displaystyle V}$

1. Para cada par de vértices ( s , t ), calcule las rutas más cortas entre ellos.
2. Para cada par de vértices ( s , t ), determine la fracción de caminos más cortos que pasan por el vértice en cuestión (aquí, vértice v ).
3. Suma esta fracción sobre todos los pares de vértices ( s , t ).

De manera más compacta, la intermediación se puede representar como: ^[26]

${\displaystyle C_{B}(v)=\sum _{s\neq v\neq t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st}}}}$

donde es el número total de caminos más cortos de nodo a nodo y es el número de esos caminos que pasan . La intermediación se puede normalizar dividiendo entre el número de pares de vértices sin incluir v , que para gráficos dirigidos es y para gráficos no dirigidos es . Por ejemplo, en un gráfico de estrella no dirigido , el vértice central (que está contenido en cada camino más corto posible) tendría una intermediación de (1, si está normalizado) mientras que las hojas (que están contenidas en caminos no más cortos) tendrían una intermediación de 0.${\displaystyle \sigma _{st}}$${\displaystyle s}$${\displaystyle t}$${\displaystyle \sigma _{st}(v)}$${\displaystyle v}$${\displaystyle (n-1)(n-2)}$${\displaystyle (n-1)(n-2)/2}$${\displaystyle (n-1)(n-2)/2}$

Desde el punto de vista del cálculo, las centralidades de intermediación y proximidad de todos los vértices en un gráfico implican calcular las rutas más cortas entre todos los pares de vértices en un gráfico, lo que requiere tiempo con el algoritmo Floyd-Warshall . Sin embargo, en gráficos dispersos, el algoritmo de Johnson puede ser más eficiente y tomar tiempo. En el caso de gráficos no ponderados, los cálculos se pueden hacer con el algoritmo de Brandes ^[26] que toma O ( V 3 ) {\displaystyle O(V^{3})} O ( V 2 log ⁡ V + V E ) {\displaystyle O(V^{2}\log V+VE)} O ( V E ) {\displaystyle O(VE)} hora. Normalmente, estos algoritmos asumen que los gráficos no están dirigidos y conectados con la tolerancia de bucles y bordes múltiples. Cuando se trata específicamente de gráficos de red, a menudo los gráficos no tienen bucles o bordes múltiples para mantener relaciones simples (donde los bordes representan conexiones entre dos personas o vértices). En este caso, el uso del algoritmo de Brandes dividirá las puntuaciones finales de centralidad por 2 para tener en cuenta que cada ruta más corta se cuenta dos veces. ^[26]

Centralidad del vector propio

Artículo principal: centralidad de vector propio

La centralidad del vector propio (también llamada centralidad propia ) es una medida de la influencia de un nodo en una red . Asigna puntuaciones relativas a todos los nodos de la red basándose en el concepto de que las conexiones a los nodos de puntuación alta contribuyen más a la puntuación del nodo en cuestión que las conexiones iguales a los nodos de puntuación baja. ^{[27] [6]} El PageRank de Google y la centralidad Katz son variantes de la centralidad del vector propio. ^[28]

Uso de la matriz de adyacencia para encontrar la centralidad del vector propio

Para un gráfico dado con número de vértices, sea ​​la matriz de adyacencia , es decir, si el vértice está vinculado al vértice , y de otro modo. La puntuación de centralidad relativa del vértice se puede definir como:${\displaystyle G:=(V,E)}$${\displaystyle |V|}$${\displaystyle A=(a_{v,t})}$${\displaystyle a_{v,t}=1}$${\displaystyle v}$${\displaystyle t}$${\displaystyle a_{v,t}=0}$${\displaystyle v}$

${\displaystyle x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\sum _{t\in G}a_{v,t}x_{t}}$

donde es un conjunto de vecinos de y es una constante. Con una pequeña reordenación, esto se puede reescribir en notación vectorial como la ecuación de vector propio${\displaystyle M(v)}$${\displaystyle v}$${\displaystyle \lambda }$

${\displaystyle \mathbf {Ax} ={\lambda }\mathbf {x} }$

En general, habrá muchos valores propios diferentes para los que existe una solución de vector propio distinto de cero. Dado que las entradas en la matriz de adyacencia no son negativas, existe un valor propio más grande único, que es real y positivo, según el teorema de Perron-Frobenius . Este mayor valor propio da como resultado la medida de centralidad deseada. ^[29] El componente del vector propio relacionado proporciona la puntuación de centralidad relativa del vértice en la red. El vector propio solo se define hasta un factor común, por lo que solo las razones de las centralidades de los vértices están bien definidas. Para definir una puntuación absoluta, se debe normalizar el vector propio, por ejemplo, de modo que la suma de todos los vértices sea 1 o el número total de vértices n${\displaystyle \lambda }$${\displaystyle v^{th}}$${\displaystyle v}$. La iteración de potencia es uno de los muchos algoritmos de valor propio que se pueden utilizar para encontrar este vector propio dominante. ^[28] Además, esto se puede generalizar de modo que las entradas en A puedan ser números reales que representen la fuerza de la conexión, como en una matriz estocástica .

Centralidad de Katz

Artículo principal: centralidad de Katz

La centralidad de Katz ^[30] es una generalización de la centralidad de grado. La centralidad de grados mide el número de vecinos directos, y la centralidad de Katz mide el número de todos los nodos que se pueden conectar a través de una ruta, mientras que las contribuciones de los nodos distantes se penalizan. Matemáticamente, se define como

${\displaystyle x_{i}=\sum _{k=1}^{\infty }\sum _{j=1}^{N}\alpha ^{k}(A^{k})_{ji}}$

donde es un factor de atenuación en .${\displaystyle \alpha }$${\displaystyle (0,1)}$

La centralidad de Katz puede verse como una variante de la centralidad de vector propio. Otra forma de centralidad de Katz es

${\displaystyle x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j}+1).}$

En comparación con la expresión de la centralidad del vector propio, se reemplaza por ${\displaystyle x_{j}}$${\displaystyle x_{j}+1.}$

Se muestra que ^[31] el vector propio principal (asociado con el valor propio más grande de , la matriz de adyacencia) es el límite de la centralidad de Katz como enfoques desde abajo.${\displaystyle A}$${\displaystyle \alpha }$${\displaystyle {\tfrac {1}{\lambda }}}$

Centralidad de PageRank

Artículo principal: PageRank

PageRank satisface la siguiente ecuación

${\displaystyle x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)}}+{\frac {1-\alpha }{N}},}$

dónde

${\displaystyle L(j)=\sum _{i}a_{ji}}$

es el número de vecinos del nodo (o el número de enlaces salientes en un gráfico dirigido). En comparación con la centralidad del vector propio y la centralidad de Katz, una diferencia importante es el factor de escala . Otra diferencia entre la centralidad de PageRank y el vector propio es que el vector PageRank es un vector propio de la izquierda (tenga en cuenta que el factor tiene índices invertidos). ^[32]${\displaystyle j}$${\displaystyle L(j)}$${\displaystyle a_{ji}}$

Centralidad de filtración

Existe una gran cantidad de medidas de centralidad para determinar la "importancia" de un solo nodo en una red compleja. Sin embargo, estas medidas cuantifican la importancia de un nodo en términos puramente topológicos, y el valor del nodo no depende del "estado" del nodo de ninguna manera. Permanece constante independientemente de la dinámica de la red. Esto es cierto incluso para las medidas de intermediación ponderadas. Sin embargo, un nodo puede muy bien estar ubicado centralmente en términos de centralidad de intermediación u otra medida de centralidad, pero puede no estar ubicado "centralmente" en el contexto de una red en la que hay percolación. La filtración de un 'contagio' ocurre en redes complejas en varios escenarios. Por ejemplo, la infección viral o bacteriana puede propagarse a través de las redes sociales de personas, conocidas como redes de contacto.La propagación de enfermedades también se puede considerar en un nivel superior de abstracción, al contemplar una red de ciudades o núcleos de población, conectados por carreteras, ferrocarriles o conexiones aéreas. Los virus informáticos pueden propagarse por las redes informáticas. Los rumores o noticias sobre ofertas y negocios comerciales también pueden difundirse a través de las redes sociales de personas. En todos estos escenarios, un 'contagio' se propaga a través de los enlaces de una red compleja, alterando los 'estados' de los nodos a medida que se propaga, ya sea recuperable o no. Por ejemplo, en un escenario epidemiológico, las personas pasan de un estado "susceptible" a un estado "infectado" a medida que se propaga la infección. Los estados que los nodos individuales pueden tomar en los ejemplos anteriores podrían ser binarios (como recibir / no recibir una noticia), discretos (susceptibles / infectados / recuperados),o incluso continuo (como la proporción de personas infectadas en una ciudad), a medida que se propaga el contagio. La característica común en todos estos escenarios es que la propagación del contagio da como resultado el cambio de estados de los nodos en las redes. La centralidad de percolación (PC) se propuso con esto en mente, que mide específicamente la importancia de los nodos en términos de ayudar a la percolación a través de la red. Esta medida fue propuesta por Piraveenan et al.^[33]

La centralidad de filtración se define para un nodo dado, en un momento dado, como la proporción de 'caminos filtrados' que atraviesan ese nodo. Una "ruta percolada" es la ruta más corta entre un par de nodos, donde el nodo fuente está percolado (p. Ej., Infectado). El nodo objetivo puede estar filtrado o no filtrado, o en un estado parcialmente filtrado.

${\displaystyle PC^{t}(v)={\frac {1}{N-2}}\sum _{s\neq v\neq r}{\frac {\sigma _{sr}(v)}{\sigma _{sr}}}{\frac {{x^{t}}_{s}}{{\sum {[{x^{t}}_{i}}]}-{x^{t}}_{v}}}}$

donde es el número total de caminos más cortos de nodo a nodo y es el número de esos caminos que pasan . El estado de percolación del nodo en el momento se denota por y dos casos especiales son cuando indica un estado no percolado en el momento, mientras que when indica un estado completamente percolado en el momento . Los valores intermedios indican estados parcialmente filtrados (por ejemplo, en una red de municipios, este sería el porcentaje de personas infectadas en ese pueblo).${\displaystyle \sigma _{sr}}$${\displaystyle s}$${\displaystyle r}$${\displaystyle \sigma _{sr}(v)}$${\displaystyle v}$${\displaystyle i}$${\displaystyle t}$${\displaystyle {x^{t}}_{i}}$${\displaystyle {x^{t}}_{i}=0}$${\displaystyle t}$${\displaystyle {x^{t}}_{i}=1}$${\displaystyle t}$

Los pesos adjuntos a las rutas de percolación dependen de los niveles de percolación asignados a los nodos de origen, basándose en la premisa de que cuanto mayor es el nivel de percolación de un nodo de origen, más importantes son las rutas que se originan en ese nodo. Por lo tanto, los nodos que se encuentran en las rutas más cortas que se originan en nodos muy percolados son potencialmente más importantes para la percolación. La definición de PC también puede ampliarse para incluir también los pesos de los nodos de destino. Los cálculos de centralidad de filtración se ejecutan en el tiempo con una implementación eficiente adoptada del algoritmo rápido de Brandes y si el cálculo necesita considerar los pesos de los nodos de destino, el peor de los casos es el tiempo . O ( N M ) {\displaystyle O(NM)} O ( N 3 ) {\displaystyle O(N^{3})}

Centralidad entre camarillas

La centralidad entre camarillas de un solo nodo en un gráfico complejo determina la conectividad de un nodo a diferentes camarillas . Un nodo con alta conectividad entre camarillas facilita la propagación de información o enfermedad en un gráfico. Las camarillas son subgrafos en los que cada nodo está conectado a todos los demás nodos de la camarilla. La conectividad entre camarillas de un nodo para un gráfico dado con vértices y aristas se define como dónde es el número de camarillas a las que pertenece el vértice . Esta medida se utilizó en ^[34], pero Everett y Borgatti la propusieron por primera vez en 1998, donde la llamaron centralidad de superposición de camarillas.${\displaystyle v}$${\displaystyle G:=(V,E)}$${\displaystyle |V|}$${\displaystyle |E|}$${\displaystyle X(v)}$${\displaystyle X(v)}$${\displaystyle v}$

Centralización de Freeman

La centralización de cualquier red es una medida de cuán central es su nodo más central en relación con cuán centrales son todos los demás nodos. ^[13] Entonces, las medidas de centralización (a) calculan la suma de las diferencias de centralidad entre el nodo más central de una red y todos los demás nodos; y (b) dividir esta cantidad por la suma de diferencias teóricamente más grande en cualquier red del mismo tamaño. ^[13] Por tanto, cada medida de centralidad puede tener su propia medida de centralización. Definido formalmente, si es una medida de centralidad de punto , si es la medida más grande en la red, y si:${\displaystyle C_{x}(p_{i})}$${\displaystyle i}$${\displaystyle C_{x}(p_{*})}$

${\displaystyle \max \sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}$

es la mayor suma de diferencias en la centralidad de puntos para cualquier gráfico con el mismo número de nodos, entonces la centralización de la red es: ^[13]${\displaystyle C_{x}}$

${\displaystyle C_{x}={\frac {\sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}{\max \sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}}.}$

Medidas de centralidad basadas en la disimilitud

En la red ilustrada, los nodos verde y rojo son los más diferentes porque no comparten vecinos entre ellos. Entonces, el verde aporta más a la centralidad del rojo que los grises, porque el rojo puede acceder a los azules solo a través del verde, y los nodos grises son redundantes para el rojo, porque puede acceder directamente. a cada nodo gris sin ningún intermediario.

Para obtener mejores resultados en el ranking de los nodos de una red dada, en ^[35] se utilizan medidas de disimilitud (específicas de la teoría de clasificación y minería de datos) para enriquecer las medidas de centralidad en redes complejas. Esto se ilustra con la centralidad del vector propio , calculando la centralidad de cada nodo a través de la solución del problema de los valores propios.

${\displaystyle W\mathbf {c} =\lambda \mathbf {c} }$

donde (producto de coordenadas a coordenadas) y es una matriz de disimilitud arbitraria , definida a través de una medida disimilitaria, por ejemplo, disimilitud de Jaccard dada por${\displaystyle W_{ij}=A_{ij}D_{ij}}$${\displaystyle D_{ij}}$

${\displaystyle D_{ij}=1-{\dfrac {|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{+}(j)|}}}$

Donde esta medida nos permite cuantificar el aporte topológico (por eso se le llama centralidad de contribución) de cada nodo a la centralidad de un nodo dado, teniendo más peso / relevancia aquellos nodos con mayor disimilitud, ya que estos permiten al nodo dado acceder a nodos a los que ellos mismos no pueden acceder directamente.

Es de destacar que no es negativo porque y son matrices no negativas, por lo que podemos usar el teorema de Perron-Frobenius para asegurarnos que el problema anterior tiene una solución única para λ  =  λ _max con c no negativo, lo que nos permite inferir el centralidad de cada nodo de la red. Por lo tanto, la centralidad del i-ésimo nodo es${\displaystyle W}$${\displaystyle A}$${\displaystyle D}$

${\displaystyle c_{i}={\dfrac {1}{n}}\sum _{j=1}^{n}W_{ij}c_{j},\,\,\,\,\,\,i=1,\cdots ,n}$

donde es el número de nodos en la red. Se probaron varias medidas y redes de disimilitud en ^[36] obteniendo mejores resultados en los casos estudiados.${\displaystyle n}$

Extensiones

La investigación empírica y teórica ha extendido el concepto de centralidad en el contexto de redes estáticas a la centralidad dinámica ^[37] en el contexto de redes temporales y dependientes del tiempo. ^{[38] [39] [40]}

Para generalizaciones a redes ponderadas, consulte Opsahl et al. (2010). ^[41]

El concepto de centralidad se extendió también a nivel de grupo. Por ejemplo, la centralidad de intermediación de grupo muestra la proporción de geodésicas que conectan pares de miembros que no pertenecen al grupo que pasan a través del grupo. ^{[42] [43]}

Ver también

• Centralidad alfa
• Estructura núcleo-periferia
• Distancia en gráficos
• Centralidad distintiva

Notas y referencias

1. van den Heuvel MP, Sporns O (diciembre de 2013). "Centros de red en el cerebro humano". Tendencias en ciencias cognitivas . 17 (12): 683–96. doi : 10.1016 / j.tics.2013.09.012 . PMID  24231140 .
2. Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (enero de 2021). "Impacto topológico de los enlaces negativos sobre la estabilidad de la red del cerebro en estado de reposo" . Informes científicos . doi : 10.1038 / s41598-021-81767-7 . PMC 7838299 . PMID 33500525 .  
3. Newman, MEJ 2010. Redes: una introducción. Oxford, Reino Unido: Oxford University Press.
4. Bonacich, Phillip (1987). "Poder y centralidad: una familia de medidas". Revista Estadounidense de Sociología . 92 (5): 1170-1182. doi : 10.1086 / 228631 .
5. Borgatti, Stephen P. (2005). "Centralidad y flujo de red". Redes sociales . 27 : 55–71. CiteSeerX 10.1.1.387.419 . doi : 10.1016 / j.socnet.2004.11.008 . 
6. Christian FA Negre, Uriel N. Morzan, Heidi P. Hendrickson, Rhitankar Pal, George P. Lisi, J. Patrick Loria, Ivan Rivalta, Junming Ho, Victor S. Batista. (2018). "Centralidad de vector propio para la caracterización de vías alostéricas de proteínas" . Actas de la Academia Nacional de Ciencias . 115 (52): E12201 – E12208. doi : 10.1073 / pnas.1810452115 . PMC 6310864 . PMID 30530700 .  
7. Borgatti, Stephen P .; Everett, Martin G. (2006). "Una perspectiva teórica de gráficos sobre centralidad". Redes sociales . 28 (4): 466–484. doi : 10.1016 / j.socnet.2005.11.005 .
8. Benzi, Michele; Klymko, Christine (2013). "Un análisis matricial de diferentes medidas de centralidad". Revista SIAM sobre Análisis y Aplicaciones Matriciales . 36 (2): 686–706. arXiv : 1312.6722 . doi : 10.1137 / 130950550 . S2CID 7088515 . 
9. Michalak, Aadithya, Szczepański, Ravindran y Jennings arXiv : 1402.0567
10. Hu, Xingwei; Shapley, Lloyd (2003). "Sobre las distribuciones de autoridad en las organizaciones". Juegos y comportamiento económico . 45 : 132-170. doi : 10.1016 / s0899-8256 (03) 00130-1 .
11. Hu, Xingwei (2020). "Clasificación de big data por preferencia revelada con aplicación a la clasificación de la universidad" . Revista de Big Data . 7 . doi : 10.1186 / s40537-020-00300-1 .
12. Krackhardt, David (junio de 1990). "Evaluación del panorama político: estructura, cognición y poder en las organizaciones". Trimestral de Ciencias Administrativas . 35 (2): 342–369. doi : 10.2307 / 2393394 . JSTOR 2393394 . 
13. Freeman, Linton C. (1979), "centralidad en las redes sociales: aclaración conceptual" (PDF) , Redes sociales , 1 (3): 215-239, CiteSeerX 10.1.1.227.9549 , doi : 10.1016 / 0378-8733 (78) 90021-7 , archivado desde el original (PDF) el 22 de febrero de 2016 , consultado el 31 de julio de 2014  
14. Abogado, Glenn (2015). "Comprender el poder de propagación de todos los nodos de una red: una perspectiva de tiempo continuo" . Sci Rep . 5 : 8665. arXiv : 1405.6707 . Código Bibliográfico : 2015NatSR ... 5E8665L . doi : 10.1038 / srep08665 . PMC 4345333 . PMID 25727453 .  
15. da Silva, Renato; Viana, Matheus; da F. Costa, Luciano (2012). "Predecir el brote epidémico de las características individuales de los esparcidores". J. Stat. Mech .: Teoría Exp . 2012 (7): P07005. arXiv : 1202.0024 . Código bibliográfico : 2012JSMTE..07..005A . doi : 10.1088 / 1742-5468 / 2012/07 / p07005 . S2CID 2530998 . 
16. Bauer, Frank; Lizier, Joseph (2012). "Identificación de propagadores influyentes y estimación eficiente de los números de infección en modelos epidémicos: un enfoque de conteo de caminatas". Europhys Lett . 99 (6): 68007. arXiv : 1203.0502 . Código bibliográfico : 2012EL ..... 9968007B . doi : 10.1209 / 0295-5075 / 99/68007 . S2CID 9728486 . 
17. Sikic, Mile; Lancic, Alen; Antulov-Fantulin, Nino; Stefanic, Hrvoje (2013). "Centralidad epidémica: ¿hay un impacto epidémico subestimado de los nodos periféricos de la red?". El Diario Europea de Física B . 86 (10): 1–13. arXiv : 1110.2558 . Código Bibliográfico : 2013EPJB ... 86..440S . doi : 10.1140 / epjb / e2013-31025-5 . S2CID 12052238 . 
18. Ghoshal, G .; Barabsi, AL (2011). "Ranking de estabilidad y nodos súper estables en redes complejas" . Nat Commun . 2 : 394. Bibcode : 2011NatCo ... 2..394G . doi : 10.1038 / ncomms1396 . PMID 21772265 . 
19. Freeman, Linton C. "Centralidad en la clarificación conceptual de las redes sociales". Redes sociales 1.3 (1979): 215–239.
20. Alex Bavelas. Patrones de comunicación en grupos orientados a tareas. J. Acoust. Soc. Am , 22 (6): 725–730, 1950.
21. Sabidussi, G (1966). "El índice de centralidad de un gráfico". Psychometrika . 31 (4): 581–603. doi : 10.1007 / bf02289527 . hdl : 10338.dmlcz / 101401 . PMID 5232444 . S2CID 119981743 .  
22. Marchiori, Massimo; Latora, Vito (2000), "Armonía en el mundo pequeño", Physica A: Mecánica estadística y sus aplicaciones , 285 (3–4): 539–546, arXiv : cond-mat / 0008357 , Bibcode : 2000PhyA..285 ..539M , doi : 10.1016 / s0378-4371 (00) 00311-3 , S2CID 10523345 
23. Dekker, Anthony (2005). "Distancia conceptual en el análisis de redes sociales" . Revista de Estructura Social . 6 (3).
24. Yannick Rochat. Centralidad de cercanía extendida a gráficos inconexos: el índice de centralidad armónica (PDF) . Aplicaciones del análisis de redes sociales, ASNA 2009.
25. Freeman, Linton (1977). "Un conjunto de medidas de centralidad basadas en la intermediación". Sociometría . 40 (1): 35–41. doi : 10.2307 / 3033543 . JSTOR 3033543 . 
26. Brandes, Ulrik (2001). "Un algoritmo más rápido para la centralidad de intermediación" (PDF) . Revista de Sociología Matemática . 25 (2): 163-177. CiteSeerX 10.1.1.11.2024 . doi : 10.1080 / 0022250x.2001.9990249 . S2CID 13971996 . Consultado el 11 de octubre de 2011 .   
27. MEJ Newman. "Las matemáticas de las redes" (PDF) . Consultado el 9 de noviembre de 2006 .
28. "Sociedad matemática estadounidense" .
29. MEJ Newman. "Las matemáticas de las redes" (PDF) . Consultado el 9 de noviembre de 2006 .
30. Katz, L. 1953. Un nuevo índice de estado derivado del índice sociométrico. Psychometrika, 39–43.
31. Bonacich, P (1991). "Centralidades grupales e individuales simultáneas". Redes sociales . 13 (2): 155-168. doi : 10.1016 / 0378-8733 (91) 90018-o .
32. ¿Cómo clasifica Google las páginas web? Archivado el 31 de enero de 2012 en Wayback Machine 20Q: About Networked Life
33. Piraveenan, M .; Prokopenko, M .; Hossain, L. (2013). "Centralidad de percolación: cuantificación del impacto teórico-gráfico de los nodos durante la percolación en redes" . PLOS ONE . 8 (1): e53095. Código Bibliográfico : 2013PLoSO ... 853095P . doi : 10.1371 / journal.pone.0053095 . PMC 3551907 . PMID 23349699 .  
34. Faghani, Mohamamd Reza (2013). "Un estudio de mecanismos de detección y propagación de gusanos XSS en redes sociales online". Transacciones IEEE sobre seguridad y análisis forense de la información . 8 (11): 1815–1826. doi : 10.1109 / TIFS.2013.2280884 . S2CID 13587900 . 
35. Alvarez-Socorro, AJ; Herrera-Almarza, GC; González-Díaz, LA (25 de noviembre de 2015). "Eigencentrality basado en medidas de disimilitud revela nodos centrales en redes complejas" . Informes científicos . 5 : 17095. Código Bibliográfico : 2015NatSR ... 517095A . doi : 10.1038 / srep17095 . PMC 4658528 . PMID 26603652 .  
36. Alvarez-Socorro, AJ; Herrera-Almarza; González-Díaz, LA "Información complementaria para Eigencentrality basada en medidas de disimilitud revela nodos centrales en redes complejas" (PDF) . Nature Publishing Group.
37. Braha, D .; Bar-Yam, Y. (2006). "De la centralidad a la fama temporal: centralidad dinámica en redes complejas". Complejidad . 12 (2): 59–63. arXiv : física / 0611295 . Código bibliográfico : 2006Cmplx..12b..59B . doi : 10.1002 / cplx.20156 . S2CID 1776280 . 
38. Hill, SA; Braha, D. (2010). "Modelo dinámico de redes complejas dependientes del tiempo". Revisión E física . 82 (4): 046105. arXiv : 0901.4407 . Código Bibliográfico : 2010PhRvE..82d6105H . doi : 10.1103 / physreve.82.046105 . PMID 21230343 . S2CID 3219870 .  
39. Gross, T. y Sayama, H. (Eds.). 2009. Redes adaptativas: teoría, modelos y aplicaciones. Saltador.
40. Holme, P. y Saramäki, J. 2013. Redes temporales. Saltador.
41. Opsahl, Tore; Agneessens, Filip; Skvoretz, John (2010). "Centralidad de nodos en redes ponderadas: grado de generalización y caminos más cortos" . Redes sociales . 32 (3): 245-251. doi : 10.1016 / j.socnet.2010.03.006 . Archivado desde el original el 26 de febrero de 2018 . Consultado el 23 de abril de 2010 .
42. Everett, MG y Borgatti, SP (2005). Ampliando la centralidad. En PJ Carrington, J. Scott y S. Wasserman (Eds.), Modelos y métodos en el análisis de redes sociales (págs. 57-76). Nueva York: Cambridge University Press.
43. Puzis, R., Yagil, D., Elovici, Y., Braha, D. (2009). Ataque colaborativo al anonimato de los usuarios de Internet Archivado el 7 de diciembre de 2013 en Wayback Machine , Internet Research 19 (1)

Lectura adicional

• Koschützki, D .; Lehmann, KA; Peeters, L .; Richter, S .; Tenfelde-Podehl, D. y Zlotowski, O. (2005) Índices de centralidad. En Brandes, U. y Erlebach, T. (Eds.) Análisis de red: Fundamentos metodológicos , págs. 16–61, LNCS 3418, Springer-Verlag.