Centralidad

Grado de conectividad dentro de un gráfico

En teoría de grafos y análisis de redes , los indicadores de centralidad asignan números o clasificaciones a los nodos dentro de un gráfico correspondiente a su posición en la red. 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 , súper propagadores 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]

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 una gran cantidad de significados, lo que lleva a muchas definiciones diferentes de centralidad. Se han propuesto dos esquemas de categorización. La "importancia" puede concebirse 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] La "importancia" también puede concebirse como 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. Otra conclusión es que una centralidad que es apropiada para una categoría a menudo "equivocará" cuando se aplica a una categoría diferente. ^[5]

Muchas medidas de centralidad, aunque no todas, cuentan efectivamente el número de caminos (también llamados paseos) de algún tipo que pasan por un vértice determinado; las medidas difieren en cómo se definen y cuentan los paseos relevantes. Restringir la consideración a este grupo permite una taxonomía que ubica muchas centralidades en un espectro desde aquellas relacionadas con caminatas de longitud uno (centralidad de grado) hasta caminatas infinitas (centralidad de vector propio). ^{[4] [8]} Otras medidas de centralidad, como la centralidad de intermediación, se centran no sólo en la conectividad general, sino también en ocupar posiciones que son fundamentales para la conectividad de la red.

Caracterización por flujos de red.

Una red puede considerarse una descripción de los caminos por los que fluye algo. Esto permite una caracterización en función del tipo de flujo y el tipo de recorrido codificado por la centralidad. Un flujo puede basarse en transferencias, donde cada artículo indivisible va de un nodo a otro, como una entrega de paquete que va desde el lugar de entrega hasta la casa del cliente. Un segundo caso es la duplicación en serie, en la que un elemento se replica de modo que tanto el origen como el destino lo tengan. Un ejemplo es la propagación de información a través de chismes, donde la información se propaga de forma privada y se informa tanto al nodo de origen como al de destino al final del proceso. El último caso es la duplicación paralela, en la que el elemento se duplica en varios enlaces al mismo tiempo, como una emisión de radio que proporciona la misma información a muchos oyentes a la vez. ^[5]

Del mismo modo, el tipo de ruta puede limitarse 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 atraviesa más de una vez) o paseos (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 a partir de cómo se construye la centralidad. Esto nuevamente se divide en dos clases. Las centralidades son radiales o mediales. Las centralidades radiales cuentan los recorridos que comienzan o terminan en el vértice dado. Las centralidades de grado y valor propio son ejemplos de centralidades radiales, contando el número de paseos de longitud uno o longitud infinita. Las centralidades mediales cuentan los recorridos 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 un 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 caminatas del tipo dado. Los tres ejemplos del párrafo anterior entran en esta categoría. La longitud captura la distancia desde el vértice dado hasta los vértices restantes en el gráfico. La centralidad de cercanía, 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 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; se puede comparar razonablemente cuál es mejor para una aplicación determinada. Sin embargo, las medidas de diferentes sectores son categóricamente distintas. Cualquier evaluación de la idoneidad relativa sólo puede ocurrir dentro del contexto de predeterminar qué categoría es más aplicable, lo que hace que la comparación sea discutible. ^[7]

Las centralidades de volumen radial existen en un espectro.

La caracterización por estructura de recorrido muestra que casi todas las centralidades de uso generalizado son medidas de volumen radial. Estos codifican la creencia de que la centralidad de un vértice es 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 recorridos de longitud uno, mientras que la centralidad de valor propio cuenta recorridos de longitud infinita. También son razonables definiciones alternativas de asociación. La centralidad alfa permite que los vértices tengan una fuente externa de influencia. La centralidad del subgrafo de Estrada propone contar únicamente 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 recorrido 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 rastro. 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 aproxima a cero, los índices convergen al grado 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 antes mencionadas es que evalúan la importancia de un nodo centrándose únicamente 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.

Consideremos, por ejemplo, el problema de detener una epidemia. Mirando la imagen de arriba de la red, ¿qué nodos deberíamos vacunar? Basándonos en las medidas descritas anteriormente, queremos reconocer los nodos que son los más importantes en la propagación de enfermedades. Los enfoques basados ​​únicamente en centralidades, que se centran en 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 enfermedades, pero considerándolos como grupo, vemos claramente que pueden detener la enfermedad si ha comenzado 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 . Debido a la complejidad temporal 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 un carácter especial del problema. Este enfoque puede conducir a reducir la complejidad temporal de exponencial a polinómica. ${\displaystyle v_{1}}$ ${\displaystyle v_{4}}$ ${\displaystyle v_{5}}$

De manera similar, el concepto de solución de distribución de autoridad ( ^[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 de vector propio. 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 que es óptima para una aplicación a menudo no es óptima para otra aplicación diferente. De hecho, si no fuera así, no necesitaríamos tantas centralidades diferentes. Un ejemplo de este fenómeno lo proporciona el gráfico de cometa 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 sólo 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 dependiendo 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 necesaria ]}

En segundo lugar, las características que identifican (correctamente) los vértices más importantes en una red/aplicación determinada no necesariamente se generalizan a los vértices restantes. Para la mayoría de los demás nodos de la red, las clasificaciones pueden no tener sentido. ^{[14] [15] [16] [17]} Esto explica por qué, por ejemplo, sólo los primeros resultados de una búsqueda de imágenes en Google aparecen en un orden razonable. El pagerank es una medida muy inestable que muestra frecuentes inversiones 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 topología heterogénea. En la medida en que la medida óptima depende de la estructura de la red de los vértices más importantes, una medida que es óptima para dichos vértices es subóptima para el resto de la red. ^[14]

Centralidad del título

Ejemplos de A) Centralidad de intermediación , B) Centralidad de cercanía , C) Centralidad de vector propio , D) Centralidad de grado , E) Centralidad armónica y F) Centralidad de Katz del mismo gráfico geométrico aleatorio.

Históricamente, la primera y conceptualmente más simple es la centralidad de grado , que se define como el número de vínculos que inciden sobre un nodo (es decir, el número de vínculos que tiene un nodo). El grado puede interpretarse en términos del riesgo inmediato de que un nodo contraiga 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 vínculos tienen dirección), generalmente definimos dos medidas separadas de centralidad de grado, a saber, grado interno y grado externo . En consecuencia, el grado de entrada es un recuento del número de vínculos dirigidos al nodo y el grado de salida es el número de vínculos que el nodo dirige a otros. Cuando los vínculos se asocian a algunos aspectos positivos como la amistad o la colaboración, el grado de entrada suele interpretarse como una forma de popularidad y el de grado de sociabilidad.

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)}$

Calcular el grado de centralidad para todos los nodos en un gráfico requiere una representación matricial de adyacencia densa del gráfico, y para los bordes toma una representación matricial dispersa . ${\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 del gráfico . ^[19] Sea el nodo con mayor grado de centralidad en . Sea el gráfico conectado de 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, el grado de centralización del gráfico es el 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 en 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 de los títulos denominada Tendency to Make Hub (TMH) se define de la siguiente manera: ^[2]

${\displaystyle {\text{TMH}}={\frac {\sum _{i=1}^{|V|}\deg(v)^{2}}{\sum _{i=1}^{|V|}\deg(v)}}}$

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

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 del camino más corto entre el nodo y todos los demás nodos en el gráfico. Por tanto, cuanto más central sea un nodo, más cerca estará 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]} que es donde está la distancia entre los vértices u y v . Sin embargo, cuando se habla de centralidad de cercanía, la gente suele referirse a su forma normalizada, dada por la fórmula anterior multiplicada por , donde es el número de nodos en el gráfico. ${\textstyle C_{B}(v)=(\sum _{u}d(u,v))^{-1}}$ ${\displaystyle d(u,v)}$ ${\displaystyle N-1}$ ${\displaystyle N}$

${\displaystyle C(v)={\frac {N-1}{\sum _{u}d(u,v)}}.}$

Esta normalización permite comparaciones entre nodos de gráficos de diferentes tamaños. Para muchos gráficos, existe una fuerte correlación entre la inversa de la cercanía y el logaritmo de grado, ^[22] donde es el grado del vértice v mientras que α y β son constantes para cada red. ${\displaystyle (C(v))^{-1}\approx -\alpha \ln(k_{v})+\beta }$ ${\displaystyle k_{v}}$

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 con respecto a los enlaces salientes, pero una centralidad de cercanía baja con respecto a 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 cercanía:

${\displaystyle H(v)=\sum _{u|u\neq v}{\frac {1}{d(u,v)}}}$

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

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

Centralidad de intermediación

El tono (de rojo = 0 a azul = máximo) muestra la intermediación de los nodos.

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 . ^[26] En su concepción, los vértices que tienen una alta probabilidad de ocurrir en un camino más corto elegido al azar entre dos vértices elegidos al azar 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 los caminos más cortos 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: ^[27]

${\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 un nodo a nodo y es el número de esos caminos que pasan por . La intermediación se puede normalizar dividiendo por 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 estelar no dirigido , el vértice central (que está contenido en todos los caminos más cortos posibles) tendría una intermediación de (1, si está normalizado), mientras que las hojas (que no están contenidas en caminos 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 un aspecto de cálculo, tanto las centralidades de intermediación como de cercanía de todos los vértices de un gráfico implican calcular los caminos más cortos entre todos los pares de vértices de 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 llevar tiempo. En el caso de gráficos no ponderados, los cálculos se pueden realizar con el algoritmo de Brandes ^[27] , lo que lleva tiempo. Normalmente, estos algoritmos suponen que los gráficos no están dirigidos y están conectados con la tolerancia de bucles y múltiples aristas. Cuando se trata específicamente de gráficos de red, a menudo los gráficos no tienen bucles ni múltiples aristas para mantener relaciones simples (donde las aristas representan conexiones entre dos personas o vértices). En este caso, el uso del algoritmo de Brandes dividirá las puntuaciones de centralidad finales por 2 para tener en cuenta que cada camino más corto se cuenta dos veces. ^[27] ${\displaystyle O(V^{3})}$ ${\displaystyle O(V^{2}\log V+VE)}$ ${\displaystyle O(VE)}$

Centralidad del 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 nodos con puntuación alta contribuyen más a la puntuación del nodo en cuestión que las conexiones iguales a nodos con puntuación baja. ^{[28] [6]} El PageRank de Google y la centralidad de Katz son variantes de la centralidad de vector propio. ^[29]

Usando 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 en caso contrario. 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 cuales 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áximo ú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. ^[30] El componente del vector propio relacionado proporciona la puntuación de centralidad relativa del vértice en la red. El vector propio solo está definido 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 . La iteración de potencia es uno de los muchos algoritmos de valores propios que pueden usarse para encontrar este vector propio dominante. ^[29] Además, esto se puede generalizar de modo que las entradas en A puedan ser números reales que representen intensidades de conexión, como en una matriz estocástica . ${\displaystyle \lambda }$ ${\displaystyle v^{th}}$ ${\displaystyle v}$

Centralidad de Katz

La centralidad de Katz ^[31] es una generalización de la centralidad de grado. La centralidad de grado 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 centralidad del vector propio, se reemplaza por ${\displaystyle x_{j}}$ ${\displaystyle x_{j}+1.}$

Se muestra que ^[32] 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 cuando se aproxima desde abajo. ${\displaystyle A}$ ${\displaystyle \alpha }$ ${\displaystyle {\tfrac {1}{\lambda }}}$

Centralidad del 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 PageRank y la centralidad del vector propio es que el vector PageRank es un vector propio del lado izquierdo (tenga en cuenta que el factor tiene índices invertidos). ^[33] ${\displaystyle j}$ ${\displaystyle L(j)}$ ${\displaystyle a_{ji}}$

Centralidad de percolación

Existe una serie 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 de su "estado" 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 filtración. La filtración de un "contagio" se produce en redes complejas en varios escenarios. Por ejemplo, una 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 puede considerarse en un nivel más alto de abstracción, contemplando una red de ciudades o centros de población, conectados por carreteras, ferrocarriles o vías aéreas. Los virus informáticos pueden propagarse a través de las redes informáticas. Los rumores o noticias sobre ofertas y acuerdos comerciales también pueden difundirse a través de las redes sociales de las personas. En todos estos escenarios, un "contagio" se propaga sobre 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, los individuos pasan del estado "susceptible" al 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 recibió/no recibió una noticia), discretos (susceptible/infectado/recuperado) o incluso continuos (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. Teniendo esto en cuenta, se propuso la centralidad de percolación (PC), 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. ^[34]

La centralidad de percolación se define para un nodo determinado, en un momento dado, como la proporción de "caminos filtrados" que pasan por ese nodo. Una 'ruta filtrada' es una ruta más corta entre un par de nodos, donde el nodo fuente se filtra (por ejemplo, se infecta). 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 un nodo a nodo y es el número de esos caminos que pasan por . El estado de percolación del nodo en el momento se denota por y dos casos especiales son cuando indica un estado no filtrado en el momento mientras que cuando indica un estado completamente filtrado 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 esa ciudad). ${\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 fuente, basándose en la premisa de que cuanto mayor sea el nivel de percolación de un nodo fuente, más importantes son las rutas que se originan en ese nodo. Por lo tanto, los nodos que se encuentran en caminos más cortos que se originan a partir de nodos altamente percolados son potencialmente más importantes para la percolación. La definición de PC también puede ampliarse para incluir los pesos de los nodos objetivo. Los cálculos de centralidad de percolació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 objetivo, el peor de los casos es el tiempo . ${\displaystyle O(NM)}$ ${\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 con 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 está el número de camarillas a las que pertenece el vértice. Esta medida fue utilizada por Faghani en 2013 ^[35] , pero fue propuesta por primera vez por Everett y Borgatti 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 qué tan central es su nodo más central en relación con qué tan centrales son todos los demás nodos. ^[13] Las medidas de centralización luego (a) calculan la suma de las diferencias en centralidad entre el nodo más central de una red y todos los demás nodos; y (b) dividir esta cantidad por la suma teóricamente mayor de diferencias en cualquier red del mismo tamaño. ^[13] Así, cada medida de centralidad puede tener su propia medida de centralización. Definido formalmente, si es alguna medida de centralidad de punto , si es la medida más grande de este tipo 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}))}}.}$

El concepto se debe a Linton Freeman .

Medidas de centralidad basadas en disimilitud

En la red ilustrada, los nodos verdes y rojos son los más diferentes porque no comparten vecinos entre ellos. Entonces, el verde contribuye más a la centralidad del rojo que los grises, porque el rojo puede acceder a los azules sólo 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 determinada, en ^[36] 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 mediante la solución del problema de valores propios.

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

donde (producto de coordenada a coordenada) y es una matriz de disimilitud arbitraria , definida mediante una medida de disimilitud, 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 la contribución topológica (por eso se llama centralidad de contribución) de cada nodo a la centralidad de un determinado nodo, teniendo más peso/relevancia aquellos nodos con mayor disimilitud, ya que estos permiten al nodo dado acceso a nodos a los que ellos mismos no pueden acceder directamente.

Es de destacar que es no negativo porque y son matrices no negativas, por lo que podemos usar el teorema de Perron-Frobenius para asegurar que el problema anterior tiene una solución única para λ  =  λ _max con c no negativo, lo que nos permite inferir la 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 de la red. Se probaron varias medidas de disimilitud y redes en ^[37] obteniendo mejores resultados en los casos estudiados. ${\displaystyle n}$

Ver también

• Centralidad alfa
• Estructura centro-periferia
• Distancia en gráficos

notas y referencias

1. van den Heuvel MP, Sporns O (diciembre de 2013). "Centros de redes en el cerebro humano". Tendencias en Ciencias Cognitivas . 17 (12): 683–96. doi :10.1016/j.tics.2013.09.012. PMID  24231140. S2CID  18644584.
2. Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (enero de 2021). "Impacto topológico de los enlaces negativos en la estabilidad de la red cerebral en estado de reposo". Informes científicos . 11 (1): 2176. Código bibliográfico : 2021NatSR..11.2176S. 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. S2CID  145392072.
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 del vector propio para la caracterización de vías alostéricas de proteínas". Procedimientos de la Academia Nacional de Ciencias . 115 (52): E12201–E12208. arXiv : 1706.02327 . Código Bib : 2018PNAS..11512201N. doi : 10.1073/pnas.1810452115 . PMC 6310864 . PMID  30530700. {{cite journal}}: CS1 maint: multiple names: authors list (link)
7. Borgatti, Stephen P.; Everett, Martín G. (2006). "Una perspectiva teórica de grafos sobre la centralidad". Redes sociales . 28 (4): 466–484. doi :10.1016/j.socnet.2005.11.005.
8. Benzi, Michele; Klimko, Christine (2013). "Un análisis matricial de diferentes medidas de centralidad". Revista SIAM sobre Análisis y Aplicaciones de Matrices . 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 autoridades 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 al ranking universitario". Revista de Big Data . 7 . arXiv : 2003.12198 . 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". Ciencia Administrativa Trimestral . 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, S2CID  751590, 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 expansión de todos los nodos de una red: una perspectiva de tiempo continuo". Representante de ciencia . 5 : 8665. arXiv : 1405.6707 . Código Bib : 2015NatSR...5E8665L. doi :10.1038/srep08665. PMC 4345333 . PMID  25727453. 
15. da Silva, Renato; Viana, Mateo; da F. Costa, Luciano (2012). "Predecir brotes epidémicos a partir de características individuales de los propagadores". J. estadística. Mec.: Teoría Exp . 2012 (7): P07005. arXiv : 1202.0024 . Código Bib : 2012JSMTE..07..005A. doi :10.1088/1742-5468/2012/07/p07005. S2CID  2530998.
16. Bauer, Frank; Lizier, José (2012). "Identificar propagadores influyentes y estimar eficientemente el número de infecciones en modelos epidémicos: un enfoque de conteo de caminatas". Europhys Lett . 99 (6): 68007. arXiv : 1203.0502 . Código Bib : 2012EL..... 9968007B. doi :10.1209/0295-5075/99/68007. S2CID  9728486.
17. Sikic, Milla; Lancic, Alen; Antulov-Fantulin, Nino; Stefanic, Hrvoje (2013). "Centralidad epidémica: ¿existe un impacto epidémico subestimado de los nodos periféricos de la red?". La revista física europea B. 86 (10): 1–13. arXiv : 1110.2558 . Código Bib : 2013EPJB...86..440S. doi :10.1140/epjb/e2013-31025-5. S2CID  12052238.
18. Ghoshal, G.; Barabsi, AL (2011). "Clasificación de estabilidad y nodos superestables en redes complejas". Comuna Nacional . 2 : 394. Código Bib : 2011NatCo...2..394G. doi : 10.1038/ncomms1396 . PMID  21772265.
19. Freeman, Linton C. "Aclaración conceptual de la centralidad en las redes sociales". Redes sociales 1.3 (1979): 215–239.
20. Álex Bavelas. Patrones de comunicación en grupos orientados a tareas. J. acústico. Soc. Soy , 22 (6): 725–730, 1950.
21. Sabidussi, G (1966). "El índice de centralidad de un gráfico". Psicometrika . 31 (4): 581–603. doi :10.1007/bf02289527. hdl : 10338.dmlcz/101401 . PMID  5232444. S2CID  119981743.
22. Evans, Tim S.; Chen, Bingsheng (2022). "Vincular la centralidad de la red mide cercanía y grado". Física de las Comunicaciones . 5 (1): 172. arXiv : 2108.01149 . Código Bib : 2022CmPhy...5..172E. doi : 10.1038/s42005-022-00949-5 . ISSN  2399-3650. S2CID  236881169.
23. 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
24. Dekker, Anthony (2005). "Distancia conceptual en el análisis de redes sociales". Revista de Estructura Social . 6 (3). Archivado desde el original el 4 de diciembre de 2020 . Consultado el 18 de febrero de 2017 .
25. Yannick Rochat. Centralidad de cercanía extendida a gráficos desconectados: el índice de centralidad armónica (PDF) . Aplicaciones de análisis de redes sociales, ASNA 2009. Archivado (PDF) desde el original el 16 de agosto de 2017 . Consultado el 19 de febrero de 2017 .
26. 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.
27. 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. hdl :10983/23603. S2CID  13971996. Archivado desde el original el 4 de marzo de 2016 . Consultado el 11 de octubre de 2011 . 
28. MEJ Newman. «Las matemáticas de las redes» (PDF) . Archivado (PDF) desde el original el 22 de enero de 2021 . Consultado el 9 de noviembre de 2006 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
29. "Sociedad Estadounidense de Matemáticas". Archivado desde el original el 11 de enero de 2018 . Consultado el 24 de agosto de 2011 .
30. MEJ Newman. «Las matemáticas de las redes» (PDF) . Archivado (PDF) desde el original el 22 de enero de 2021 . Consultado el 9 de noviembre de 2006 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
31. Katz, L. 1953. Un nuevo índice de estatus derivado del índice sociométrico. Psicometrika, 39–43.
32. Bonacich, P (1991). "Centralidades grupales e individuales simultáneas". Redes sociales . 13 (2): 155-168. doi :10.1016/0378-8733(91)90018-o.
33. Cómo clasifica Google las páginas web? Archivado el 31 de enero de 2012 en Wayback Machine 20Q: Acerca de la vida en red
34. Piraveenan, M.; Prokopenko, M.; Hossain, L. (2013). "Centralidad de la percolación: cuantificación del impacto teórico de gráficos de los nodos durante la percolación en redes". MÁS UNO . 8 (1): e53095. Código Bib : 2013PLoSO...853095P. doi : 10.1371/journal.pone.0053095 . PMC 3551907 . PMID  23349699. 
35. Faghani, Mohamamd Reza (2013). "Un estudio de los mecanismos de detección y propagación de gusanos XSS en redes sociales en línea". Transacciones IEEE sobre seguridad y análisis de la información . 8 (11): 1815–1826. doi :10.1109/TIFS.2013.2280884. S2CID  13587900.
36. Álvarez-Socorro, AJ; Herrera-Almarza, GC; González-Díaz, LA (25 de noviembre de 2015). "La centralidad propia basada en medidas de disimilitud revela nodos centrales en redes complejas". Informes científicos . 5 : 17095. Código Bib : 2015NatSR...517095A. doi :10.1038/srep17095. PMC 4658528 . PMID  26603652. 
37. Álvarez-Socorro, AJ; Herrera-Almarza; González-Díaz, LA "Información complementaria para la centralidad propia basada en medidas de disimilitud revela nodos centrales en redes complejas" (PDF) . Grupo Editorial Naturaleza. Archivado (PDF) desde el original el 7 de marzo de 2016 . Consultado el 29 de diciembre de 2015 .

Otras lecturas

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