Centralidad

El indicador de centralidad o proximidad al centro en teoría de grafos y análisis de redes determina los vértices más importantes del grafo. Las aplicaciones del indicador se utilizan para identificar a la(s) persona(s) más influyente(s) en una red social , nodos de infraestructura clave en Internet o redes metropolitanas y portadores de la enfermedad. Los conceptos de centralidad desarrollados originalmente en el análisis de redes sociales y muchos términos de centralidad se utilizan para medir las fuentes primarias sociológicas [2] . Estas métricas no deben confundirse con las métricas de influencia de nodo , que buscan características cuantitativas de la influencia de cada nodo en la red.

Definición y descripción de los índices de centralidad

Los índices de centralidad son respuestas a la pregunta "¿Qué caracteriza la importancia de un vértice?" La respuesta se da en términos de una función de valor real en los vértices del gráfico, cuyos valores (esperadamente) proporcionan una clasificación que determina los nodos más importantes [3] [4] [5] .

La palabra "importancia" tiene una amplia gama de significados, lo que lleva a muchas definiciones diferentes de centralidad. Se han propuesto dos esquemas de categorización. La "importancia" se puede entender en relación con el tipo de flujo a través de la red. Esto permite clasificar la centralidad por el tipo de flujo que se considera importante [4] . La "importancia" puede entenderse alternativamente como participación en la integridad de la red. Esto permite clasificar las centralidades en función de cómo miden la participación [6] . Ambos enfoques dividen las centralidades en diferentes categorías. Una centralidad que es adecuada para una categoría a menudo no lo será cuando se aplique a otra categoría [4] .

Si las centralidades se clasifican por su participación, queda claro que la mayoría de las centralidades pertenecen a la misma categoría. El número de rutas que se originan en un nodo determinado difiere solo en cómo se determinan y cuentan las rutas. La restricción de acuerdos para este grupo permite la descripción de centralidades en el espectro de rutas desde la longitud uno ( grado de conectividad ) hasta rutas sin restricciones ( grado de influencia ) [3] [7] . La observación de que muchas centralidades comparten estos vínculos explica el alto nivel de correlación entre estos índices.

Descripción de flujos en la red

Se puede pensar en una red como una descripción de los caminos a lo largo de los cuales fluye algo. Esto permite una descripción basada en tipos de flujo y tipos de ruta codificados por centralidad. El flujo puede basarse en transferencias, donde cada elemento indivisible pasa de un nodo a otro, similar a la entrega de paquetes desde la oficina de correos a la casa del cliente. En el segundo caso, hay una reproducción del elemento que pasa al siguiente nodo, de modo que tanto el origen como el destino tienen este elemento. Un ejemplo de tal caso es la difusión de rumores, donde la información se comparte de forma privada, con la fuente y el objetivo informados al final del proceso. El último caso es la propagación paralela, donde un elemento se propaga a través de varios enlaces al mismo tiempo, similar a una transmisión de radio, que brinda la misma información a muchos oyentes al mismo tiempo [4] .

Del mismo modo, el tipo de ruta se puede limitar a: geodésicas (caminos más cortos), rutas (ningún vértice se visita más de una vez), rutas (los vértices se pueden visitar varias veces, pero ningún borde se recorre dos veces) o rutas (tanto los vértices como los bordes). puede ocurrir varias veces) [4] .

Descripción por estructura de paseo

Una clasificación alternativa puede derivarse de la forma en que se construye la centralidad. Esto nuevamente conduce a una división en dos clases: Radial o Mediana. Las centralidades radiales cuentan el número de caminos que comienzan/terminan en un vértice dado. Los grados de conectividad y los grados de influencia son ejemplos de medidas radiales de centralidad, contando el número de caminos de longitud uno o longitud ilimitada. Las centralidades medianas cuentan los caminos que pasan por un vértice dado. El ejemplo canónico es el grado de mediación de Freeman, el número de caminos más cortos que pasan por un vértice dado [6] .

De manera similar, el conteo puede capturar el volumen o la longitud de la ruta. El volumen es el número total de rutas de un tipo dado. Tres ejemplos del párrafo anterior entran en esta categoría. La longitud es la distancia desde un vértice dado a los otros vértices en el gráfico. El grado de proximidad a otros nodos 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 [6] . Tenga en cuenta que esta clasificación depende del tipo de rutas que se calculen (es decir, rutas, circuitos, caminos, geodésicas).

Borgatti y Everett opinaron que esta tipología da una idea de cómo comparar medidas de centralidad. Las centralidades que caen en la misma celda en esta clasificación 2x2 son lo suficientemente similares como para ser alternativas aceptables, y uno puede comparar razonablemente qué puntaje es mejor para un problema dado. Sin embargo, las medidas de diferentes celdas son completamente diferentes. Cualquier determinación de idoneidad relativa sólo puede ocurrir en un contexto predeterminado, qué categoría es más adecuada [6] .

Centralidades volumétricas radiales que existen en el espectro

La descripción a modo de estructura de rutas muestra que casi todas las centralidades utilizadas son medidas radiales-volumétricas. Esto da confianza de que la centralidad de los vértices es una función de la centralidad de los vértices con los que está asociada. Las centralidades difieren en la forma en que se asocian.

Bonacic demostró que si una asociación se define en términos de caminos, entonces una familia de centralidades se puede definir en términos de longitudes de camino bajo consideración [3] . El grado de conectividad cuenta el número de rutas de longitud uno, el grado de influencia cuenta rutas de longitud ilimitada. También son posibles definiciones alternativas de asociaciones. Alpha-centrality le permite tener fuentes externas de influencia para los vértices. La centralidad del subgrafo de Estrada cuenta solo caminos cerrados (triángulos, cuadriláteros, ...).

El corazón de tales medidas es la observación de que los grados de la matriz de adyacencia de un gráfico dan el número de caminos con longitud igual al grado. De manera similar, el exponente de la matriz está estrechamente relacionado con el número de caminos de una longitud dada. Una transformación inicial de la matriz de adyacencia permite la definición de un recuento de diferentes tipos de rutas. En cualquier enfoque, la centralidad del vértice se puede expresar como una suma infinita, o

{\displaystyle \sum_{k=0}^{\infty}A_{R}^{k}\beta^{k))

para potencias matriciales, o

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

para el exponente de la matriz, donde

$k$ igual a la longitud de la ruta,
${\ estilo de visualización A_ {R}}$ es la matriz de adyacencia transformada, y
$\beta$ es un parámetro de compensación que asegura la convergencia de la suma.

La familia de medidas de Bonacic no transforma la matriz de adyacencia. La centralidad alfa reemplaza la matriz de adyacencia con su resolución . La centralidad del subgrafo reemplaza la matriz de adyacencia con su rastro. Independientemente de la transformación inicial de la matriz de adyacencia, todos estos enfoques tienen un comportamiento limitante común. Como tiende a cero, el índice converge al grado de conectividad . Al buscar el valor máximo, el índice converge al grado de influencia [7] . $\beta$ $\beta$

Centralidad de la teoría de juegos

Una característica común de la mayoría de las medidas estándar anteriores es que evalúan la importancia de un nodo, centrándose solo en el papel que desempeña el nodo por sí mismo. Sin embargo, en muchas aplicaciones, este enfoque no será adecuado, ya que se puede detectar la interacción de los nodos si se aplican medidas a los nodos del grupo.

Por ejemplo, considere el problema de detener una epidemia. Mirando la imagen de la red de arriba, ¿qué nodos deben vacunarse? Con base en las medidas descritas anteriormente, queremos reconocer los nodos que son más importantes en la propagación de la enfermedad. Puede que no sea una buena idea utilizar enfoques de centralidad únicamente que se centren en las propiedades individuales de los nodos. Los nodos en el cuadro rojo por sí solos no pueden detener la propagación de la enfermedad, pero cuando se ven como un grupo, vemos claramente que pueden detener la enfermedad si comienza en los nodos , , . Las centralidades de la teoría de juegos intentan tener en cuenta los problemas y oportunidades descritos utilizando las herramientas de la teoría de juegos. El enfoque propuesto por Michalak (et al.) [8] utiliza el vector de Shapley . Debido a la complejidad (en el tiempo) de calcular el vector de Shapley, la mayor parte del esfuerzo en esta área se invierte en el desarrollo de nuevos algoritmos y métodos que se basan en la topología de red específica y la naturaleza especial del problema. Este enfoque puede reducir la complejidad temporal del algoritmo de exponencial a polinomial. $v_{1}$ ${\ Displaystyle v_ {4}}$ ${\ estilo de visualización v_ {5}}$

Restricciones importantes

Los índices de centralidad tienen dos limitaciones importantes, una es obvia, la otra es sutil. Una limitación obvia es que la centralidad que es óptima para una aplicación a menudo no lo es para otra. Además, si no fuera así, no habría necesidad de tantas centralidades diferentes. Una ilustración de este fenómeno la proporciona la cometa de Crackhard , para la cual tres nociones diferentes de centralidad producen tres vértices más centrales diferentes [9] .

Una limitación sutil es que existe una idea errónea generalizada de que la centralidad de los vértices refleja la importancia relativa de los vértices. Los índices de centralidad se desarrollaron explícitamente para la clasificación, lo que permite la selección de los vértices más importantes [3] [4] . Lo hacen bien bajo las limitaciones mencionadas. No fueron diseñados para medir nudos de manera general. Recientemente, los físicos de redes han comenzado a desarrollar métricas de influencia de nodos para resolver este problema.

El error es doble. Primero, clasificar solo en el orden de los vértices, ya que su importancia no refleja la diferencia de importancia entre los diferentes niveles de clasificación. Este hecho se puede mitigar aplicando la centralidad de Freeman a la medida de centralidad en cuestión, lo que da una idea de la importancia de los nodos por sus diversas puntuaciones de centralidad. Además, la centralidad de Freeman le permite comparar algunas redes en términos de indicadores de los nodos con el valor más alto [10] .

En segundo lugar, las propiedades que reflejan (correctamente) los vértices más importantes en una red/aplicación determinada no necesariamente se generalizan al resto de los vértices. Para la mayoría de los demás nodos de la red, la clasificación puede no tener sentido [11] [12] [13] [14] . Esto explica, por ejemplo, por qué solo los primeros resultados de una búsqueda de imágenes de Google aparecen en un orden adecuado. PageRank es una medida muy inestable, que a menudo muestra el rango opuesto después de un pequeño cambio en el parámetro de búsqueda [15] .

Aunque la imposibilidad de generalizar el índice de centralidad al resto de la red no parezca obvia a primera vista, se sigue directamente de las definiciones anteriores. Las redes complejas tienen una topología heterogénea. En qué medida la medida óptima depende de la estructura de la red de los vértices más importantes, en la medida en que la medida óptima para tales vértices no lo es para el resto de la red [11] .

Conectividad

Históricamente, el primer y conceptualmente más simple concepto es el grado de conectividad , que se define como el número de enlaces incidentes a un nodo (es decir, el número de enlaces que tiene un nodo). El grado se puede interpretar en términos del riesgo directo del nodo de atrapar algo que pasa por la red (como un virus o alguna información). En el caso de una red dirigida (donde se dirigen los enlaces), normalmente definimos dos medidas diferentes del grado de conectividad, a saber, grado de entrada y grado de salida . En consecuencia, el grado de entrada es el número de conexiones con el nodo y el grado de salida es el número de conexiones del nodo con otros nodos. Cuando la conexión se asocia con algún aspecto positivo, como la amistad o la cooperación, el grado de entrada suele interpretarse como una especie de popularidad y el grado de salida como sociabilidad.

El grado de conectividad de un vértice para un grafo dado con vértices y aristas se define como $v$ ${\ estilo de visualización G: = (V, E)}$ $|V|$ $|E|$

C_{D}(v)=\grado(v)

Calcular el grado de conectividad de todos los nodos de un gráfico lleva tiempo en la representación de matriz de adyacencia densa del gráfico y tiempo en la representación de matriz dispersa para los bordes . ${\ estilo de visualización \ Theta (V^{2})}$ ${\ estilo de visualización \ Theta (E)}$

La definición de centralidad a nivel de nodo se puede extender a todo el grafo, y en este caso estamos hablando de centralidad de grafo [10] . Sea el nodo con mayor grado de conectividad en . Sea un grafo conexo con nodos que maximiza el siguiente valor (con como el nodo con mayor grado de conectividad en ): ${\ estilo de visualización v*}$ $GRAMO$ ${\ estilo de visualización X: = (Y, Z)}$ ${\ estilo de visualización | Y |}$ ${\ estilo de visualización y*}$ $X$

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

En consecuencia, el grado de centralidad del gráfico es igual a: $GRAMO$

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

El valor es máximo cuando el gráfico contiene un nodo central al que están conectados todos los demás nodos ( gráfico de estrella ), en cuyo caso $H$ $X$

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

Así, para cualquier gráfico ${\ estilo de visualización G: = (V, E),}$

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

Proximidad a otros nodos

En un grafo conexo , el grado normalizado de proximidad de un nodo es igual a la longitud promedio del camino más corto entre el nodo y todos los demás nodos del grafo. Entonces, cuanto más central sea el nodo, más cerca estará de todos los demás nodos.

El grado de proximidad fue definido por Alex Bavelas (1950) como el recíproco de la distancia [16] [17] , es decir

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

donde es igual a la distancia entre los vértices y . Sin embargo, cuando se habla del grado de proximidad a otros nodos, la gente suele referirse a su forma normalizada, generalmente obtenida de la fórmula anterior al multiplicar por , donde es igual al número de nodos en el gráfico. El dimensionamiento permite la comparación entre nodos de gráficos de diferentes tamaños. ${\ estilo de visualización d (y, x)}$ $X$ $y$ $N-1$ $norte$

Considerar la distancia desde o hacia todos los demás nodos no es aplicable a los gráficos no dirigidos, mientras que en los gráficos dirigidos dan resultados bastante diferentes. Por ejemplo, un sitio web puede tener una proximidad saliente alta pero una proximidad entrante baja).

Centralidad armónica

En un gráfico (no necesariamente conectado), la centralidad armónica invierte las operaciones de suma e inversión para determinar el grado de cercanía:

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 es igual al número de nodos en el gráfico. ${\ estilo de visualización 1/d (y, x) = 0}$ $y$ $X$ $N-1$ $norte$

La centralidad armónica fue propuesta por Marchiori y Lathora (2000) [18] , luego de forma independiente por Dekker (2005) bajo el nombre de centralidad valorada [19] y Rochat (2009) [ 20] .

Grado de mediación

El grado de mediación es una medida de la centralidad de un vértice en un gráfico (también hay un grado de mediación de borde , que no se analiza aquí). El grado de mediación cuantifica el número de veces que un nodo une el camino más corto entre otros dos nodos. El grado de mediación fue introducido por Linton Freeman como una medida de la expresión cuantitativa de la interacción de una persona con otras personas en una red social [21] . En este concepto, los vértices que tienen la mayor probabilidad de estar en un camino más corto elegido al azar entre dos vértices elegidos al azar tienen un alto grado de mediación.

El grado de mediación de un vértice en un grafo con vértices se calcula de la siguiente manera: $v$ ${\ estilo de visualización G: = (V, E)}$ $V$

Para cada par de vértices ( s , t ) se calculan los caminos más cortos entre ellos .
Para cada par de vértices ( s , t ), determine la fracción de los caminos más cortos que pasan por el vértice en cuestión (aquí, el vértice v ).
Resumimos estas acciones en todos los pares de vértices ( s , t ).

De forma más compacta, el grado de mediación se puede representar como [22] :

{\displaystyle C_{B}(v)=\sum_{s\neq v\neq t\in V}{\frac {\sigma_{st}(v)}{\sigma_{st})))

donde es igual al número total de caminos más cortos de nodo a nodo , y es igual al número de esos caminos que pasan . El grado de mediación se puede normalizar dividiendo por el número de pares de vértices sin incluir v , que es igual a para gráficos dirigidos e igual a para gráficos no dirigidos . Por ejemplo, en una estrella no dirigida, el vértice central (que está contenido en cualquier camino más corto posible) tiene un grado de mediación (1 si está normalizado), mientras que las hojas (que no están contenidas en ningún camino más corto) tienen un grado de mediación 0. ${\ estilo de visualización \ sigma _ {st}}$ $s$ $t$ ${\ estilo de visualización \ sigma _ {st} (v)}$ $v$ ${\ estilo de visualización (n-1) (n-2)}$ ${\ estilo de visualización (n-1) (n-2)/2}$ ${\ estilo de visualización (n-1) (n-2)/2}$

Desde un punto de vista computacional, tanto el grado de mediación como el grado de proximidad de todos los vértices de un gráfico implican calcular los caminos más cortos entre todos los pares de vértices del gráfico, lo que lleva tiempo cuando se utiliza el algoritmo de Floyd-Warshall . Sin embargo, en gráficos dispersos , el algoritmo de Johnson puede ser más eficiente, ejecutándose en el tiempo . En el caso de gráficos no ponderados, los cálculos se pueden realizar utilizando el algoritmo de Brandes [22] , lo que requiere tiempo . Por lo general, estos algoritmos asumen que los gráficos no están dirigidos y están conectados con la resolución de bucles y múltiples aristas. Cuando se trabaja con gráficos de red que representan conexiones simples que a menudo no tienen bucles ni bordes múltiples (donde los bordes representan conexiones entre personas). En este caso, utilizando el algoritmo de Brandes, el índice de centralidad final se divide por 2 para tener en cuenta que cada ruta más corta se cuenta dos veces [22] . ${\ estilo de visualización O (V ^ {3})}$ $O(V^{2}\log V+VE)$ $O(VE)$

Grado de influencia

El grado de influencia es una medida de la influencia de un nodo en la red . Asigna puntuaciones relativas a todos los nodos de la red basándose en el concepto de que los enlaces a nodos de puntuación alta contribuyen más a la puntuación del nodo en cuestión que el mismo enlace a un nodo de puntuación baja [23] [5] [5] . El PageRank de Google y la centralidad del nodo de Katz son variantes del grado de influencia [24] .

Usando la matriz de adyacencia para encontrar el grado de influencia

Para un grafo dado con vértices, sea la matriz de adyacencia , es decir , si el vértice está conectado con el vértice , y en caso contrario. El índice de centralidad de vértice relativo se puede definir como ${\ estilo de visualización G: = (V, E)}$ $|V|$ ${\ estilo de visualización A = (a_ {v, t})}$ $a_{v,t}=1$ $v$ $t$ $a_{v,t}=0$ $v$

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

donde es el conjunto de vecinos del vértice , y es una constante. Después de pequeñas transformaciones, esta expresión se puede reescribir en notación vectorial como una ecuación para un vector propio ${\ estilo de visualización M (v)}$ $v$ $\lambda$

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

En general, hay muchos valores propios diferentes para los que existe un vector propio distinto de cero. Debido a que los elementos de la matriz de adyacencia no son negativos, existe un solo valor propio más grande que es real y positivo, según el teorema de Frobenius-Perron . Este valor propio más grande da la medida deseada de centralidad [23] . El componente del vector propio asociado da la centralidad relativa de un vértice en la red. El vector propio se define hasta un factor, de modo que solo la relación de centralidades de los vértices está completamente definida. Para determinar el valor absoluto del exponente, es necesario normalizar el vector propio, por ejemplo, para que la suma de todos los vértices sea igual a 1 o normalizar por el número total de vértices n . El método de la potencia es uno de los muchos algoritmos de derivación de valores propios que se pueden utilizar para encontrar este vector propio dominante [24] . Además, esto se puede generalizar para que los elementos de la matriz A puedan ser números reales que representen la fuerza del enlace, como en una matriz estocástica . $\lambda$ $v^{th}$ $v$

Centralidad según Katz

La centralidad según Kac [25] es una generalización del grado de conexión. La conectividad mide la cantidad de vecinos directos y la centralidad de Kac mide la cantidad de todos los nodos que se pueden conectar mediante rutas y penaliza a los nodos lejanos. Matemáticamente, esta centralidad se define como

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

donde es un multiplicador de atenuación del intervalo . $\alfa$ $(0.1)$

Según Katz, la centralidad puede verse como una variante del grado de influencia. Otra forma de centralidad según Kac es

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

En comparación con el grado de influencia , se reemplaza por $x_{j}$ ${\ estilo de visualización x_ {j} + 1.}$

Se demostró [26] que el vector propio principal (correspondiente al valor propio más grande de la matriz de adyacencia ) es el límite de centralidad de Kac cuando k se aproxima desde abajo. $A$ $\alfa$ ${\ estilo de visualización {\ tfrac {1} {\ lambda}}}$

PageRank

PageRank satisface la siguiente igualdad

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 igual al número de vecinos del nodo (o al número de conexiones salientes del grafo dirigido). En comparación con el grado de influencia y centralidad de Katz, el factor de escala es una diferencia importante . La diferencia entre PageRank y el grado de influencia radica en el hecho de que el vector PageRank es un vector propio izquierdo (es decir, un vector propio de la matriz transpuesta, tenga en cuenta que el multiplicador tiene el orden inverso de los índices) [27] . $j$ ${\ estilo de visualización L (j)}$ ${\ Displaystyle a_ {ji}}$

Centralidad de percolación

Hay un montón de medidas de centralidad para determinar la "importancia" de un solo nodo en una red compleja. Sin embargo, reflejan la importancia de un nodo puramente en términos topológicos, y el valor de un nodo no depende de ninguna manera del "estado" del nodo. El valor permanece constante independientemente de la dinámica de la red. Esto es cierto incluso para las medidas de mediación medidas. Sin embargo, un nodo también puede estar ubicado centralmente en términos de grado de intermediación u otra medida de centralidad, pero no estar "ubicado centralmente" en el contexto de una red en la que hay fugas. La fuga de "infección" ocurre en redes complejas en una gran cantidad de escenarios. Una infección viral o bacteriana puede propagarse a través de las redes sociales de las personas, conocidas como redes de contacto. La propagación de enfermedades también se puede ver en un alto nivel de abstracción al considerar una red de ciudades o centros de población conectados por carreteras, ferrocarriles o líneas 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, la "infección" se propaga a través de los enlaces de una red compleja, cambiando los "estados" de los nodos de forma reversible o irreversible. Por ejemplo, en un escenario epidemiológico, los individuos pasan del estado "susceptible" al estado "infectado". Los estados de nodos específicos a medida que se propaga el "contagio" pueden tomar valores binarios (como "una noticia recibida/no recibida"), valores discretos (susceptible/infectado/curado) o incluso valores continuos. (como la proporción de personas infectadas en la ciudad). Lo común en todos estos escenarios es que la propagación de la "infección" provoque un cambio en el estado de los nodos de la red. Con esto en mente, se ha propuesto la centralidad de percolación ( PC ) , que mide la importancia de un nodo en términos de contribuir a la percolación a través de la red. Esta medida fue propuesta por Pairavinan et al .[28] .

La centralidad de filtración se define para un nodo dado y en un momento dado como la proporción de "caminos de filtración" que pasan a través del nodo. Una "ruta de fuga" es la ruta más corta entre un par de nodos donde el nodo de origen se encuentra en un estado de fuga (por ejemplo, infectado). El nodo objetivo puede estar en un estado de percolación, un estado de no percolación o un estado de percolación parcial.

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^{ televisión}}}

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 fuga de un nodo en el momento se denota como y hay dos casos especiales, cuando indica una condición ajustada en el momento y cuando indica una fuga completa en el momento . Los valores entre estos valores significan estados de filtración parcial (por ejemplo, en una red de ciudades, este podría ser el porcentaje de personas infectadas en la ciudad). ${\ estilo de visualización \ sigma _ {sr}}$ $s$ $r$ ${\ estilo de visualización \ sigma _ {sr} (v)}$ $v$ $i$ $t$ ${\ estilo de visualización {x^{t}}_{i}}$ ${\ estilo de visualización {x^{t}}_{i}=0}$ $t$ ${\ estilo de visualización {x^{t}}_{i}=1}$ $t$

Los pesos de las rutas de fuga dependen de los niveles de fuga asignados a los nodos fuente, con base en el postulado de que cuanto mayor sea el nivel de fuga del nodo fuente, más importantes serán las rutas que salen de ese nodo. Los nodos que se encuentran en los caminos más cortos que comienzan en los nodos de alta percolación son, por lo tanto, potencialmente más importantes para la percolación. La definición de PC también se puede ampliar para incluir también los pesos de los nodos de destino. El cálculo de la centralidad de fuga se realiza en el tiempo con una implementación eficiente tomada del algoritmo rápido de Brandes, y si los cálculos requieren tener en cuenta los pesos de los nodos finales, el peor de los casos es el tiempo . ${\ estilo de visualización O (NM)}$ ${\ estilo de visualización O (N ^ {3})}$

Centralidad de clic cruzado

La centralidad entre camarillas de un nodo individual en un gráfico complejo determina las conexiones del nodo con diferentes camarillas . Un nodo con alta centralidad de clics cruzados promueve la difusión de información o enfermedad en el gráfico. Las camarillas son subgrafos en los que cada nodo está conectado a todos los demás nodos de camarilla. La centralidad de clic cruzado de un nodo para un gráfico dado con vértices y bordes se denota como e igual al número de camarillas a las que pertenece el vértice. Esta medida se utilizó en el artículo de Fagani [29] , pero fue propuesta por primera vez por Everett y Borgatti en 1998 bajo el nombre de "centralidad de superposición de camarilla". $v$ ${\ estilo de visualización G: = (V, E)}$ $|V|$ $|E|$ ${\ estilo de visualización X (v)}$ $v$

Centralidad de Freeman

La centralidad de cualquier red es una medida de cuán central es su nodo más central en comparación con otros nodos [10] . La medida de centralidad se calcula entonces (a) como la suma de las diferencias de centralidad entre el nodo más central de la red y todos los demás nodos, y (b) dividiendo este valor por la suma de diferencias teóricamente más grande de cualquier red de la red. mismo tamaño [10] . Entonces cualquier medida de centralidad puede tener su propia medida de centralidad. Hablando formalmente, si es la medida de centralidad del punto , si es la mayor medida de este tipo en la red, y si ${\ estilo de visualización C_ {x} (p_ {i})}$ $i$ $C_{x}(p_{*})$

\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 centralidad de la red es [10] $C_{x}$

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

Medidas de centralidad basadas en diferencias

Para obtener mejores resultados en la clasificación de los nodos de una red dada, Álvarez-Socorro (et al.) [30] utiliza una medida de disimilitud (característica de la teoría de clasificación y análisis de datos) para mejorar la medida de centralidad en redes complejas. Esto se ilustra con el grado de influencia al calcular la centralidad de cada nodo al resolver el problema de valor propio

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

donde (producto de coordenadas), y es una matriz de disimilitud arbitraria , definida en términos de la medida de disimilitud. Por ejemplo, a través de la disimilitud de Jaccard dada por la fórmula $W_{ij}=A_{ij}D_{ij}$ ${\ Displaystyle D_ {ij}}$

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

Esta medida nos permite cuantificar la contribución topológica (de ahí la llamada centralidad de contribución) de cada nodo a la centralidad de un nodo dado, obteniendo una mayor relación peso/importancia de aquellos nodos con mayor disimilitud, ya que esto permite que un nodo dado llegue a nodos que no se puede llegar directamente.

Tenga en cuenta que es no negativa, ya que y son matrices no negativas, por lo que podemos usar el teorema de Frobenius-Perron para asegurar que la solución al problema anterior es única para con c no negativa , lo que nos permite obtener la centralidad de cada nodo de la red. Por tanto, la centralidad del i-ésimo nodo es igual a $W$ $A$ $D$ ${\ estilo de visualización \ lambda = \ lambda _ {max}}$

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

donde es igual al número de nodos de la red. Algunas redes y medidas de disimilitud fueron probadas por Alvarez-Socorro (et al.) [31] y se obtuvieron mejores resultados en los casos estudiados. $norte$

Generalizaciones

Los estudios empíricos y teóricos generalizan el concepto de centralidad en el contexto de redes estáticas a centralidades dinámicas [32] en el contexto de redes dependientes del tiempo y de corta duración [33] [34] [35] .

Para una generalización a las redes ponderadas, consulte Opsal et al [36] .

El concepto de centralidad también se ha generalizado al nivel de grupo. Por ejemplo, el grado de mediación del grupo muestra la proporción de enlaces geodésicos de pares (es decir, caminos de longitud mínima) de nodos que no pertenecen al grupo que pasan por el grupo [37] [38] .

Véase también

Notas

↑ Parte de la terminología está tomada del artículo de A. S. Semenov y M. V. Bartosh "ESTIMACIÓN DE LA ESTABILIDAD DE LA RED DE INTERNET DE LAS COSAS UTILIZANDO INDICADORES DE CENTRALIDAD DE LAS RELACIONES" . Los términos en la literatura en ruso no se han establecido. Así, en el artículo de Evin I. A. Redes complejas: una introducción a la teoría , en lugar del término "grado de mediación", se utilizan los términos "carga de nodo", "conexiones con máxima importancia". En la página Network Metrics , en lugar del término “grado de conectividad”, se utiliza la traducción literal “centralidad por grado”, en lugar de los términos “grado de…” - “centralidad por…”. A veces se utiliza el término "centralidad" en lugar del término "centralidad".
↑ Newman, 2010 .
↑ 1 2 3 4 Bonacich, 1987 , p. 1170–1182.
↑ 1 2 3 4 5 6 Borgatti, 2005 , pág. 55–71.
↑ 1 2 3 Negre, Morzan, Hendrickson et al., 2018 , p. E12201-E12208.
↑ 1 2 3 4 Borgatti, Everett, 2006 , pág. 466–484.
↑ 1 2 Benzi, Klymko, 2013 , pág. 686–706.
↑ Michalak, Aadithya, Szczepański, Ravindran, Jennings, 2013 , pág. 607-650.
↑ Krackhardt, 1990 , pág. 342–369.
↑ 1 2 3 4 5 Freeman, 1979 , pág. 215–239.
↑ 12 Abogado , 2015 , pág. 8665.
↑ da Silva, Viana, da F. Costa, 2012 , p. P07005.
↑ Bauer y Lizier, 2012 , pág. 68007.
↑ Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013 , pág. 1–13.
↑ Ghoshal, Barabsi, 2011 , pág. 394.
↑ Bavelas, 1950 , p. 725–730.
↑ Sabidussi, 1966 , pág. 581–603.
↑ Marchiori, Latora, 2000 , pág. 539–546.
↑ Dekker, 2005 .
↑ Rochat, 2009 .
↑ Freeman, 1977 , pág. 35–41.
↑ 1 2 3 Brandes, 2001 , pág. 163–177.
↑ 12 Newman , 2007 , pág. 1-12.
↑ 12 Sociedad Matemática Estadounidense . (indefinido)
↑ Katz, 1953 , pág. 39–43.
↑ Bonacich, 1991 , pág. 155–168.
↑ ¿Cómo clasifica Google las páginas web? Archivado desde el original el 31 de enero de 2012. 20Q: Acerca de la vida en red
↑ Piraveenan, Prokopenko, Hossain, 2013 , pág. e53095.
↑ Faghani, 2013 , pág. 1815-1826
↑ Alvarez-Socorro, Herrera-Almarza, González-Díaz, 2015 , p. 17095.
↑ Alvarez-Socorro AJ, Herrera-Almarza LA, González-Díaz. La información complementaria para la autocentralidad basada en medidas de disimilitud revela nodos centrales en redes complejas . Grupo Editorial Naturaleza. (indefinido)
↑ Braha, Bar-Yam, 2006 , pág. 59–63.
↑ Colina, Braha, 2010 , pág. 046105.
↑ Bruto, Sayama, 2009 .
↑ Holmes, Saramaki, 2013 .
↑ Opsahl, Agneessens, Skvoretz, 2010 , pág. 245–251.
↑ Everett, Borgatti, 2005 , pág. 57–76.
↑ Puzis, Yagil, Elovici, Braha, 2009 .

Literatura

Redes Newman MEJ : una introducción. — Oxford, Reino Unido: Oxford University Press, 2010.
Newman MEJ Las matemáticas de las redes, // The New Palgrave Encyclopedia of Economics . — Basingstoke, Palgrave Macmillan, 2007.

Felipe Bonacich. Poder y centralidad: una familia de medidas // American Journal of Sociology. - 1987. - T. 92 , núm. 5 . -doi : 10.1086/ 228631 .
Bonacich P. Centralidades grupales e individuales simultáneas // Redes Sociales. - 1991. - T. 13 , núm. 2 . -doi : 10.1016 / 0378-8733(91)90018-o .
Esteban P. Borgatti. Centralidad y Flujo de Red // Redes Sociales. - 2005. - T. 27 . -doi : 10.1016/ j.socnet.2004.11.008 .
Christian F. A. Negre, Uriel N. Morzan, Heidi P. Hendrickson, Rhitankar Pal, George P. Lisi, J. Patrick Loria, Ivan Rivalta, Junming Ho, Victor S. Batista. Centralidad del vector propio para la caracterización de vías alostéricas de proteínas // Actas de la Academia Nacional de Ciencias. - 2018. - T. 115 . -doi : 10.1073/ pnas.1810452115 .
Stephen P. Borgatti, Martin G. Everett. Una perspectiva teórica de grafos sobre la centralidad // Redes sociales. - 2006. - T. 28 , núm. 4 . -doi : 10.1016/ j.socnet.2005.11.005 .
Michele Benzi, Christine Klymko. Un análisis matricial de diferentes medidas de centralidad // SIAM Journal on Matrix Analysis and Applications. - 2013. - T. 36 , núm. 2 . -doi : 10.1137/ 130950550 . - arXiv : 1312.6722 .
Tomasz P. Michalak, Karthik V. Aadithya, Piotr L. Szczepański, Balaraman Ravindran, Nicholas R. Jennings. Cálculo eficiente del valor de Shapley para la centralidad de la red teórica de juegos // Journal of Artificial Intelligence Research. - 2013. - T. 46 .
David Krackhardt. Evaluación del panorama político: estructura, cognición y poder en las organizaciones // Ciencia administrativa trimestral. - 1990. - junio ( vol. 35 , número 2 ). -doi : 10.2307/ 2393394 . — .
Renato da Silva, Matheus Viana, Luciano da F. Costa. Predicción de epidemias a partir de características individuales de los esparcidores // J. Stat. Mec.: Teoría Exp. - 2012. - T. 2012 . -doi : 10.1088 / 1742-5468/2012/07/p07005 . - . -arXiv : 1202.0024 . _
Frank Bauer, Joseph Lizier. Identificación de los propagadores que afectan y estimación eficiente del número de infecciones en modelos epidémicos: un enfoque de conteo de caminatas // Europhys Lett. - 2012. - T. 99 . - S. 68007 . -doi : 10.1209 / 0295-5075/99/68007 . - . -arXiv : 1203.0502 . _
Mile Sikic, Alen Lancic, Nino Antulov-Fantulin, Hrvoje Stefanic. Centralidad epidémica: ¿existe un impacto epidémico subestimado de los nodos periféricos de la red? // The European Physical Journal B. - 2013. - T. 86 , No. 10 . -doi : 10.1140 / epjb/e2013-31025-5 . -arXiv : 1110.2558 . _
Ghoshal G., Barabsi AL Clasificación de estabilidad y nodos súper estables en redes complejas. // NatComun. - 2011. - T. 2 . -doi : 10.1038/ ncomms1396 . — .
Glen Abogado. Comprender el poder de propagación de todos los nodos en una red: una perspectiva de tiempo continuo // Sci Rep. - 2015. - T. 5 . -doi : 10.1038/ srep08665 . - . -arXiv : 1405.6707 . _ — PMID 25727453 .
Linton C. Freeman. Centralidad en las redes sociales: Aclaración conceptual // Redes sociales. - 1979. - Vol. 1 , número. 3 . — S. 215–239 . - doi : 10.1016/0378-8733(78)90021-7 . Archivado desde el original el 22 de febrero de 2016.
Linton Freeman. Un conjunto de medidas de centralidad basadas en la intermediación // Sociometría. - 1977. - T. 40 , núm. 1 . — págs. 35–41 . -doi : 10.2307/ 3033543 . — .
Álex Bavelas. Patrones de comunicación en grupos orientados a tareas // J. Acoust. soc. Soy. - 1950. - T. 22 , núm. 6 _
Sabidussi G. Sabidussi. El índice de centralidad de un grafo // Psicometría. - 1966. - T. 31 , núm. 4 . -doi : 10.1007/ bf02289527 . —PMID 5232444 .
Massimo Marchiori, Vito Latora. Armonía en el mundo pequeño // Physica A: Mecánica estadística y sus aplicaciones. - 2000. - T. 285 , núm. 3–4 . - doi : 10.1016/s0378-4371(00)00311-3 . - . -arXiv : cond - mat/0008357 .
Antonio Decker. Distancia conceptual en el análisis de redes sociales // Revista de estructura social. - 2005. - T. 6 , núm. 3 .
Yannick Rochat. Centralidad de cercanía extendida a grafos no conectados: El índice de centralidad armónica // Aplicaciones del Análisis de Redes Sociales, ASNA 2009 . — 2009.
Ulrik Brandes. Un algoritmo más rápido para la centralidad de intermediación // Journal of Mathematical Sociology. - 2001. - T. 25 , núm. 2 . -doi : 10.1080/ 0022250x.2001.9990249 .
Newman MEJ Las matemáticas de las redes .
Katz L. Un nuevo índice de estatus derivado del índice sociométrico // Psicometría. - 1953. - S. 39-43 .
Piraveenan M., Prokopenko M., Hossain L. Centralidad de la filtración: cuantificación del impacto teórico de gráficos de los nodos durante la filtración en redes // PLOS ONE. - 2013. - T. 8 , núm. 1 . - doi : 10.1371/journal.pone.0053095 . - . — PMID 23349699 .
Mohamamd Reza Faghani. Un estudio de los mecanismos de detección y propagación de gusanos XSS en redes sociales en línea // Transacciones IEEE sobre análisis forense y seguridad de la información. - 2013. - T. 8 , núm. 11 _ -doi : 10.1109/ TIFS.2013.2280884 .
Alvarez-Socorro AJ, Herrera-Almarza GC, González-Díaz LA La autocentralidad basada en medidas de disimilitud revela nodos centrales en redes complejas // Scientific Reports. - 2015. - Noviembre ( vol. 5 ). -doi : 10.1038/ srep17095 . - . —PMID 26603652 .
Braha D., Bar-Yam Y. De la centralidad a la fama temporal: centralidad dinámica en redes complejas // Complejidad. - 2006. - T. 12 , núm. 2 . -doi : 10.1002/ cplx.20156 . - . - arXiv : física/0611295 .
Hill SA, Braha D. Modelo dinámico de redes complejas dependientes del tiempo // Revisión física E. - 2010. - Vol. 82 , no. 4 . -doi : 10.1103/ physreve.82.046105 . - . -arXiv : 0901.4407 . _ — PMID 21230343 .
Redes Adaptativas: Teoría, Modelos y Aplicaciones / Gross T., Sayama H.. - Springer, 2009.
Holme P., Saramaki J. Redes temporales. — Springer, 2013.
Tore Opsahl, Filip Agneessens, John Skvoretz. Centralidad de nodos en redes ponderadas: grado de generalización y caminos más cortos // Redes Sociales. - 2010. - T. 32 , núm. 3 . -doi : 10.1016/ j.socnet.2010.03.006 . Archivado desde el original el 26 de febrero de 2018.
Everett MG, Borgatti SP Extender la centralidad. En PJ Carrington, J. Scott y S. Wasserman (Eds.) // Modelos y métodos en el análisis de redes sociales. - Nueva York: Cambridge University Press, 2005. - S. 57-76.
Puzis R., Yagil D., Elovici Y., Braha D. Ataque colaborativo al anonimato de los usuarios de Internet // Internet Research. - 2009. - T. 19 , núm. 1 . Archivado desde el original el 7 de diciembre de 2013.

Lectura para leer más

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.) Network Analysis: Methodological Foundations , págs. 16-61, LNCS 3418, Springer-Verlag.