Detectando influyentes a nivel mesoescópico

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).

Tecnología para atacar las fuentes de desinformación en medios sociales

Desinformación en las redes sociales: ¿Puede la tecnología salvarnos?
The conversation


Compartiendo hashtags de la elección: Los puntos son cuentas de Twitter; Las líneas muestran retweeting; Los puntos más grandes son retweeted más. Los puntos rojos son bots probables; Los azules son probablemente seres humanos. Clayton Davis, CC BY-ND

Autor Filippo Menczer
Profesor de Informática e Informática; Director del Centro de Redes Complejas y Sistemas de Investigación, Universidad de Indiana, Bloomington


Si obtienes tus noticias de las redes sociales, como la mayoría de los estadounidenses, estás expuesto a una dosis diaria de engaños, rumores, teorías conspirativas y noticias engañosas. Cuando todo está mezclado con información confiable de fuentes honestas, la verdad puede ser muy difícil de discernir.

De hecho, el análisis de mi equipo de investigación de datos y seguimiento de rumores de la Universidad de Columbia Emergent sugiere que esta desinformación es tan probable que vaya viral como información confiable.

Muchos están preguntando si este ataque de desinformación digital afectó el resultado de las elecciones estadounidenses de 2016. La verdad es que no sabemos, aunque hay razones para creer que es totalmente posible, sobre la base de análisis anteriores y los recuentos de otros países. Cada pieza de desinformación contribuye a la formación de nuestras opiniones. En general, el daño puede ser muy real: si la gente puede ser engañada para poner en peligro la vida de nuestros hijos, como lo hacen cuando se optan por inmunizaciones, ¿por qué no nuestra democracia?

Como investigador de la propagación de la desinformación a través de los medios de comunicación social, sé que limitar la capacidad de los falsificadores de noticias para vender anuncios, como anunció recientemente Google y Facebook, es un paso en la dirección correcta. Pero no limitará los abusos impulsados ​​por motivos políticos.

Explotación de medios sociales

Hace unos 10 años, mis colegas y yo realizamos un experimento en el que aprendimos que el 72 por ciento de los estudiantes universitarios confiaban en vínculos que parecían originados por amigos, incluso hasta el punto de ingresar información de inicio de sesión personal en sitios de phishing. Esta vulnerabilidad generalizada sugiere otra forma de manipulación maliciosa: La gente también podría creer que la desinformación que reciben al hacer clic en un enlace de un contacto social.

Para explorar esa idea, he creado una página web falsa con noticias aleatorias generadas por computadoras, como "Celebrity X en la cama con Celebrity Y!". Los visitantes del sitio que buscaban un nombre activarían el script para fabricar automáticamente una Historia de la persona. Incluí en el sitio un descargo de responsabilidad, diciendo que el sitio contenía texto sin sentido y "hechos" inventados. También colocé anuncios en la página. Al final del mes, recibí un cheque por correo con los ingresos de los anuncios. Esa era mi prueba: las noticias falsas podían ganar dinero contaminando Internet con falsedades.

Lamentablemente, yo no era el único con esta idea. Diez años más tarde, tenemos una industria de falsas noticias y desinformación digital. Los sitios de Clickbait fabrican bromas para ganar dinero con anuncios, mientras que los llamados sitios hiperpartidistas publican y difunden rumores y teorías de conspiración para influir en la opinión pública.

Esta industria se ve reforzada por lo fácil que es crear bots sociales, cuentas falsas controladas por software que parecen personas reales y por lo tanto pueden tener una influencia real. Investigaciones en mi laboratorio descubrieron muchos ejemplos de falsas campañas populares, también llamadas de astroturfing político.

En respuesta, desarrollamos la herramienta BotOrNot para detectar bots sociales. No es perfecto, pero lo suficientemente preciso como para descubrir campañas de persuasión en los movimientos Brexit y antivax. Usando BotOrNot, nuestros colegas encontraron que una gran parte de la charla en línea sobre las elecciones de 2016 fue generada por bots.



En esta visualización de la propagación del hashtag # SB277 sobre una ley de vacunación de California, los puntos son cuentas de Twitter publicando usando ese hashtag, y las líneas entre ellos muestran retweeting de mensajes hashtagged. Los puntos más grandes son cuentas que se retweeted más. Los puntos rojos son bots probables; Los azules son probablemente seres humanos. Onur Varol, CC BY-ND

Creación de burbujas de información

Los seres humanos somos vulnerables a la manipulación por la desinformación digital gracias a un complejo conjunto de sesgos sociales, cognitivos, económicos y algorítmicos. Algunos de estos han evolucionado por buenas razones: Confiar en las señales de nuestros círculos sociales y rechazar la información que contradice nuestra experiencia nos sirvió bien cuando nuestra especie se adaptó a evadir a los depredadores. Pero en las actuales redes en línea, una conexión de red social con un teórico de la conspiración en el otro lado del planeta no ayuda a informar mis opiniones.

Copiar a nuestros amigos y no seguir a los que tienen diferentes opiniones nos dan cámaras de eco tan polarizadas que los investigadores pueden decir con alta precisión si usted es liberal o conservador por sólo mirar a sus amigos. La estructura de la red es tan densa que cualquier desinformación se extiende casi instantáneamente dentro de un grupo, y así segregada que no llega al otro.

Dentro de nuestra burbuja, estamos expuestos selectivamente a información alineada con nuestras creencias. Ese es un escenario ideal para maximizar el compromiso, pero uno perjudicial para desarrollar un escepticismo saludable. El sesgo de confirmación nos lleva a compartir un titular sin ni siquiera leer el artículo.

Nuestro laboratorio obtuvo una lección personal en esto cuando nuestro propio proyecto de investigación se convirtió en el tema de una campaña de desinformación viciosa en el período previo a las elecciones de mitad de mandato de los Estados Unidos en 2014. Cuando investigamos lo que estaba sucediendo, encontramos falsas noticias sobre nuestra investigación que eran compartidas predominantemente por los usuarios de Twitter dentro de una cámara de eco partidista, una comunidad grande y homogénea de usuarios políticamente activos. Estas personas se apresuraron a retweet e impermeables a debunking información.




En este gráfico de cámaras de eco en la Twittersfera, puntos morados representan a las personas difundir afirmaciones falsas sobre el proyecto de investigación Truthy; Las dos cuentas que trataban de desacreditar la información falsa están en naranja en la extrema izquierda. Giovanni Luca Ciampaglia, CC BY-ND

Inevitabilidad viral 

Nuestra investigación muestra que dada la estructura de nuestras redes sociales y nuestra limitada atención, es inevitable que algunos memes se vuelvan virales, independientemente de su calidad. Incluso si los individuos tienden a compartir información de mayor calidad, la red en su conjunto no es efectiva para discriminar entre información confiable y fabricada. Esto ayuda a explicar todos los engaños virales que observamos en la naturaleza.

La economía de la atención se ocupa del resto: si prestamos atención a un tema determinado, se producirá más información sobre ese tema. Es más barato fabricar información y transmitirla como un hecho que para informar la verdad real. Y la fabricación se puede adaptar a cada grupo: los conservadores leen que el Papa endosó a Trump, los liberales leen que apoyó a Clinton. Él tampoco hizo nada.

Atención a los algoritmos

Dado que no podemos prestar atención a todos los posts de nuestros feeds, los algoritmos determinan lo que vemos y lo que no. Los algoritmos utilizados por las plataformas de medios sociales hoy en día están diseñados para priorizar puestos atractivos - los que es probable que haga clic en, reaccionar y compartir. Pero un análisis reciente encontró que las páginas engañosas intencionalmente consiguieron al menos tanto compartir y reaccionar en línea como noticias reales.

Este sesgo algorítmico hacia el compromiso sobre la verdad refuerza nuestros sesgos sociales y cognitivos. Como resultado, cuando seguimos enlaces compartidos en las redes sociales, tendemos a visitar un conjunto de fuentes más pequeñas y homogéneas que cuando realizamos una búsqueda y visitamos los resultados principales.

La investigación existente demuestra que estar en una cámara de eco puede hacer que las personas sean más crédulas acerca de aceptar rumores no verificados. Pero necesitamos saber mucho más acerca de cómo diferentes personas responden a un solo engaño: algunos lo comparten de inmediato, otros lo comprueban primero.

Estamos simulando una red social para estudiar esta competencia entre compartir y verificación de hechos. Esperamos ayudar a desentrañar evidencias contradictorias sobre cuándo la comprobación de hechos ayuda a evitar que los engaños se propaguen y cuando no. Nuestros resultados preliminares sugieren que cuanto más segregada sea la comunidad de creyentes engañadores, más larga la broma sobrevivirá. Una vez más, no se trata sólo de la estafa sino también de la red.

Muchas personas están tratando de averiguar qué hacer con todo esto. Según el último anuncio de Mark Zuckerberg, los equipos de Facebook están probando opciones potenciales. Y un grupo de estudiantes universitarios ha propuesto una manera de etiquetar simplemente los enlaces compartidos como "verificados" o no.

Algunas soluciones permanecen fuera de alcance, al menos por el momento. Por ejemplo, todavía no podemos enseñar a los sistemas de inteligencia artificial cómo discernir entre la verdad y la falsedad. Pero podemos decir algoritmos de clasificación para dar mayor prioridad a fuentes más confiables.

Estudiar la difusión de noticias falsas

Podemos hacer que nuestra lucha contra las noticias falsas sea más eficiente si comprendemos mejor cómo se propaga la mala información. Si, por ejemplo, los bots son responsables de muchas de las falsedades, podemos centrar la atención en detectarlas. Si, alternativamente, el problema es con las cámaras de eco, tal vez podríamos diseñar sistemas de recomendación que no excluyan puntos de vista diferentes.

Para ello, nuestro laboratorio está construyendo una plataforma llamada Hoaxy para rastrear y visualizar la propagación de reclamos sin verificar y la verificación de hechos correspondiente en las redes sociales. Eso nos dará datos reales, con los que podemos informar a nuestras redes sociales simuladas. Entonces podemos probar posibles enfoques para combatir falsas noticias.

Hoaxy también puede mostrar a la gente lo fácil que es que sus opiniones sean manipuladas por la información en línea - e incluso la probabilidad de que algunos de nosotros compartamos falsedades en línea. Hoaxy se unirá a una serie de herramientas en nuestro Observatorio de Medios Sociales, que permite a cualquiera ver cómo se propagan los memes en Twitter. Vincular herramientas como éstas a los verificadores de hechos humanos y las plataformas de medios sociales podría facilitar la minimización de la duplicación de esfuerzos y apoyarse mutuamente.

Es imprescindible invertir recursos en el estudio de este fenómeno. Necesitamos todas las manos en la cubierta: los científicos de la computación, los científicos sociales, los economistas, los periodistas y los socios de la industria deben trabajar juntos para mantenerse firmes contra la extensión de la desinformación.

Infografía: La vida de un influenciador en Twitter

La Vida de un Influenciador de Twitter [Infografía]

Chiara Di Rago - Social Media Today

Si bien Twitter puede no ser la plataforma de medios sociales más utilizada, sigue siendo uno de los canales más efectivos y relevantes para iniciar la conversación en línea - e incluso puede provocar un movimiento social.

En Webfluential, a menudo doy consejos a los influyentes sobre su valor social y cómo pueden mejorarlo. Mientras trabajaba con estos influenciadores me han hecho una serie de preguntas sobre Twitter, siendo la más común:

• ¿Cómo puedo aumentar mi audiencia?
• ¿Cuánto debo cobrar como influenciador de Twitter?
• ¿Cuántos seguidores necesito para ser considerado influyente?

Teniendo en cuenta el concepto de contenido nutritivo, pensé que sería útil responder a algunas de estas preguntas en forma de un infográfico - compruébalo a continuación.

ARS 101: Redes de co-ocurrencia

Redes de co-ocurrencia 
Wikipedia

Las redes de co-ocurrencia se usan generalmente para proporcionar una visualización gráfica de relaciones potenciales entre personas, organizaciones, conceptos u otras entidades representadas dentro del material escrito. La generación y visualización de redes de co-ocurrencia se ha vuelto práctico con el advenimiento del texto almacenado electrónicamente que es susceptible a la minería de texto.

A modo de definición, las redes de co-ocurrencia son la interconexión colectiva de términos basados ​​en su presencia emparejada dentro de una unidad de texto especificada. Las redes se generan conectando pares de términos usando un conjunto de criterios que definen la co-ocurrencia. Por ejemplo, se puede decir que los términos A y B "co-ocurren" si ambos aparecen en un artículo particular. Otro artículo puede contener términos B y C. Vincular A a B y B a C crea una red de co-ocurrencia de estos tres términos. Las reglas para definir la co-ocurrencia dentro de un corpus de texto se pueden establecer de acuerdo con los criterios deseados. Por ejemplo, un criterio más estricto para la co-ocurrencia puede requerir un par de términos para aparecer en la misma oración.



Una red de co-occurrencia creada con KH Coder

Métodos y desarrollo

Las redes de co-ocurrencia pueden ser creadas para cualquier lista de términos (cualquier diccionario) en relación con cualquier colección de textos (cualquier corpus de texto). Los pares co-occurrentes de términos se pueden llamar "vecinos" y éstos agrupan a menudo en "barrios" basados ​​en sus interconexiones. Los términos individuales pueden tener varios vecinos. Los barrios pueden conectarse entre sí a través de al menos un término individual o pueden permanecer desconectados.

Los términos individuales son, en el contexto de la minería de textos, representados simbólicamente como cadenas de texto. En el mundo real, la entidad identificada por un término normalmente tiene varias representaciones simbólicas. Por tanto, es útil considerar los términos como representados por un símbolo primario y hasta varios símbolos sinónimos alternativos. La ocurrencia de un término individual se establece mediante la búsqueda de cada representación simbólica conocida del término. El proceso puede ser aumentado a través de algoritmos de procesamiento de lenguaje natural (NLP) que interrogan segmentos de texto para posibles alternativas como orden de palabras, espaciado y separación de palabras. La PNL también se puede usar para identificar la estructura de oraciones y categorizar las cadenas de texto de acuerdo con la gramática (por ejemplo, categorizar una cadena de texto como un sustantivo basado en una cadena de texto anterior conocida como un artículo).

La representación gráfica de las redes de co-ocurrencia permite visualizarlas e inferencias sobre las relaciones entre entidades en el dominio representado por el diccionario de términos aplicados al corpus de texto. Una visualización significativa requiere normalmente simplificaciones de la red. Por ejemplo, las redes pueden ser dibujadas de manera que el número de vecinos que se conectan a cada término sea limitado. Los criterios para limitar los vecinos podrían basarse en el número absoluto de co-ocurrencias o criterios más sutiles como la "probabilidad" de co-ocurrencia o la presencia de un término descriptivo intermedio.

Los aspectos cuantitativos de la estructura subyacente de una red de coinoconducción también pueden ser informativos, como el número total de conexiones entre entidades, el agrupamiento de entidades que representan subdominios, la detección de sinónimos [1], etc.

Aplicaciones y uso

Algunas aplicaciones de trabajo del enfoque de co-ocurrencia están disponibles para el público a través de Internet. PubGene es un ejemplo de una aplicación que se ocupa de los intereses de la comunidad biomédica mediante la presentación de redes basadas en la co-ocurrencia de la genética relacionados con los términos que aparecen en los registros de MEDLINE [2] [3] El sitio web NameBase es un ejemplo de cómo las relaciones humanas se pueden inferir mediante el examen de redes construidas a partir de la co-ocurrencia de nombres personales en los periódicos y otros textos (como en Ozgur et al [4]).

Las redes de información también se utilizan para facilitar los esfuerzos para organizar y centrar la información disponible públicamente para fines de aplicación de la ley y de inteligencia (llamada "inteligencia de código abierto" o OSINT). Las técnicas conexas incluyen las redes de co-citación, así como el análisis del hipervínculo y la estructura del contenido en Internet (como en el análisis de sitios web relacionados con el terrorismo [5]).

Véase también

• Takada H, Saito K, Yamada T, Kimura M: “Analysis of Growing Co-occurrence Networks” SIG-KBS (Journal Code:X0831A) 2006, VOL.73rd;NO.;PAGE.117-122 Language;Japanese
• Liu, Chua T-S; “Building semantic perceptron net for topic spotting.” Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, 2001; 378 - 385

Referencias

1. Cohen AM, Hersh WR, Dubay C, Spackman, K: “Using co-occurrence network structure to extract synonymous gene and protein names from MEDLINE abstracts” BMC Bioinformatics 2005, 6:103
2. Jenssen TK, Laegreid A, Komorowski J, Hovig E: "A literature network of human genes for high-throughput analysis of gene expression. " Nature Genetics, 2001 May; 28(1):21-8. PMID 11326270
3. Grivell L: “Mining the bibliome: searching for a needle in a haystack? New computing tools are needed to effectively scan the growing amount of scientific literature for useful information.” EMBO reports 2001 Mar;3(3):200-3: doi:10.1093/embo-reports/kvf059 PMID 11882534
4. Ozgur A, Cetin B, Bingol H: “Co-occurrence Network of Reuters News” (15 Dec 2007) http://arxiv.org/abs/0712.2491
5. Zhou Y, Reid E, Qin J, Chen H, Lai G: "US Domestic Extremist Groups on the Web: Link and Content Analysis" http://doi.ieeecomputersociety.org/10.1109/MIS.2005.96

Puentes: Árbitros inter escalamiento

Árbitros de escalas: nuevas herramientas teóricas para analizar la capacidad de adaptación

por Henrik Ernstson

La estructura de la red social es importante para la capacidad de adaptación. Una posición clave son los 'intermediarios de escalas' que vinculan a los actores que interactúan con los procesos de los ecosistemas a diferentes escalas ecológicas.

Junto con colegas de la Universidad de Estocolmo, acabamos de publicar un artículo en Ecology and Society llamado:

Scale-crossing brokers and network governance of urban ecosystem services: the case of Stockholm

Henrik Ernstson, Stephan Barthel,Erik Andersson y Sara T. Borgström,Ecology and Society 2010: 15 (4), 28.

El artículo sintetiza estudios empíricos de la gestión ecológica urbana en Estocolmo. Sin embargo, también contribuye a las discusiones teóricas sobre la gobernabilidad adaptativa de los sistemas socio-ecológicos (por ejemplo, el número especial en Global Environmental Change, Folke y otros 2005, Duit y Galaz, 2008). Como tal, el artículo es de interés para estudios en sistemas marinos, forestales y agrícolas.
Aquí les presento algunas ideas teóricas claves. (ver también el blog en Stockholm Resilience Centre.).

Marco para evaluar la capacidad de adaptación - vinculando los procesos ecológicos y la estructura de la red social

El artículo construye un marco teórico que vincula procesos ecológicos a estructuras de redes sociales para evaluar la capacidad de adaptación de la gobernanza de los ecosistemas. En efecto, el artículo empuja las teorizaciones actuales en al menos tres aspectos: 1) complejidad espacial; 2) el papel de la estructura de la red social; y 3) cómo manejar las interacciones entre escalas.

1) Complejidad espacial

Primero, construye un marco para explicar más explícitamente la complejidad espacial (y por lo tanto la complejidad del "recurso" en cuestión). Esto se hace principalmente a través de un enfoque empírico sobre los procesos ecológicos de dispersión de semillas y polinización, que son procesos importantes para la re-generación y resiliencia de los ecosistemas locales en el paisaje urbano fragmentado de Estocolmo.

2)Estructura de red social como variable intermedia

En segundo lugar, el documento "mira" más allá de los actores individuales y sus vínculos directos con otros (a menudo el caso en la literatura sobre, por ejemplo, las "organizaciones puente"). En cambio, los actores que interactúan con los procesos ecológicos se ven incorporados en los patrones de comunicación y relaciones sociales. Esto significa que el documento reconoce la "estructura de la red social" y cómo esta variable intermedia (no individual, no institución) media la agencia de actores individuales, y el desempeño de toda la red para responder al cambio.

Para captar la dinámica social, tomamos la idea de la sociología de que, al igual que los parches ecológicos forman parte de patrones de mayor escala, los actores sociales forman parte de estructuras de redes sociales emergentes que limitan y modelan la dinámica social (Wasserman y Faust, 1994). [...] los patrones de redes sociales son consecuencia de interacciones localizadas entre pares de actores, y ningún actor puede controlar completamente la estructura emergente. [Esto] permite la agencia humana, pero una agencia restringida y mediada a través de la propia estructura de red (Emirbayer y Goodwin, 1994).

3) Interacciones a escala cruzada y árbritros de escalas

En tercer lugar, el documento impulsa la comprensión de lo que significaría para un conjunto de actores identificables para manejar interacciones a escala cruzada en los sistemas socio-ecológicos. Esto se logra a través del desarrollo de un modelo de red de cómo ciertos grupos de actores se involucran en procesos ecológicos a diferentes escalas a través de su práctica social y teorizan una posición clave en la red llamada "arbitraje de cruce" (basándose en la noción de árbitros de Burt)

Por lo tanto, al explicar la estructura de las redes sociales entre los grupos de actores, y cómo se vinculan a las escalas ecológicas, nuestro modelo resultante consiste en grupos de actores que interactúan entre sí y con procesos ecosistémicos en diferentes escalas espaciales y en sitios espacialmente separados [ Figura en la parte superior].

Un último aspecto central de nuestro modelo es la posición en red del intermediario de escalas [que se define] como una posición de red social que vincula a grupos de actores sociales desconectados que, a través de sus prácticas sociales, interactúan con procesos ecosistémicos a diferentes niveles ecológicos ) Y en diferentes sitios físicos.

En relación con la discusión sobre cómo los sistemas de gobernanza pueden hacer frente a cambios lentos por un lado y cambios rápidos por otro, nuestra respuesta indica que debemos buscar esto en la estructura de redes sociales que une a diversos actores a través de escalas. En este sentido, el corredor de escalas se convierte en "un cruce de posibilidades" y podría facilitar la "conmutación" entre los procesos sociales de aprendizaje localizados (en tiempos de lento cambio) y la acción colectiva centralizada (en tiempos de cambio rápido):

Los intermediarios inter-escalas pueden ser vistos como agentes para fomentar la aparición de una estructura de redes sociales determinada y para cambiar entre un modo de acción colectiva centralizada y un modo descentralizado de aprendizaje social entre un conjunto diverso de grupos de actores autónomos locales.

Evaluando los sistemas de gobernanza

Como tal, el agente de cruce de escala se convierte en una lente analítica para utilizar al evaluar sistemas de gobierno empíricos. Las próximas investigaciones deberían, por lo tanto, apuntar a medir hasta qué punto puede encontrar intermediarios de escala en un sistema particular. Otra herramienta de evaluación de este tipo reside en nuestra conceptualización de una escala meso en la gobernanza en forma de "redes verdes a escala de la ciudad" (véase la figura siguiente).

En conclusión, y aparte de sus hallazgos empíricos no abordados en este blog, el documento puede ser visto como aportando nuevas ideas teóricas sobre cómo discutir y analizar la complejidad socio-ecológica y la capacidad de adaptación. Para más información vea el trabajo en sí mismo, el posteo del blog en la Stockholm Resilience Centre, o mi propio blog In Rhizomia.

El artículo es parte de un número especial en Ecology and Society sobre análisis de redes sociales y gestión de recursos naturales.

Fig. 4. La figura demuestra cómo se podría identificar las redes verdes de polinización y dispersión de semillas en una zona particular de Estocolmo (sugerida aquí por el uso de mapas digitales y análisis de redes ecológicas) (véase Andersson y Bodin 2008). Observe cómo ciertas áreas verdes locales son compartidas entre las dos redes verdes de la escala de la ciudad, que dan lugar a la superposición de la red (áreas púrpuras con líneas verticales en negrita en la red verde 2 de la escala de la ciudad). Además, se sugiere que los gerentes de mediana escala puedan asumir la responsabilidad de las redes verdes de escala urbana. En su conjunto, la figura demuestra cómo los servicios ecosistémicos en particular pueden ser vistos como incrustados tanto en el paisaje físico como en las redes sociales de grupos de actores locales (manejo de áreas verdes locales), agentes de escala y agentes municipales a regionales.

Resilience Science

ARS 101: Grafo dividido

Grafo dividido
Wikipedia


Un grafo dividido, dividido en una agrupación y un conjunto independiente.

En la teoría de grafos, una rama de las matemáticas, un grafo dividido es un grafo en el que los vértices se pueden dividir en una agrupación y un conjunto independiente. Los grafos divididos fueron estudiados por primera vez por Földes y Hammer (1977a, 1977b), e introducidos independientemente por Tyshkevich y Chernyak (1979). [1]

Un grafo dividido puede tener más de una partición en una agrupación y un conjunto independiente; Por ejemplo, la trayectoria a-b-c es un grafo dividido, cuyos vértices se pueden dividir en tres formas diferentes:

1. La camarilla {a, b} y el conjunto independiente {c}
2. La camarilla {b, c} y el conjunto independiente {a}
3. La camarilla {b} y el conjunto independiente {a, c}

Los grafos divididos se pueden caracterizar en términos de sus subgrafos inducidos prohibidos: un grafo se divide si y sólo si ningún subgrafo inducido es un ciclo en cuatro o cinco vértices, o un par de enlaces disjuntos (el complemento de un ciclo de 4). 2]

Relación con otras familias de grafos

De la definición, los grafos divididos se clausuran claramente bajo complementación. [3] Otra caracterización de los grafos divididos implica la complementación: son grafos cordales cuyos complementos son también acordales. [4] Del mismo modo que los grafos acordales son los grafos de intersección de los subárboles de los árboles, los grafos divididos son los grafos de intersección de los distintos subestados de los grafos en estrella. Casi todos los grafos acordales son grafos divididos; Es decir, en el límite cuando n va al infinito, la fracción de los grafos acordales de n-vértices que se dividen se aproxima a uno. [6]

Debido a que los grafos acordales son perfectos, también lo son los grafos divididos. Los grafos de doble división, una familia de grafos derivados de grafos divididos, duplicando cada vértice (por lo que la camarilla viene a inducir un antimatching y el conjunto independiente viene a inducir una correspondencia), figura prominentemente como una de las cinco clases básicas de grafos perfectos de los cuales Todos los demás pueden formarse en la prueba de Chudnovsky et al. (2006) del teorema Strong Perfect Graph.

Si un grafo es a la vez un grafo dividido y un grafo de intervalo, entonces su complemento es tanto un grafo dividido como un grafo de comparabilidad, y viceversa. Los grafos divididos de comparabilidad, y por lo tanto también los grafos de intervalo divididos, se pueden caracterizar en términos de un conjunto de tres subgrafos inducidos prohibidos. [7] Los cógrafos divididos son exactamente los gráficos de umbral, y los grafos de permutación dividida son exactamente los grafos de intervalos que tienen complementos de grafos de intervalos. [8] Los grafos divididos tienen el número 2 cocromático.

Problemas Algorítmicos

Sea G un grafo dividido, dividida en un clique C y un conjunto independiente I. Entonces cada camarilla máxima en un grafo dividido es C o la vecindad de un vértice en I. Por lo tanto, es fácil identificar la máxima camarilla , Y complementariamente el conjunto independiente máximo en un grafo dividido. En cualquier grafo dividido, una de las siguientes tres posibilidades debe ser verdadera: [9]

1. Existe un vértice x en I tal que C ∪ {x} es completo. En este caso, C ∪ {x} es una máxima e I es un conjunto máximo independiente.
2. Existe un vértice x en C tal que I ∪ {x} es independiente. En este caso, I ∪ {x} es un conjunto máximo independiente y C es un máximo clique.
3. C es una camarilla máxima e I es un conjunto independiente máximo. En este caso, G tiene una única partición (C, I) en una camarilla y un conjunto independiente, C es la máxima camarilla, e I es el conjunto máximo independiente.

Algunos otros problemas de optimización que son NP-completos en las familias de grafos más generales, incluyendo el grafos coloreados, son similares en los grafos de división. Encontrar un ciclo hamiltoniano sigue siendo NP-completo, incluso para los grafos divididos que son los grafos de cuerdas fuertes. [10] También es bien sabido que el problema del Conjunto Dominador Mínimo sigue siendo NP-completo para los grafos divididos. [11]

Secuencias de grados

Una característica notable de los grafos divididos es que pueden ser reconocidos únicamente a partir de sus secuencias de grados. Sea la sucesión de grados de un grafo G d₁ ≥ d₂ ≥ ... ≥ d_n, y sea m el mayor valor de i tal que d_i ≥ i - 1. Entonces G es un grafo dividido si y solo si



Si este es el caso, entonces los m vértices con los grados más grandes forman una camarilla máxima en G, y los vértices restantes constituyen un conjunto independiente.

Cuenta de grafos divididos

Royle (2000) demostró que las grafos divididos de n-vértices con n están en correspondencia uno a uno con ciertas familias de Sperner. Usando este hecho, determinó una fórmula para el número de grafos (no isomórficos) divididos en n vértices. Para valores pequeños de n, a partir de n = 1, estos números son

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (secuencia A048194 en el OEIS).

Este resultado de enumeración gráfica también fue demostrado antes por Tyshkevich y Chernyak (1990).

Notas

1. Földes & Hammer (1977a) tenían una definición más general, en la que los grafos que llamaron grafos divididos también incluían grafos bipartitos (es decir, grafos que se dividen en dos conjuntos independientes) y los complementos de los grafos bipartitos (es decir, los grafos que se pueden dividir en dos grupos) . Földes & Hammer (1977b) utilizan la definición aquí dada, que se ha seguido en la literatura subsiguiente; Por ejemplo, es Brandstädt, Le & Spinrad (1999), Definition 3.2.3, p.41.
2. Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151.
3. Golumbic (1980), Theorem 6.1, p. 150.
4. Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151; Brandstädt, Le & Spinrad (1999), Theorem 3.2.3, p. 41.
5. McMorris & Shier (1983); Voss (1985); Brandstädt, Le & Spinrad (1999), Theorem 4.4.2, p. 52.
6. Bender, Richmond & Wormald (1985).
7. Földes & Hammer (1977b); Golumbic (1980), Theorem 9.7, page 212.
8. Brandstädt, Le & Spinrad (1999), Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.
9. Hammer & Simeone (1981); Golumbic (1980), Theorem 6.2, p. 150.
10. Müller (1996)
11. Bertossi (1984)
12. Hammer & Simeone (1981); Tyshkevich (1980); Tyshkevich, Melnikow & Kotov (1981); Golumbic (1980), Theorem 6.7 and Corollary 6.8, p. 154; Brandstädt, Le & Spinrad (1999), Theorem 13.3.2, p. 203. Merris (2003) further investigates the degree sequences of split graphs.

Referencias

• Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), "Almost all chordal graphs split", J. Austral. Math. Soc., A, 38 (2): 214–221, doi:10.1017/S1446788700023077, MR 0770128.
• Bertossi, Alan A. (1984), "Dominating sets for split and bipartite graphs", Information Processing Letters, 19: 37–40, doi:10.1016/0020-0190(84)90126-1.
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, doi:10.4007/annals.2006.164.51, MR 2233847.
• Földes, Stéphane; Hammer, Peter Ladislaw (1977a), "Split graphs", Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium, XIX, Winnipeg: Utilitas Math., pp. 311–315, MR 0505860.
• Földes, Stéphane; Hammer, Peter Ladislaw (1977b), "Split graphs having Dilworth number two", Canadian Journal of Mathematics, 29 (3): 666–672, doi:10.4153/CJM-1977-069-1, MR 0463041.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7, MR 0562306.
• Hammer, Peter Ladislaw; Simeone, Bruno (1981), "The splittance of a graph", Combinatorica, 1 (3): 275–284, doi:10.1007/BF02579333, MR 0637832.
• McMorris, F. R.; Shier, D. R. (1983), "Representing chordal graphs on K1,n", Commentationes Mathematicae Universitatis Carolinae, 24: 489–494, MR 0730144.
• Merris, Russell (2003), "Split graphs", European Journal of Combinatorics, 24 (4): 413–430, doi:10.1016/S0195-6698(03)00030-1, MR 1975945.
• Müller, Haiko (1996), "Hamiltonian Circuits in Chordal Bipartite Graphs", Discrete Mathematics, 156: 291–298, doi:10.1016/0012-365x(95)00057-4.
• Royle, Gordon F. (2000), "Counting set covers and split graphs" (PDF), Journal of Integer Sequences, 3 (2): 00.2.6, MR 1778996.
• Tyshkevich, Regina I. (1980), "[The canonical decomposition of a graph]", Doklady Akademii Nauk SSSR (in Russian), 24: 677–679, MR 0587712
• Tyshkevich, Regina I.; Chernyak, A. A. (1979), "Canonical partition of a graph defined by the degrees of its vertices", Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk (en ruso), 5: 14–26, MR 0554162.
• Tyshkevich, Regina I.; Chernyak, A. A. (1990), Еще один метод перечисления непомеченных комбинаторных объектов, Matem. Zametki (in Russian), 48 (6): 98–105, MR 1102626. Translated as "Yet another method of enumerating unmarked combinatorial objects" (1990), Mathematical notes of the Academy of Sciences of the USSR 48 (6): 1239–1245, doi:10.1007/BF01240267.
• Tyshkevich, Regina I.; Melnikow, O. I.; Kotov, V. M. (1981), "On graphs and degree sequences: the canonical decomposition", Kibernetika (in Russian), 6: 5–8, MR 0689420.
• Voss, H.-J. (1985), "Note on a paper of McMorris and Shier", Commentationes Mathematicae Universitatis Carolinae, 26: 319–322, MR 0803929.

Marta Peirano: La inmanente vigilancia de las redes sociales