Fragmentando redes apuntando a influyentes colectivos a un nivel mesoscópico
Teruyoshi Kobayashi & Naoki Masuda
Scientific Reports 6, Article number: 37778 (2016)
doi:10.1038/srep37778
Resumen
Un enfoque práctico para proteger las redes contra los procesos epidémicos, como la propagación de enfermedades infecciosas, malware e información viral nociva, es eliminar previamente algunos nodos influyentes para fragmentar la red en pequeños componentes. Debido a que determinar el orden óptimo para eliminar nodos es un problema computacionalmente difícil, se han propuesto varios algoritmos aproximados para fragmentar eficientemente las redes mediante eliminación secuencial de nodos. Morone y Makse propusieron un algoritmo que emplea la matriz de no retroceso de las redes dadas, que supera a varios algoritmos existentes. De hecho, muchas redes empíricas tienen la estructura de la comunidad, comprometiendo la asunción de la estructura similar al árbol local en la que se basa el algoritmo original. Desarrollamos un algoritmo de inmunización combinando sinérgicamente el algoritmo de Morone-Makse y el graining grueso de la red en el cual consideramos a una comunidad como un supernodo. De esta manera, buscamos identificar nodos que conecten comunidades diferentes a un costo computacional razonable. El algoritmo propuesto funciona más eficientemente que el Morone-Makse y otros algoritmos en redes con estructura comunitaria.
Introducción
La identificación de nodos influyentes en una red es un tema de interés en el análisis de redes, disfrutando de numerosas aplicaciones. Por ejemplo, una eliminación o inmunización de un nodo influyente puede suprimir la propagación de una enfermedad infecciosa que puede ocurrir más tarde. Una campaña de difusión de información viral a partir de un nodo influyente puede tener más éxito que una campaña que comienza desde otros nodos. Existen diversas nociones de nodos influyentes, como lo demuestra una multitud de definiciones de centralidad del nodo correspondientes a las aplicaciones mencionadas anteriormente y otras1. Entre ellos, un criterio principal del nodo influyente es que la eliminación de un nodo, o inmunización, fragmenta eficientemente la red en pequeños fragmentos. Debido a que el problema de encontrar el conjunto mínimo de nodos a inmunizar para fragmentar la red es NP-hard2, se han propuesto diversos algoritmos de inmunización para determinar el orden de los nodos que se van a retirar para realizar una fragmentación eficiente de la red2, 5,6,7,8,9,10,11,12, a veces con la limitación de que la información sobre la red está sólo parcialmente disponible6,13,14,15,16,17. En particular, aunque los centros de inmunización (es decir, los nodos con un gran grado) primero es intuitivo y mucho mejor que la selección aleatoria de los nodos a inmunizar18,19,20, muchos algoritmos de inmunización superan al algoritmo de inmunización del primer hub.
Morone y Makse propusieron un algoritmo escalable y potente para eliminar secuencialmente nodos y fragmentar la red en pequeños componentes tan pronto como sea posible9. Fundado en el enfoque de paso de mensajes y la teoría de matrices que no retroceden, el método calcula la llamada influencia colectiva (CI) para cada nodo para clasificar los nodos para priorización. Su método, que se conoce como el algoritmo CI, supera a varios otros métodos conocidos en el modelo y las redes empíricas. En el presente estudio, se propone un nuevo IC basado en la inmunización algoritmo que está diseñado para funcionar bien cuando la red tiene la estructura de la comunidad.
El algoritmo CI supone que la red dada es localmente similar a un árbol. De hecho, la mayoría de las redes empíricas no son localmente parecidas a las de un árbol. A nivel microscópico, las redes empíricas suelen estar agrupadas, es decir, llenas de triángulos1. A nivel mesoscópico, muchas redes están compuestas de comunidades, de tal manera que los vínculos son densos dentro de las comunidades y escasos entre diferentes comunidades21. Aunque el algoritmo CI también parece funcionar de manera eficiente en las redes loopy a menos que los bucles no son excesivos9, el rendimiento del algoritmo CI en las redes con estructura de la comunidad no está claro. Algunos algoritmos de inmunización existentes están explícita o implícitamente informados por la estructura de la comunidad4,5,6,10,15,16,22,23. Los algoritmos de inmunización que utilizan la centralidad de intermediación son eficaces en redes con estructura comunitaria6,7,16,22,23. Sin embargo, no son escalables debido a un alto coste computacional de cálculo de la centralidad de intermediación24. Para otros algoritmos de inmunización que explotan la estructura de la comunidad de redes, su desempeño relativo al algoritmo de CI es desconocido en general5,10 o al menos para redes con estructura de comunidad4,9. Sin embargo, otros algoritmos de inmunización basados en la comunidad imponen que sólo se dispone de información local sobre la red, imitando restricciones realistas6,15,16. Esta limitación limita naturalmente el rendimiento de un algoritmo de inmunización.
Desarrollamos un algoritmo de inmunización mediante la formulación de un algoritmo de CI para una red de grano grueso, en el que un nodo representa una comunidad, y un enlace ponderado representa el número de enlaces entre diferentes comunidades. Se compara el rendimiento del algoritmo propuesto con el del algoritmo CI[9] y el algoritmo convencional que apunta a los hubs18,19,20 y otros5,10 cuando las redes tienen estructura comunitaria.
Teoría
Considere una red no dirigida y no ponderada que tenga
N nodos. El objetivo de un algoritmo de inmunización es eliminar secuencialmente los nodos para fragmentar la red tan pronto como sea posible, es decir, con un pequeño número de nodos eliminados.
Influencia colectiva
El algoritmo CI se basa en la puntuación de los nodos según el valor de CI[9]. El CI del nodo i se define como
donde
ki es el grado del nodo
i, y es el conjunto de nodos a distancia del nodo
i. Cuando, el IC es equivalente al grado, mientras que el orden de rango se refiere.
El algoritmo CI calcula el valor de todos los nodos y elimina el nodo con el mayor valor de CI en un solo paso. A continuación, los valores de CI de todos los nodos restantes se vuelven a calcular y se repite el mismo procedimiento.
De hecho, usamos el orden de los nodos que se eliminarán determinado anteriormente como una orden tentativa. Para mejorar el rendimiento general, reordenamos los nodos reinsertándolos de la siguiente manera. Partiendo de la situación en la que la fracción de nodos en el componente más grande conectado (LCC) es igual o menor que 0,01 por primera vez. A continuación, calculamos para cada nodo eliminado i el número de componentes que el nodo i conecta si se vuelve a insertar en la red actual. A continuación, agregamos el nodo que conecta el número más pequeño de componentes conectados. Repetimos este procedimiento hasta que todos los nodos eliminados se vuelvan a insertar de tal manera que se restaure la red inicial.
El tiempo de cálculo del algoritmo CI se evalúa como sigue9. El cálculo de requiere O (1) tiempo para un nodo, y por lo tanto O (N) tiempo para todos los nodos. Dado que la clasificación de los valores consume tiempo O (N logN), cada paso del algoritmo CI consume tiempo O (N logN). Por lo tanto, el tiempo de cálculo total hasta que se eliminan los nodos O (N) se evalúa como
O(N2 logN). Sin embargo, explotando el hecho de que los valores de CI de sólo O (1) nodos se ven afectados por la eliminación de un solo nodo, se puede acelerar el mismo algoritmo con una estructura de datos de montón máximo, dando O (N logN) .
Influencia colectiva basada en la comunidad
La estructura de la comunidad puede hacer que una red no sea localmente similar a un árbol. Proponemos un algoritmo de inmunización mediante la ejecución de una variante de red ponderada del algoritmo CI en una red de grano grueso en el que una comunidad constituye un supernodo. Primero ejecutamos un algoritmo de detección de comunidad. Denotan por NC el número de comunidades y por
la matriz de adyacencia ponderada de grano grueso NC × NC cuyo elemento (I, J) es igual al número de enlaces que conectan las comunidades I y J (I ≠ J). Utilizamos minúsculas (por ejemplo, i, j) para indicar nodos individuales y mayúsculas (por ejemplo, I, J) para denotar supernodos, es decir, comunidades, a lo largo del texto. Los elementos diagonales de
se ponen a cero.
Supongamos que la red de grano grueso es localmente similar a un árbol. Teniendo en cuenta el hecho de que la red de grano grueso es generalmente una red ponderada, definimos el IC de la comunidad I en la red de grano grueso por
donde
Ball
denota el conjunto de las comunidades cuya distancia de la comunidad I es igual en la red de grano grueso.
Establecimos
Esta definición es análoga a zi ≡ ki - 1 en la Ec. (1). Con esta definición de, el IC de la comunidad I es igual a cero cuando sólo tengo un vecino, como en el CI original9,26.
Establecimos
Donde J es una comunidad que está a distancia de I y J- es la comunidad que está a distancia
de I y en el camino entre I y J (Fig. 1 (a)). Cabe señalar que
es igual a cero si J- es el único vecino de J. También debe observarse que cuando cada comunidad consta de un solo nodo en la red original,
para 1 ≤ i ≤ N. La ecuación (5) Está mal definido para
. Para ser coherente con la definición original de la IC, definimos
para
. Entonces,
es grande cuando el nodo I tiene un gran grado en la red de grano grueso.
Figura 1: Concepto de la influencia colectiva basada en la comunidad.
(a) Vista egocéntrica de la red de grano grueso. Cada círculo representa una comunidad. Dos comunidades están adyacentes por un enlace ponderado si un nodo en una comunidad está conectado a al menos un nodo en la otra comunidad. El peso del enlace en la red de grano grueso es igual al número de enlaces que conectan las dos comunidades en la red original. Se asume la estructura similar a un árbol local de la red de grano grueso. (b) Ilustración de 
y 
para 
, en cuyo caso I + = J-. Una línea representa un vínculo en la red original. El círculo discontinuo representa la comunidad iésima. (c) Esquema de la reinserción comunitaria. Un círculo discontinuo representa una comunidad. Supongamos que vamos a reinsertar el nodo i o j. Si se reinsertaron, el nodo iy j tendrían un camino a dos y tres comunidades, respectivamente. Por lo tanto, reinsertamos el nodo i.
Sea A =
(Aij) la matriz de adyacencia de la red original. La ecuación (3) se reescribe como
Donde I + es la comunidad adyacente a I (de ahí la distancia uno de I) a través de la cual se alcanza J desde I (figura 1 (b)). Sobre la base de la ecuación (6), definimos la influencia colectiva basada en la comunidad (CbCl) del nodo i, denotada por CbCI (i), como
Donde el nodo i pertenece a la comunidad I. En la ecuación (7), la importancia de un nodo se deriva de tres factores. En primer lugar, CbCI (i) es proporcional a, que es esencialmente el número de vínculos inter-comunitarios de la comunidad a la que pertenece. En segundo lugar, CbCl (i) es grande si I tiene muchos nodos de alto grado a distancia en la red de grano grueso (es decir, la suma de
). En tercer lugar, CbCI (i) es grande si el nodo i tiene muchos enlaces inter-comunitarios en relación con el número total de enlaces inter-comunitarios que la comunidad I tiene (es decir,
). Se establecen
las siguientes simulaciones numéricas. Cuando, I + en las ecuaciones (6) y (7) coinciden con J- en la Ec. (5) (figura 1 (b)).
Quitamos el nodo con el mayor valor CbCI. Si hay nodos múltiples con el mismo valor CbCI más grande, seleccionamos el nodo que tiene el grado más grande. Si hay múltiples nodos con el mismo CbCI y grado mayor, rompemos el empate al azar. A continuación, recalcular el CbCI para todos los nodos restantes, quitar el nodo con el mayor CbCI, y repetir el mismo procedimiento hasta que el tamaño de la LCC se convierte en igual o inferior a 0,01N. Optimizamos además el orden obtenido de eliminación de nodos por reinserción, como en el algoritmo CI. Utilizamos la red de grano grueso, no la red original, para informar al proceso de reinserción en el algoritmo CbCI. En otras palabras, el número de comunidades que pertenecen al mismo componente que el nodo reinsertado se mide para cada nodo tentativamente reinsertado. Decidimos reinsertar el nodo cuya presencia conecta el menor número de comunidades (Fig. 1 (c)).
Dada una partición de la red en comunidades, el cálculo de CbCI (i) para un nodo consume O (1) tiempo. Por lo tanto, si adaptamos la implementación original del algoritmo CI9 al caso del CbCI, la clasificación de CbCl (i) domina el tiempo de cálculo del algoritmo CbCI. La complejidad temporal del algoritmo CbCI es la misma que la del algoritmo CI en ref. 9, es decir, O (N2 logN), si la detección de la comunidad no es un cuello de botella. El uso de la estructura de datos de heap máximo hace que el algoritmo CbCI se ejecute en tiempo O (N logN) si
NC = O(N) tal que los valores CbCI de los nudos O (1) se ven afectados por la eliminación de un solo nodo. En general, el algoritmo CbCI con la estructura de datos de heap máximo se ejecuta en tiempo
O(N logN) × O(N/NC) = O((N2/NC)logN).
Utilizamos los siguientes seis algoritmos para la detección de la comunidad: (i) Infomap27,28, que requieren O (M) time21, donde M es el número de enlaces, y por tanto O (N) tiempo para las redes escasas; (Ii) Walktrap, que requiere
O(N2logN) para la mayoría de las redes empíricas29; (Iii) el algoritmo de propagación de etiquetas, que requiere tiempo casi lineal en N ref. 30; (Iv) un algoritmo rápido codicioso para la maximización de la modularidad, que requiere
O(N(logN)2) tiempo para las redes escasas31; (V) la maximización de la modularidad basada en el recocido simulado, que es práctico hasta ≈104 nodos en el documento original32 y que consume mucho tiempo porque la modularidad debe maximizarse dependiendo del parámetro33; (Vi) el algoritmo de Lovaina, que prácticamente se ejecuta en tiempo O (N )34. Los tres últimos algoritmos pretenden maximizar la modularidad, denotada por Q. Los tres primeros algoritmos detectan las comunidades de acuerdo con diferentes criterios.
Excepto para el algoritmo de recocido simulado, el coste computacional es como máximo para el algoritmo CbCI dada la partición de la red, es decir,
O(N2 logN). Por lo tanto, si el algoritmo CbCI es ingenuamente implementado, la detección de la comunidad no es un cuello de botella en términos del tiempo de cálculo cuando se utiliza cualquiera de estos cinco algoritmos de detección de la comunidad. Si NC = O (N) e implementamos el algoritmo CbCI utilizando la estructura de datos de heap máximo, un algoritmo de detección de comunidad que requiere más tiempo que O (N logN) presenta un cuello de botella. En este caso, el Infomap cuando la red es escasa (es decir, M = O (N)), el algoritmo de propagación de la etiqueta y el algoritmo de Louvain conservan el tiempo de cálculo total de O (N logN) del algoritmo CbCI. El tiempo de cálculo total con cualquiera de los otros tres algoritmos de detección de comunidad se rige por el algoritmo de detección de la comunidad.
Resultados
En esta sección, comparamos el rendimiento del algoritmo CbCI con el IC y otros algoritmos de inmunización (ver Métodos) en dos redes modelo y 12 redes empíricas. Sea q la fracción de nodos eliminados. El tamaño de la LCC después de
qN nodos se han eliminado, dividido por N, se denotan por
G(q).
Modelos de red sin escala con y sin estructura comunitaria
Empezamos por probar diversos algoritmos de inmunización en un modelo de red sin escala con estructura de comunidad integrada (Métodos). Eliminamos secuencialmente nodos de esta red de acuerdo con cada algoritmo de inmunización y seguimos el tamaño de la LCC. Utilizamos la estructura de la comunidad impuesta por el modelo para informar a los algoritmos CbCI y CbDI. Los resultados para una gama de algoritmos de inmunización se muestran en la Fig. 2 (a). Los algoritmos CbCI y CbDI superan considerablemente el algoritmo CI. El algoritmo CbCI funciona mejor que el algoritmo CbDI. El rendimiento del algoritmo CbCI está cerca del algoritmo Betweenness. Cabe señalar que el algoritmo Betweenness, aunque eficiente, no es escalable a redes más grandes.
Figura 2: Tamaño normalizado de la LCC, G (q), trazado contra la fracción de nodos eliminados, q, en redes de modelos con N = 5000.
Una curva corresponde a un algoritmo de inmunización. Véase Métodos para las abreviaturas. (A) Red libre de escala con la estructura comunitaria predefinida. (B) Modelo BA.
A continuación, consideramos una red sin escala sin estructura comunitaria, que es generada por el modelo BA original con N = 5000 y <k> ≈ 12 (los parámetros del modelo son iguales a m0 = m = 6). Ejecutamos las estrategias CbCI y CbDI aplicando un algoritmo de detección de comunidades a la red generada, aunque el modelo de BA carece de estructura comunitaria. De hecho, todos menos el algoritmo de propagación de etiquetas devuelve un resultado de particionamiento. El rendimiento de los diferentes algoritmos de inmunización para esta red se compara en la Fig. 2 (b). El algoritmo CbCI combinado con Infomap o Walktrap supera los algoritmos de Grado y LSP. El rendimiento del algoritmo CbCI es cercano a la del algoritmo CI excepto en una etapa temprana de la eliminación del nodo. Un algoritmo de inmunización basado en la comunidad diferente, CbDI, carece de esta característica. Este resultado sugiere que el algoritmo CbCI combinado con Infomap o Walktrap puede funcionar eficientemente incluso cuando la red no tiene estructura comunitaria.
Los resultados de los algoritmos CbCI y CbDI combinados con los otros cuatro algoritmos de detección de la comunidad se muestran en la Fig. S2 (a). La cifra sugiere que el algoritmo CbCI combinado con Infomap o Walktrap funciona mejor que cuando se combina con un algoritmo de detección de comunidad diferente.
Redes empíricas
En esta sección, ejecutamos el CbCI y otros algoritmos en las siguientes 12 redes empíricas con la estructura de la comunidad. (I) Dos redes de Sistemas Autónomos de Internet construidas por el Proyecto de Vistas de Ruta de la Universidad de Oregón35,36,37: Un nodo es un Sistema Autónomo. La red recogida el 2 de enero de 2000 y la 31 de marzo de 2001 se denominan AS-1 y AS-2, respectivamente. (Ii) Red de privacidad bastante buena (PGP) 38: Dos personas están conectadas por un enlace si comparten información confidencial utilizando el algoritmo de cifrado PGP en Internet. (Iii) World Wide Web (WWW) 39: Una red de sitios web conectados por hipervínculos, que originalmente es una red dirigida. (Iv) Red de comunicación basada en el correo electrónico en la Universidad de Kiel (denominada e-mail-uni) 40: Actividad de envío de correo electrónico entre los estudiantes, que proporciona un enlace dirigido, registrado durante un período de 112 días. (V) Red de comunicación basada en correo electrónico en Enron Corporation (correo electrónico-Enron) 36,41,42: Dos usuarios de correo electrónico en el conjunto de datos están conectados por un enlace directo no ponderado si al menos un correo electrónico ha sido enviado desde un Usuario al otro usuario. Vi) Redes de colaboración en las categorías de Relatividad General y Cosmología Cuántica (CA-GrQc), Astro Física (CA-Astroph) y Condensed Matter (CA-Condmat )36,43 y Física de Energía Elevada - Fenomenología (CA-HepPh) y Física de alta energía - Teoría (CA-HepTh) categorías en arXiv35,36. Por definición, dos autores son adyacentes si coautorizan un trabajo. Vii) Red de citas de física de alta energía dentro de la categoría hep-th de arXiv (HEP) 44, que originalmente es una red dirigida. Para cada red, eliminamos el peso del enlace, los auto-bucles y la dirección del enlace, y sometimos el LCC al siguiente análisis. Las estadísticas resumidas de estas redes, incluyendo la modularidad, Q, se muestran en las Tablas S1 y S2.
No investigamos el algoritmo de inmunización de Betweenness debido a su alto costo computacional (es decir, el tiempo O (NM) para calcular la centralidad intermedia de todos los nodos24, por lo tanto el tiempo O (N2M) para eliminar los nódulos O (N)).
El rendimiento de los diferentes algoritmos de inmunización se compara en dos redes empíricas en la Fig. 3. Entre las 12 redes empíricas que probamos, estas dos redes produjeron los valores de modularidad más pequeños y más grandes maximizados por el algoritmo de Louvain. La figura indica que el algoritmo CbCI combinado con Infomap o Walktrap funciona mejor que los algoritmos propuestos anteriormente incluyendo el algoritmo CI en ambas redes. El algoritmo CbCI funciona mejor que el algoritmo CI en muchas otras redes empíricas también (Fig. S2 (b) - (m)). Además, el algoritmo CbCI combinado con un algoritmo de detección de comunidad diferente también supera el algoritmo CI en la mayoría de las redes (Fig. S2 (b) - (m)).
Figura 3: Tamaño normalizado del LCC, G (q), trazado contra la fracción de nodos eliminados, q, en dos redes empíricas.
(a) Red de comunicaciones por correo electrónico en Enron. (b) World Wide Web.
Para ser cuantitativos, se mide la fracción de nodos eliminados en la que la red fragmentos en suficientemente pequeños componentes conectados, es decir,
Donde recordamos que
G(q) es el tamaño de la LCC normalizada por N. Se establece
θ = 0.05. Calculamos
qc para cada combinación de una red y un algoritmo de inmunización.
El valor de
qc para cada algoritmo de inmunización normalizado por el valor qc para el algoritmo CI se representa en la Fig. 4. Un símbolo representa una red. Un pequeño valor normalizado de qc implica una alta eficiencia del algoritmo de inmunización. Como era de esperar, el algoritmo de inmunización de Grado funciona peor que el CI en todas las redes probadas (Fig. 4 (c)). Para el algoritmo CbCI combinado con Infomap, qc es menor en un 15,0% a 49,7% que en el algoritmo CI (Fig. 4 (a)). El algoritmo CbCI combinado con Walktrap muestra un rendimiento similar para todas las redes excepto una (Fig. 4 (b)). El algoritmo CbCI combinado con tres de los otros cuatro algoritmos de detección de la comunidad tiene mejores resultados que el algoritmo CI para redes con una estructura comunitaria relativamente fuerte (Figura S3). El algoritmo CbDI combinado con Infomap funciona mejor que el algoritmo CI para todas las redes, pero en menor medida que el algoritmo CbCI combinado con Infomap (Fig. 4 (d)). El algoritmo CbDI combinado con Walktrap (Fig. 4 (e)) y los otros cuatro algoritmos de detección de la comunidad (Fig. S3) es peor que el algoritmo CI. El algoritmo LSP es peor que el algoritmo CI en la mayoría de las redes (Fig. 4 (f)).
Figura 4: La fracción de nodos eliminados para fragmentar la red, qc, para un algoritmo de inmunización dividido por el valor para el algoritmo CI.
(a) CbCI combinado con Infomap. (b) CbCI combinado con Walktrap. (c) Alto grado de adaptación (Grado). (d) CbDI combinado con Infomap. (e) CbDI combinado con Walktrap. (f) Partición espectral laplaciana (LSP). Un símbolo representa una red. La cruz representa la red modelo usada en la Fig. 2 (a). El valor de modularidad, Q, viene determinado por el algoritmo de Louvain.
Incluso si dos algoritmos de inmunización producen el mismo valor
qc en la misma red, G (q) puede caer considerablemente a un valor q más pequeño con un algoritmo de inmunización que el otro algoritmo. Para cuantificar el rendimiento de los algoritmos de inmunización en este sentido, se mide el tamaño de la LCC integrada a lo largo de valores q 7,45, es decir,
Debe tenerse en cuenta que es el área bajo la curva cuando
G(q) se traza contra q y oscila entre 0 y 1/2. Un valor pequeño implica un buen desempeño de un algoritmo de inmunización.
El valor de
para cada algoritmo de inmunización normalizado por el del algoritmo de CI se representa en la Fig. 5. El algoritmo CbCI combinado con Infomap supera el algoritmo CI en 11 de las 12 redes en términos de
(Fig. 5 (a)). Del mismo modo, el algoritmo CbCI combinado con Walktrap supera el algoritmo CI en diez de las 12 redes (Fig. 5 (b)). El CbCI combinado con cualquiera de los otros cuatro algoritmos de detección de la comunidad supera el algoritmo CI en aproximadamente la mitad de las redes y tiende a ser eficiente para redes que tienen grandes valores de modularidad según lo determinado por el algoritmo de Louvain (Figura S4). En particular, para las tres redes con la mayor modularidad, el algoritmo CbCI combinado con cualquiera de los seis algoritmos de detección de la comunidad supera el algoritmo CI. Los algoritmos de Grado, CbDI y LSP son menos eficientes que el algoritmo de CI en términos de
(Fig. 5 (c) - (f) y S4).
Figura 5: El valor normalizado por el algoritmo CI.
(a) CbCI combinado con Infomap. (b) CbCI combinado con Walktrap. (c) Grado. (d) CbDI combinado con Infomap. (e) CbDI combinado con Walktrap. (f) LSP. El valor de Q es determinado por el algoritmo de Louvain.
¿Por qué Infomap y Walktrap se casan mejor con el algoritmo CbCI que con los otros algoritmos de detección de la comunidad?
Hemos demostrado que el algoritmo CbCI es más eficiente cuando se combina con Infomap o Walktrap, en particular Infomap, que con los otros cuatro algoritmos de detección de la comunidad. Para explorar por qué, empezamos por medir el coeficiente de agrupamiento46 de la versión no ponderada de las redes de grano grueso. Lo hacemos porque en teoría la IC asume redes locales parecidas a árboles9,47. Alto agrupamiento en la red de grano grueso puede desalentar el algoritmo CbCI. Para cada red empírica, se mide el coeficiente de correlación de Pearson entre el coeficiente de agrupamiento y qc normalizado por el valor para el algoritmo CI. Utilizamos el resultado para cada algoritmo de detección de la comunidad como un punto de datos tal que el coeficiente de correlación se calcula sobre la base de seis puntos de datos. Los resultados se muestran en la Tabla 1. Encontramos que el coeficiente de agrupamiento no está correlacionado consistentemente con el qc normalizado. Los resultados son cualitativamente iguales con un coeficiente de agrupamiento ponderado48,49 (Tabla 1). Obtenemos resultados similares si en lugar de qc se utiliza como medida de rendimiento (Tabla 2). Cabe señalar que diferentes algoritmos de detección de la comunidad producen valores de coeficientes de agrupamiento suficientemente diferentes, incluyendo valores grandes (Fig. S5 (a)). Llegamos a la conclusión de que la falta de locales árbol-como la estructura en las redes de grano grueso no es un fuerte determinante de la realización del algoritmo CbCI. Este resultado no contradice los del algoritmo CI original, que asume redes similares a las de un árbol, ya que el algoritmo CI es prácticamente eficiente en las redes con autoenlaces 9.
Hemos establecido
, ignorando así la contribución de los nodos en las redes de grano grueso tres o más saltos lejos de un nodo focal. De hecho, las grandes redes de grano grueso pueden tener una gran longitud de trayectoria media y deteriorar el rendimiento del algoritmo CbCI. Por lo tanto, calcular el coeficiente de correlación entre
NC, es decir, el número de las comunidades detectadas, y
qC, y entre la longitud de la ruta media en la red de grano grueso no ponderado y
qC (Tabla 1]. La correlación eficiente entre
y
NC o la longitud media de la trayectoria también se mide (Tabla 2]. Las tablas indican que el rendimiento de un algoritmo de detección de la comunidad no está correlacionada de forma consistente con la longitud del camino promedio. Se correlaciona con NC, pero de tal manera que el rendimiento del algoritmo CbCI mejora a medida que aumenta NC, contrariamente al mecanismo postulado anteriormente mencionado. Por lo tanto, el uso de
probablemente no explica la razón por la cual un algoritmo de detección de la comunidad se casa con el algoritmo CbCI mejor que otro.
De hecho, el algoritmo CbCI funciona bien cuando las comunidades detectadas tienen tamaños relativamente similares. Para demostrar esto, medimos la entropía en la partición, que se define por, donde está el número de nodos en la comunidad cth. La entropía oscila entre 0 y logNC. Un valor de entropía grande implica que la partición de la red es relativamente igualitaria. El coeficiente de correlación entre la entropía y el qc normalizado se muestra en la Tabla 1 para cada red. La entropía y qc están negativamente correlacionados entre sí para todas las redes y fuertemente para la mayoría de las redes. Este resultado es robusto cuando normalizamos la entropía por el mayor valor posible, es decir, logNC (Tabla 1), y cuando la medida de rendimiento se sustituye por (Tabla 2).
Para evaluar la robustez de este hallazgo, se calcula el mismo coeficiente de correlación entre la entropía no normalizada o normalizada y una de las dos medidas de rendimiento, pero para cada algoritmo de detección de la comunidad. Ahora cada red empírica constituye un punto de datos basado en el cual se calcula el coeficiente de correlación. Los valores de los coeficientes de correlación se muestran en la Tabla 3. Aunque la correlación es más débil que en el caso anterior, la correlación entre la entropía y el qC normalizado o es en gran medida negativa, lo cual es consistente con los resultados mostrados en las Tablas 1 y 2. Coeficiente de correlación entre Q y cada uno de la medida de rendimiento se muestra también en la Tabla 3. La entropía proporciona un factor más débil del rendimiento en comparación con Q, lo que se espera porque el algoritmo CbCI está diseñado para redes con estructura comunitaria. Sin embargo, la entropía proporciona un valor de correlación más grande (es decir, más negativo) que Q en algunos casos (Tabla 3).
Infomap tiende a detectar un gran número de comunidades (Tabla S2) cuyo tamaño es menos heterogéneamente distribuido que el caso de los otros algoritmos de detección de la comunidad (Fig. S5 (i) y (k)). Consideramos que esta es la razón principal por la que Infomap es eficaz cuando se combina con el algoritmo CbCI. A grandes rasgos, el algoritmo de propagación de etiquetas tiende a producir un número similar de comunidades, NC (Tabla S2). Sin embargo, el tamaño de la comunidad está más heterogéneamente distribuido con el algoritmo de propagación de etiquetas que con Infomap, cuantificado por las medidas de entropía (Fig. S5 (i) y (k)).
Discusión
Hemos demostrado que el algoritmo de inmunización CbCI supera a la CI y algunos otros algoritmos cuando una determinada red tiene la estructura de la comunidad. El algoritmo tiene como objetivo señalar los nodos que conectan a diferentes comunidades a un costo computacional razonable. El algoritmo CbCI es particularmente eficaz cuando Infomap27,28 se utiliza para detectar comunidades previamente. Infomap se ejecuta suficientemente rápido al menos para las redes escasas21 de tal manera que todo el algoritmo CbCI se ejecute tan rápido como el algoritmo CI al menos asintóticamente en términos del tamaño de la red. El algoritmo de detección de la comunidad de Walktrap29 es el segundo mejor entre los seis candidatos que se combinan con el algoritmo CbCI en términos de la calidad de la inmunización. Sin embargo, Walktrap es más lento que Infomap. Walktrap consume más tiempo que la parte principal del algoritmo CbCI, es decir, eliminación de nodos secuenciales, cuando se utiliza la estructura de datos de heap máximo para implementar el algoritmo CbCI. En este caso, la detección de la comunidad antes de iniciar la eliminación del nodo es el cuello de botella de todo el algoritmo CbCI, y el algoritmo CbCI es más lento que el algoritmo CI. Para nuestros esfuerzos numéricos, recomendamos que Infomap se combine con el algoritmo CbCI.
Argumentamos que Infomap funciona mejor en combinación con el algoritmo CbCI que los otros algoritmos de detección de la comunidad lo hacen principalmente porque Infomap produce una distribución relativamente igualitaria del tamaño de la comunidad. Sin embargo, la distribución del tamaño de la comunidad suele ser sesgada incluso con Infomap50. El algoritmo CbCI puede funcionar aún mejor si usamos un algoritmo de detección de comunidad que impone que las comunidades detectadas sean de igual o similar tamaño. Este problema se conoce como k-equilibrado de partición, donde k se refiere al número de comunidades. Aunque k-equilibrado partición de k general es notoriamente difícil de resolver, hay varios algoritmos aproximados para este problema51,52,53. La combinación de estos algoritmos con el algoritmo CbCI puede ser rentable.
Se particionó la red sólo una vez en el inicio del algoritmo CbCI y se utilizó la estructura de la comunidad obtenida a lo largo del procedimiento de eliminación de nodos. Esta propiedad es compartida por el algoritmo CbDI5 y otro algoritmo de inmunización11. Podemos ser capaces de mejorar el desempeño de la inmunización mediante la actualización de la estructura de la comunidad durante la eliminación del nodo. Nuestras simulaciones numéricas preliminares no produjeron una mejora del algoritmo CbCI con actualización en línea de la estructura de la comunidad (sección S1 en el SI). También debemos tener en cuenta el coste computacional de la detección de la comunidad, que se aplicaría repetidamente en el caso de la actualización en línea. Sin embargo, esta línea de mejora puede valer la pena investigar.
El CI supone localmente árbol-como redes9. Aunque el algoritmo CI es prácticamente eficiente en redes moderadamente loopy9, muchas redes empíricas son abundantes en triángulos y ciclos cortos de tal manera que son altamente loopy1. La conectividad densa dentro de una comunidad implica que tienden a haber muchos triángulos y ciclos cortos en una red con estructura comunitaria54,55. Entonces, grano grueso coalesce eficazmente muchos triángulos y ciclos cortos en un supernodo, posiblemente suprimiendo sus efectos perjudiciales. Al mismo tiempo, sin embargo, las redes de grano grueso tienden a tener un gran coeficiente de agrupamiento (Fig. S5 (a)). Podemos ser capaces de mejorar el rendimiento del algoritmo CbCI mediante la supresión del efecto de los ciclos cortos en las redes de grano grueso. Recientemente, se ha propuesto un método para mejorar la precisión de la estimación del umbral de percolación utilizando matrices sin retroceso, donde se suprimen los caminos redundantes en el recuento de las trayectorias47. Este método aplicado a los algoritmos CI y CbCI puede mejorar su rendimiento en el problema de la inmunización.
El algoritmo de propagación de influencia colectiva (CIp) propuesto recientemente, que puede interpretarse como el algoritmo CI en el límite de, generalmente produce mejores soluciones que el algoritmo de CI25. Dado que no hemos implementado el algoritmo CIp en el presente artículo, no estamos argumentando que el algoritmo CbCI es mejor que el algoritmo CIp. También debe señalarse que es posible que podamos combinar el algoritmo CbCI con la idea del algoritmo CIp (es decir, utilizando los principales vectores izquierdo y derecho de la matriz que no retrocede) para diseñar un nuevo algoritmo.
Referencias
1. Newman, M. E. J. Networks — An Introduction. Oxford University Press, Oxford (2010).
2. Altarelli, F., Braunstein, A., Dall’Asta, L., Wakeling, J. R. & Zecchina, R. Containing epidemic outbreaks by message-passing techniques. Phys. Rev. X 4, 021024 (2014).
3. Restrepo, J. G., Ott, E. & Hunt, B. R. Weighted percolation on directed networks. Phys. Rev. Lett. 100, 058701 (2008).
CAS PubMed Article
4. Chen, Y., Paul, G., Havlin, S., Liljeros, F. & Stanley, H. E. Finding a better immunization strategy. Phys. Rev. Lett. 101, 058701 (2008).
CAS PubMed Article
5. Masuda, N. Immunization of networks with community structure. New J. Phys. 11, 123018 (2009).
Article
6. Salathé, M. & Jones, J. H. Dynamics and control of diseases in networks with community structure. PLOS Comput. Biol. 6, e1000736 (2010).
CAS PubMed Article
7. Schneider, C. M., Mihaljev, T., Havlin, S. & Herrmann, H. J.Suppressing epidemics with a limited amount of immunization units. Phys. Rev. E 84, 061911 (2011).
CAS Article
8. Zhao, D. et al. Immunization of epidemics in multiplex networks. PLOS ONE 9, e112018 (2014).
PubMed Article
9. Morone, F. & Makse, H. A. Influence maximization in complex networks through optimal percolation. Nature 524, 65–68 (2015).
CAS PubMed Article
10. Zahedi, R. & Khansari, M. A new immunization algorithm based on spectral properties for complex networks. In The 7th Conference on Information and Knowledge Technology (IKT), 1–5 (2015).
11. Requião da Cunha, B., González-Avella, J. C. & Gonçalves, S. Fast fragmentation of networks using module-based attacks. PLOS ONE 10, e0142824 (2015).
Article
12. Mugisha, S. & Zhou, H.-J. Identifying optimal targets of network attack by belief propagation. Phys. Rev. E 94, 012305 (2016).
CAS
Article
13. Cohen, R., Havlin, S. & ben-Avraham, D. Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett.91, 247901 (2003).
CAS PubMed Article
14. Gallos, L. K., Liljeros, F., Argyrakis, P., Bunde, A. & Havlin, S.Improving immunization strategies. Phys. Rev. E 75, 045104(R) (2007).
CAS Article
15. Gong, K. et al. An efficient immunization strategy for community networks. PLOS ONE 8, e83489 (2013).
Article
16. Hébert-Dufresne, L., Allard, A., Young, J.-G. & Dubé, L. J. Global efficiency of local immunization on complex networks. Sci. Rep. 3, 2171 (2013).
PubMed Article
17. Liu, Y., Deng, Y. & Wei, B. Local immunization strategy based on the scores of nodes. Chaos 26, 013106 (2016).
Article
18. Albert, R., Jeong, H. & Barabási, A.-L. Error and attack tolerance of complex networks. Nature 406, 378–382 (2000).
ISI CAS PubMed Article
19. Callaway, D. S., Newman, M. E. J., Strogatz, S. H. & Watts, D. J.Network robustness and fragility: Percolation on random graphs. Phys. Rev. Lett. 85, 5468–5471 (2000).
ISI CAS PubMed Article
20. Cohen, R., Erez, K., ben-Avraham, D. & Havlin, S. Breakdown of the internet under intentional attack. Phys. Rev. Lett. 86, 3682–3685 (2001).
ISI CAS PubMed Article
21. Fortunato, S. Community detection in graphs. Phys. Rep. 486, 75–174 (2010).
Article
22. Holme, P., Kim, B. J., Yoon, C. N. & Han, S. K. Attack vulnerability of complex networks. Phys Rev. E 65, 056109 (2002).
CAS Article
23. Ueno, T. & Masuda, N. Controlling nosocomial infection based on structure of hospital social networks. J. Theor. Biol. 254, 655–666 (2008).
Article
24. Brandes, U. A faster algorithm for betweenness centrality. J. Math. Sociol. 25, 163–177 (2001).
ISI Article
25. Morone, F., Min, B., Bo, L., Mari, R. & Makse, H. A. Collective influence algorithm to find influencers via optimal percolation in massively large social media. Sci. Rep. 6, 30062 (2016).
PubMed Article
26. Karrer, B., Newman, M. E. J. & Zdeborová, L. Percolation on sparse networks. Phys. Rev. Lett. 113, 208702 (2014).
CAS PubMed Article
27. Rosvall, M. & Bergstrom, C. T. Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. USA105, 1118–1123 (2008).
PubMed Article
28. Rosvall, M., Axelsson, D. & Bergstrom, C. T. The map equation. Eur. Phys. J. Spec. Top. 178, 13–23 (2010).
Article
29. Pons, P. & Latapy, M. Computing communities in large networks using random walks. In Computer and Information Sciences-ISCIS 2005, Yolum, P., Güngör, T., Gürgen, F. & Özturan, C. editors, volume 3733 of Lecture Notes in Computer Science, 284–293. Springer Berlin Heidelberg (2005).
30. Raghavan, U. N., Albert, R. & Kumara, S. Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76, 036106 (2007).
CAS Article
31. Clauset, A., Newman, M. E. J. & Moore, C. Finding community structure in very large networks. Phys. Rev. E 70, 066111 (2004).
CAS Article
32. Sales-Pardo, M., Guimerá, R., Moreira, A. A. & Amaral, L. A. N.Extracting the hierarchical organization of complex systems. Proc. Natl. Acad. Sci. USA 104, 15224–15229 (2007).
PubMed
Article
33. Lancichinetti, A. & Fortunato, S. Community detection algorithms: A comparative analysis. Phys. Rev. E 80, 056117 (2009).
CAS Article
34. Blondel, V. D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. Fast unfolding of communities in large networks. J. Stat. Mech. 2008, P10008 (2008).
Article
35. Leskovec, J., Kleinberg, J. & Faloutsos, C. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 177–187. ACM (2005).
36. Jure, L. & Andrej, K. Stanford Network Analysis Project.
http://snap.stanford.edu/. (Date of access: 19/01/2016).
37. University of Oregon Route Views Project.
http://www.routeviews.org. (Date of access: 19/01/2016).
38. Boguñá, M., Pastor-Satorras, R., Díaz-Guilera, A. & Arenas, A.Models of social networks based on social distance attachment. Phys. Rev. E 70, 056122 (2004).
CAS Article
39. Albert, R., Jeong, H. & Barabási, A.-L. Internet: Diameter of the world-wide web. Nature 401, 130–131 (1999).
ISI CAS Article
40. Ebel, H., Mielsch, L. I. & Bornholdt, S. Scale-free topology of e-mail networks. Phys. Rev. E 66, 035103(R) (2002).
CAS Article
41. Klimt, B. & Yang, Y. The enron corpus: A new dataset for email classification research. In Machine Learning: ECML 2004, 217–226, Springer (2004).
42. Leskovec, J., Lang, K. J., Dasgupta, A. & Mahoney, M. W.Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6, 29–123 (2009).
Article
43. Leskovec, J., Kleinberg, J. & Faloutsos, C. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1, 2 (2007).
Article
44. Batagelj, V. & Mrvar, A. Pajeck datasets (2006),
http://vlado.fmf.uni-lj.si/pub/networks/data/. (Data of access: 19/01/2016).
45. Schneider, C. M., Moreira, A. A., Andrade, J. S., Havlin, S. & Herrmann, H. J. Mitigation of malicious attacks on networks. Proc. Natl. Acad. Sci. USA 108, 3838–3841 (2011).
PubMed Article
46. Watts, D. J. & Strogatz, S. H. Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998).
ISI CAS PubMed Article
47. Radicchi, F. & Castellano, C. Beyond the locally treelike approximation for percolation on real networks. Phys. Rev. E 93, 030302(R) (2016).
Article
48. Onnela, J.-P., Saramäki, J., Kertész, J. & Kaski, K. Intensity and coherence of motifs in weighted complex networks. Phys. Rev. E71, 065103 (2005).
CAS Article
49. Saramäki, J., Kivelä, M., Onnela, J.-P., Kaski, K. & Kertész, J.Generalizations of the clustering coefficient to weighted complex networks. Phys. Rev. E 75, 027105 (2007).
Article
50. Lancichinetti, A., Kivelä, M., Saramäki, J. & Fortunato, S.Characterizing the community structure of complex networks. PLOS ONE 5, e11976 (2010).
CAS PubMed Article
51. Andreev, K. & Racke, H. Balanced graph partitioning. Theor. Comp. Sys. 39, 929–939 (2006).
Article
52. Krauthgamer, R., Naor, J. S. & Schwartz, R. Partitioning graphs into balanced components. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ‘09, 942–949 (2009).
53. Feldmann, A. E. & Foschini, L. Balanced partitions of trees and applications. Algorithmica 71, 354–376 (2015).
Article
54. Radicchi, F., Castellano, C., Cecconi, F., Loreto, V. & Parisi, D.Defining and identifying communities in networks. Proc. Natl. Acad. Sci. USA 101, 2658–2663 (2004).
CAS PubMed Article
55. Palla, G., Derényi, I., Farkas, I. & Vicsek, T. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005).
ISI CAS PubMed Article
56. Barabási, A.-L. & Albert, R. Emergence of scaling in random networks. Science 286, 509–512 (1999).
