miércoles, 17 de octubre de 2018

Capital social como estructura social de la corrupción

El capital social predice el riesgo de corrupción en las ciudades 

Johannes Wachs, Taha Yasseri, Balázs Lengyel, János Kertész





La corrupción es una plaga social: las ganancias se acumulan en grupos pequeños, mientras que sus costos son asumidos por todos. Una variación significativa en su nivel entre y dentro de los países sugiere una relación entre la estructura social y la prevalencia de la corrupción, sin embargo, faltan estudios empíricos a gran escala debido a la falta de datos. En este documento relacionamos las características estructurales del capital social de las ciudades con la corrupción en sus gobiernos locales. Al usar conjuntos de datos de Hungría, cuantificamos el riesgo de corrupción mediante la supresión de la competencia y la falta de transparencia en los contratos públicos adjudicados de la ciudad. Caracterizamos el capital social utilizando datos de redes sociales de una plataforma en línea popular. Al controlar los factores sociales, económicos y políticos, encontramos que los asentamientos con redes sociales fragmentadas, que indican un exceso de bonding social capital tienen un mayor riesgo de corrupción y las ciudades con conectividad externa más diversa, lo que sugiere un excedente de bridging social capital está menos expuesto a la corrupción. Interpretamos que la fragmentación fomenta el favoritismo y la conformidad en el grupo, lo que aumenta la corrupción, mientras que la diversidad facilita la imparcialidad en la vida pública y reprime la corrupción.

Cite as: arXiv:1810.05485 [cs.SI]
  (or arXiv:1810.05485v1 [cs.SI] for this version)


domingo, 14 de octubre de 2018

Detectando estructuras centro-periferia en redes por sorpresa

Detectando estructuras núcleo-periféricas por sorpresa

Jeroen van Lidth de Jeude, Guido Caldarelli, Tiziano Squartini

arXiv:1810.04717 [physics.soc-ph]
(or arXiv:1810.04717v1 [physics.soc-ph] for this version)



Detectar la presencia de estructuras de mesoescala en redes complejas es de primordial importancia. Esto es especialmente cierto para las redes financieras, cuya organización estructural afecta profundamente su resiliencia a eventos como las cascadas predeterminadas, la propagación de choques, etc. Hasta ahora, se han propuesto varios métodos para detectar comunidades, es decir, grupos de nodos cuya conectividad es significativamente grande. Sin embargo, las comunidades no representan el único tipo de estructuras de mesoescala que caracterizan las redes del mundo real: otros ejemplos son proporcionados por estructuras de lazo, estructuras centro-periferia y estructuras bipartitas. Aquí proponemos un método novedoso para detectar estructuras bimodulares estadísticamente significativas, es decir, bipartitas o centrales-periféricas. Se basa en una modificación de la sorpresa, recientemente propuesta para la detección de comunidades. Nuestra variante permite que se revelen las particiones de los nodos bimodulares, al permitir que los enlaces se coloquen 1) dentro de la parte central y entre las partes central y periférica o 2) solo entre las capas (vacías) de una red bipartita. Desde un punto de vista técnico, esto se logra empleando una distribución hipergeométrica multinomial en lugar de la hipergeométrica tradicional (binomial); como en el último caso, esto permite asignar un valor p a cualquier (bi) partición dada de los nodos. Para ilustrar el rendimiento de nuestro método, informamos los resultados de su aplicación a varias redes del mundo real, incluidas las sociales, económicas y financieras.



miércoles, 10 de octubre de 2018

Sesgo de discurso mediate análisis de redes de texto

Medición del sesgo del discurso mediante el análisis de red de texto



Dmitry Paranyushkin
http://noduslabs.com
Towards Data Science

En este artículo, propongo un método y una herramienta para medir el nivel de sesgo en el discurso basado en el análisis de red de texto. La medida se basa en la estructura del texto y utiliza parámetros cuantitativos y cualitativos de un gráfico de texto para identificar qué tan sesgado es. Por lo tanto, puede ser utilizado por humanos, así como implementarse en varias API y AI para realizar un análisis de sesgo automático.

Sesgo: lo bueno y lo malo

El sesgo se entiende comúnmente como inclinación o prejuicio hacia un cierto punto de vista. Un discurso o texto que tiene un sesgo puede tener una determinada agenda o promover cierta ideología.

En la era de las "noticias falsas", el surgimiento de ideologías extremas y varias técnicas de desinformación es importante poder identificar el nivel de sesgo en el discurso: ya sean publicaciones en redes sociales, artículos periodísticos o discursos políticos.

El sesgo no es necesariamente algo malo. A veces puede hacer que una intención sea más fuerte, impulsar una agenda, hacer un punto, persuadir, disuadir y transformar. El sesgo es un agente de cambio, sin embargo, cuando hay demasiado de él, el sesgo también puede ser destructivo. Cuando medimos el sesgo medimos qué tan cargado ideológicamente es un texto, cuánto quiere expresar un cierto punto de vista. En algunos contextos, como ficción o discursos políticos muy cargados, un sesgo fuerte puede ser preferencial. En algunos otros contextos, como noticias o no ficción, un fuerte sesgo puede revelar una agenda.

Actualmente no hay herramientas que puedan medir el sesgo de un texto. Varias API de minería de textos clasifican los textos según su contenido y sentimiento, pero no hay instrumentos que puedan medir el nivel de inclinación hacia un cierto punto de vista en el texto. El instrumento y el método propuesto en este artículo pueden servir como el primer paso en esta dirección. La herramienta en línea de código abierto para el análisis de redes de texto que desarrollé ya puede medir el sesgo en función de esta metodología, por lo que le invitamos a probarlo en sus propios textos y ver cómo funciona. A continuación describo cómo funciona el índice de sesgo y algunos detalles técnicos.

La estructura del discurso como red dinámica.


Cualquier discurso puede representarse como una red: las palabras son los nodos y sus coincidencias son las conexiones entre ellos. El gráfico resultante traza las vías de circulación de significado. Podemos hacerlo más legible alineando los grupos de nodos que están más densamente conectados (algoritmo de atlas de fuerza) en los distintos grupos marcados con un color específico. También podemos hacer que los nodos más influyentes sean más grandes en el gráfico (los nodos con la centralidad de alta intermediación). Puede leer más sobre los detalles técnicos en este documento técnico sobre análisis de red de texto.

Por ejemplo, aquí hay una visualización de la charla de TED de Julian Treasure llamada “How to Speak So People Will Want to Listen”, realizada con este método. Si está interesado en ver el gráfico interactivo real, puede abrirlo aquí.





De este grafo podemos ver claramente que los conceptos principales son las nociones de
“people”, “time”, “world”, “listen”, “voice” etc.

Estos conceptos son las uniones para la circulación del significado en ese discurso en particular. Conectan las diferentes comunidades de nodos (designadas por distintos colores).

El algoritmo funciona de una manera que emula la percepción humana (siguiendo el modelo de lectura del paisaje, la idea de cebado semántico y también el sentido común): si las palabras se mencionan con frecuencia en el mismo contexto, formarán una comunidad en el gráfico. Si aparecen en diferentes contextos, se alejarán unos de otros. Si las palabras se usan con frecuencia para conectar diferentes contextos, aparecerán más grandes en el gráfico.

Como resultado, la estructura de un grafo de red de texto puede decirnos mucho sobre la estructura del discurso.

Por ejemplo, si el gráfico tiene una estructura de comunidad pronunciada (varias comunidades de palabras diferentes), el discurso también tiene varios temas distintos, que se expresan en el texto. En nuestro ejemplo tenemos al menos 4 temas principales:

people — listen — speak (dark green)
time —talk —register (light green)
world—sound—powerful (orange)
amazing—voice (pink)

Si analizamos otros textos de la misma manera, veremos que las estructuras gráficas resultantes son diferentes. Por ejemplo, aquí hay una visualización del primer capítulo de Quaran:


Visualización de la red de texto de Quaran realizada con InfraNodus. La estructura del gráfico es menos diversificada y más centralizada. Hay solo unos pocos conceptos principales, el discurso circula alrededor de ellos, el resto del texto apoya los conceptos principales.

Se puede ver que tiene una estructura de red diferente. Es mucho más centralizado y menos diversificado. Hay algunos conceptos principales:

“god”, “people”, “believe”, “lord”, “give”

y todo el discurso circula en torno a estos conceptos. Todas las otras nociones están ahí para apoyar las principales.

Realizamos un análisis similar con los discursos de inauguración de los presidentes de EE. UU. De 1969 a 2013 y visualizamos la forma en que su narrativa cambió con el tiempo:

US Presidential Inauguration Speeches 1969-2013 from Nodus Labs on Vimeo.

Visualización de los discursos de inauguración de los presidentes de los Estados Unidos realizados con InfraNodus (TNA) y Gephi (visualización). Se puede ver que con el tiempo la estructura se mantiene más o menos igual, sin embargo, los discursos de Obama parecen tener términos influyentes más distintos, lo que indica un discurso más diversificado.

Se puede ver que mientras la estructura del discurso se mantuvo más o menos igual a lo largo de los años, mientras que los conceptos enfatizados han cambiado con cada dirección. Esto puede indicar que la estrategia retórica se mantuvo igual, mientras que el contenido se ha transformado con los años. Los discursos de Obama parecen tener un mayor número de nodos influyentes distintos, lo que puede indicar un discurso más diversificado.

El sesgo como un conducto para la ideología en las redes


Ahora que hemos mostrado cómo el discurso se puede representar como una estructura de red, podemos discutir la noción de sesgo en el contexto de la ciencia de redes. Usaremos algunas ideas para la epidemiología para demostrar cómo la topología de la red afecta la velocidad y la propagación de la información a través de los nodos.

Una red se puede ver como una representación de las interacciones que ocurren a lo largo del tiempo, un diagrama de los rastros dejados por un proceso dinámico. Si estudiamos la topología de una red, podemos obtener una gran cantidad de información sobre la naturaleza de los procesos dinámicos que representa.

En el contexto de las ciencias sociales y de la atención médica, la información sobre la estructura de la red puede proporcionar información valiosa para la epidemiología: qué tan rápido se puede propagar una enfermedad (un virus, una opinión o cualquier otra (mala) información), qué tan lejos puede propagarse, qué es lo mejor. Las estrategias inmunológicas pueden ser.

Se ha demostrado (Abramson & Kuperman 2001; PastorSatorras & Vespignani 2001) que a medida que la estructura de una red se vuelve más aleatoria, su umbral epidemiológico disminuye. Las enfermedades, los virus, la desinformación pueden propagarse más rápido y a un mayor número de nodos. En otras palabras, como la estructura de la comunidad de una red es cada vez menos pronunciada y el número de conexiones aumenta, la red propaga información a más nodos y esta propagación se produce en oscilaciones altamente pronunciadas (infectadas / no infectadas).



Una figura del estudio de Abramson y Kuperman (2001) donde se muestra la fracción de elementos infectados (n) en relación con el tiempo (t) para redes con un grado diferente de trastorno (p). Cuanto mayor es el grado de desorden, más elementos se infectan, las oscilaciones se intensifican más y más, pero también el lapso de tiempo de la infección es relativamente corto.

Al mismo tiempo, cuando la estructura de la comunidad se pronuncia mientras la red está relativamente interconectada (red de mundo pequeño), los “bolsillos” de los nodos ayudan a mantener la enfermedad epidémica durante más tiempo en la red. En otras palabras, menos nodos pueden infectarse, pero la infección puede permanecer más tiempo (estado endémico).


Representación de estructuras de red: [a] aleatoria, [b] libre de escala (comunidades mejor pronunciadas) y, [c] jerárquica (menos conectividad global) (de Stocker et al. 2001)

En otro estudio realizado en varias redes sociales (Stocker, Cornforth y Bossomaier 2002) se ha demostrado que las redes jerárquicamente planas (es decir, desordenadas) no son tan estables como las que no tienen escala (es decir, las que tienen una estructura comunitaria más pronunciada ). En otras palabras, las jerarquías pueden ser buenas para pasar las órdenes, pero las estructuras sin escala son mejores para mantener una cosmovisión determinada.

Como podemos ver, no hay una topología de red que pueda considerarse preferencial. De hecho, depende de la intención, el contexto, la situación. En algunos casos, puede ser bueno si una red puede propagar información fácilmente a todos sus elementos relativamente rápido. En algunos otros casos la estabilidad puede ser más preferencial.

En general, la topología de una red refleja qué tan bien puede propagar la información, qué tan susceptible es a las nuevas ideas, si las ideas se apoderarán de toda la red solo durante un breve período de tiempo o permanecerán durante un período más largo.

El mismo enfoque se puede aplicar cuando estudiamos el sesgo. El supuesto aquí es que una red de discurso es una estructura que propaga ideas.

Si la estructura del discurso se centra en unos pocos nodos influyentes y no hay una estructura de comunidad pronunciada, significa que el discurso es bastante homogéneo y las ideas en torno a esos nodos se propagarán mejor que las ideas de la periferia. Designamos dicho discurso como parcializado.

Si, en el otro lado, una red de discurso consta de varias comunidades distintas de palabras / nodos (red de pequeño mundo sin escala) significa que hay varios temas distintos dentro del texto y cada uno de ellos recibe la misma importancia dentro del discurso. . A este discurso lo llamamos diversificado.

Una estructura de comunidad de red se puede identificar no solo de manera cualitativa mediante una visualización gráfica, sino también a través de la medida de modularidad (consulte Blondel et al 2008). Cuanto mayor sea la modularidad (generalmente por encima de 0,4), más pronunciada es la estructura de la comunidad.

Otro criterio importante es la distribución de la influencia (a través de las palabras / nodos más influyentes) en diferentes comunidades. Para que un discurso se diversifique, los nodos más influyentes deben distribuirse entre las diferentes comunidades. Utilizamos la entropía para medir la dispersión de influencia en el gráfico y tener esto en cuenta al identificar el nivel de sesgo. También verificamos si las comunidades principales incluyen un número de nodos desproporcionadamente alto, en cuyo caso el puntaje de diversificación disminuye y el número de componentes en el gráfico.

Por lo tanto, podemos identificar los tres criterios principales que podemos usar para identificar el nivel de sesgo en el discurso:
  • Estructura de la comunidad: cuán distintos son y el% de nodos que pertenecen a las comunidades principales;
  • Distribución de la influencia: cómo los nodos / palabras más influyentes se reparten entre los diferentes temas / comunidades gráficas;
  • Número de componentes del gráfico: cómo está conectado el discurso;

El índice de sesgo basado en la estructura del discurso

Sobre la base de las proposiciones y los criterios anteriores, proponemos el Índice de sesgo que tiene en cuenta la estructura del discurso y tiene cuatro parámetros principales:
  • Dispersado (sin sesgo)
  • Diversificado (sesgado localmente)
  • Enfocado (ligeramente parcial)
  • Sesgado (muy sesgado)

El primer valor, Dispersed, es un discurso que tiene una estructura de comunidad muy pronunciada (varios temas distintos) que no están muy bien conectados o tiene varios componentes (y, por lo tanto, ningún sesgo). Nuestras pruebas muestran que dichos gráficos se producen generalmente para poesía, notas personales, tweets esquizofrénicos y varios otros esfuerzos creativos. Por ejemplo, aquí hay una visualización del poema de Lord Byron "Darkness" (también puede consultar el gráfico interactivo en InfraNodus):


Visualización de la "Darkness" de Lord Byron realizada utilizando InfraNodus. La estructura del discurso se identifica como Dispersada (vea el panel de Análisis a la derecha) debido a la alta modularidad (0.68) y la alta influencia de la dispersión (las palabras más influyentes se difunden entre las diferentes comunidades y solo el 14% de las palabras están en la parte superior comunidad).

Como podemos ver en el gráfico, es bastante escaso visualmente y nuestra herramienta ha identificado la estructura del discurso como Dispersada porque la medida de modularidad es bastante alta (comunidades / temas pronunciados) y los nodos / palabras influyentes se distribuyen bastante equitativamente entre los temas principales (80 % de dispersión y solo el 14% de las palabras en la comunidad / tema superior). Si lees el poema mismo, verás que tiene un vocabulario bastante rico y que evoca muchas imágenes diversas, sin tratar de impulsar una agenda específica (quizás solo a través de medios poéticos, no retóricos).

El siguiente valor, Diversificated, es un discurso que tiene una estructura de comunidad pronunciada pero donde las comunidades están bien conectadas. Por lo general, indica un discurso que refleja varias perspectivas diferentes y les otorga una posición más o menos igual en el nivel global (sesgo local). Muchos artículos y charlas que tienen como objetivo presentar varios puntos de vista, notas de investigación, titulares de periódicos (tomados de una variedad de fuentes) y piezas de no ficción tendrán esta estructura. Por ejemplo, aquí hay una visualización de los titulares de las noticias (con teasers) del 4 de octubre de 2018 (vea la visualización interactiva aquí):


Visualización de los titulares de noticias y teasers (a través de RSS) realizada con InfraNodus para el 4 de octubre de 2018, tomada de NYT, WSJ, FT, The Guardian y Washington Post. Como podemos ver, la selección de noticias se clasifica como Diversificada, ya que la medida de modularidad es relativamente alta y, sin embargo, los temas también están relacionados entre sí. Las palabras más influyentes se reparten entre los principales grupos / comunidades tópicas, lo que indica que la selección de noticias fue bastante diversa.

Podemos ver que la estructura del discurso está clasificada como diversificada, lo que significa que hay varios temas distintos que se desarrollan dentro de este discurso y, sin embargo, están conectados a nivel global.
El tercer valor, Focused, indica un discurso que tiene un sesgo suave hacia un tema determinado. Por lo general, esto significa que el discurso presenta varias perspectivas, pero se enfoca en una sola, y lo desarrolla aún más. Las estructuras del discurso con el puntaje Enfocado son características de los artículos periodísticos, ensayos, informes, que están diseñados para proporcionar una representación clara y concisa de una idea determinada. Por ejemplo, aquí hay una visualización de las tres partes anteriores de este artículo:


Las tres secciones anteriores de este artículo se visualizan como un gráfico de texto utilizando InfraNodus. Podemos ver que la estructura del discurso está clasificada como Enfocada, lo que indica un ligero sesgo. La estructura de la comunidad está presente, pero no son muy distintas. Casi todas las palabras más influyentes se concentran en una comunidad / tema: "red / estructura / discurso" y luego hay un tema más pequeño con "texto / sesgo / medida".

Finalmente, el cuarto tipo de estructura del discurso es parcial, que es característico de los textos que tienen una estructura de comunidad baja o nula. Las ideas principales se concentran juntas y todas las otras nociones utilizadas en el texto están ahí para apoyar la agenda principal. Dicha estructura de discurso generalmente se puede observar en textos altamente ideológicos, discursos políticos y cualquier otro texto, que recurre a la retórica para persuadir a las personas a actuar. Por ejemplo, aquí hay una visualización de El Manifiesto Comunista:


Visualización de red de texto del Manifiesto comunista utilizando InfraNodus. La estructura de la comunidad no se pronuncia y las palabras más influyentes pertenecen a los dos temas principales y están altamente interconectadas. El resto del discurso está subyugado hacia la agenda principal (lucha de clases).

Epílogo

En este artículo, propuse una medida del sesgo del discurso en función de la estructura de la visualización de la red de texto y de varios parámetros que se pueden obtener a partir del análisis gráfico.

Es importante tener en cuenta que no afirmo (todavía) que las proposiciones que hice son científicamente sólidas. Un estudio completo sobre un corpus de datos mucho más grande está en camino (es bienvenido a unirse).

Mi experiencia muestra que este índice puede ser útil al estudiar textos y ya está implementado como una característica de trabajo en la herramienta de visualización y análisis de red de texto InfraNodus.

Por lo tanto, los invito a que lo prueben usted mismo y me envíen cualquier comentario, sugerencia y propuesta que puedan tener. Por favor, siéntase libre de dejar cualquier comentario aquí, estaría muy curioso de ver lo que piensa y cómo podemos desarrollarlo más. InfraNodus es una herramienta de código abierto, por lo que le invitamos a unirse e implementar cualquier propuesta que pueda tener como código.

lunes, 8 de octubre de 2018

Validación cruzada para el número de clusters en una red

Estimación de la validación cruzada del número de clusters en una red
Tatsuro Kawamoto y Yoshiyuki Kabashima
Scientific Reports  7, Número del artículo: 3327 (2017)
Doi: 10.1038 / s41598-017-03623-x


Resumen 
La ciencia de redes investiga metodologías que resumen los datos relacionales para obtener una mejor interpretación. Identificar estructuras modulares es una tarea fundamental, y la evaluación del nivel de grano grueso es su paso crucial. Aquí, proponemos criterios de evaluación principios, escalables y ampliamente aplicables para determinar el número de clusters en redes modulares basadas en la estimación de validación cruzada "leave-one-out" del error de predicción de enlace.

Introducción

Las herramientas matemáticas para el análisis de grafos o de red tienen amplia aplicabilidad en diversas disciplinas de la ciencia. De hecho, muchos conjuntos de datos, por ejemplo, conjuntos de datos biológicos, de información y sociales, representan interacciones o relaciones entre elementos y han sido estudiados con éxito como redes1, 2 utilizando los enfoques del aprendizaje mecánico, la informática y la física estadística. En un sentido amplio, un objetivo principal es identificar las estructuras macroscópicas, incluidas las estructuras temporales, que están ocultas en los datos. Para lograr este objetivo, por ejemplo, las secuencias de grados, la comunidad y las estructuras núcleo-periferia y varias centralidades han sido ampliamente estudiadas. Las estructuras modulares populares son la estructura de la comunidad (estructura asociativa) y la estructura desorganizadora5,6,7,8, aunque cualquier estructura que tenga una ley macroscópica de conectividad puede considerarse Como una estructura modular. El enfoque bayesiano que utiliza el modelo de bloqueo estocástico9, que describiremos más adelante, es una poderosa herramienta para el agrupamiento de grafos. En general, la agrupación de grafos consta de dos pasos: seleccionar el número de clústeres y determinar la asignación de clúster de cada vértice. Estos pasos se pueden realizar repetidamente. Algunos métodos requieren que el número de clústeres sea una entrada, mientras que otros métodos lo determinan automáticamente. El primer paso se llama selección de modelos en marcos estadísticos, y este paso es nuestro enfoque principal.

La selección del número de clusters no es una tarea obvia. Por ejemplo, como se muestra en la Fig. 1, las estructuras más complejas se pueden resolver usando un modelo que permita un mayor número de racimos. Sin embargo, debido a que todo el propósito del agrupamiento de grafos es el grano grueso del grafo, la partición con una resolución excesivamente alta no es deseable. Esta cuestión también está relacionada con el nivel de resolución que se requiere en la práctica. El papel de los marcos y criterios de selección de modelos es sugerir a un posible candidato, o candidatos, para el número de grupos que se van a analizar.


Particiones de la red de libros sobre la política estadounidense. Las asignaciones de clúster deducidas para varios números de entrada de clústeres q. Los vértices con el mismo color pertenecen al mismo grupo. La partición con q grande tiene una mayor resolución y se obtiene ajustando un modelo que tiene una mayor complejidad.

¿Qué marco y criterio utilizar para la selección de modelos y su evaluación es un problema inevitable que enfrentan todos los profesionales, ya que se han propuesto múltiples candidatos en la literatura. Una prescripción clásica es optimizar una función objetivo que define la resistencia de una estructura modular, como la modularidad10, 11 y la ecuación de mapa12, 13; La optimización combinatoria entre todas las posibles particiones produce el número de clústeres y las asignaciones de clúster. Aunque puede parecer que no está relacionado con los marcos estadísticos, debe señalarse que la maximización de la modularidad ha demostrado ser equivalente a la maximización de la probabilidad de un cierto tipo de modelo de bloque estocástico11, 14. También se puede usar el método espectral y contar el número de Valores propios fuera de la banda espectral15,16,17; La razón de esta prescripción es la siguiente: mientras que la banda espectral se deriva de la naturaleza aleatoria de la red, los valores propios aislados y los autovectores correspondientes poseen información estructural distinta sobre la red. Como otro enfoque agnóstico, se ha propuesto recientemente un algoritmo18 que tiene una garantía teórica de la consistencia para el modelo de bloqueo estocástico en régimen escaso con grado medio suficientemente grande; Una red se llama escasa cuando su grado medio se mantiene constante mientras que el tamaño de la red crece al infinito, y típicamente, es localmente árbol-como. Por último, en el marco bayesiano, un principio comúnmente utilizado es seleccionar un modelo que maximice la probabilidad posterior del modelo19,20,21,22,23 o el modelo que tenga la longitud mínima de descripción24,25,26, lo que conduce al Criterio Bayesiano de Información (BIC) -como los criterios.


La minimización del error de predicción es también un principio bien aceptado para la selección del modelo y la validación cruzada lo estima adecuadamente27, 28. Este enfoque se ha aplicado a varios modelos estadísticos, incluidos aquellos modelos que tienen variables ocultas29,30. Las evaluaciones de modelos de validación cruzada para el modelo de bloque estocástico también se consideran en las referencias 31, 32, 33, o bien no son del marco bayesiano o se realizan mediante un enfoque de fuerza bruta. Una ventaja notable de realizar la selección de modelos usando el error de predicción es que no se requiere que el modelo asumido sea consistente con el modelo generativo de los datos reales, mientras que el término de penalización en el BIC se obtiene explícitamente usando la suposición de consistencia del modelo. En este estudio, proponemos una evaluación de modelo de validación cruzada eficiente en el marco bayesiano utilizando el algoritmo basado en la propagación de la creencia (BP).

En general, el error de predicción puede utilizarse como una medida para cuantificar la capacidad de generalización del modelo para datos no observados. En una situación rica en datos, podemos dividir el conjunto de datos en dos partes, el entrenamiento y los conjuntos de prueba, donde el conjunto de entrenamiento se utiliza para aprender los parámetros del modelo y el conjunto de pruebas se utiliza para medir la precisión de predicción del modelo. Realizamos este proceso para modelos que tienen diferentes complejidades, y seleccionamos el modelo que tiene el menor error de predicción o el modelo que es el más parsimonioso si el menor error de predicción es compartido por múltiples modelos. En la práctica, sin embargo, el conjunto de datos es a menudo insuficiente para ser utilizado para llevar a cabo este proceso de forma fiable. La estimación de validación cruzada es una forma de superar esta situación de datos escasos. En la validación cruzada de K-fold, por ejemplo, dividimos aleatoriamente el conjunto de datos en subconjuntos K (> 1), mantenemos uno de ellos como un conjunto de prueba mientras que los restantes se usan como conjuntos de entrenamiento y medimos el error de predicción. Luego cambiamos el papel del conjunto de pruebas al conjunto de entrenamiento, seleccionamos uno de los conjuntos de entrenamiento como un nuevo conjunto de pruebas y medimos de nuevo el error de predicción. Repitamos este proceso hasta que cada subconjunto se utiliza como un conjunto de prueba; Entonces, repetimos todo el proceso para diferentes K-splits aleatorios. El promedio en todos los casos es la estimación final del error de predicción de la complejidad de un modelo dado.

Para un conjunto de datos con N elementos, la N-doble de validación cruzada se llama la licencia-uno-fuera de validación cruzada (LOOCV); En adelante, nos centraremos en este enfoque. Tenga en cuenta que el método de división es único en LOOCV. En el contexto de una red, el conjunto de datos a dividir es el conjunto de aristas y no aristas, y el procedimiento de división de datos se ilustra en la Fig. 2: para cada par de vértices, aprendemos los parámetros mientras utilizamos los datos sin la información de la existencia del enlace entre el par de vértices; Entonces, medimos si podemos predecir correctamente la existencia o no existencia de un enlace. A primera vista, este enfoque parece ser ineficiente y redundante porque realizamos el parámetro aprendiendo N (N - 1) / 2 veces para conjuntos de entrenamiento similares, lo cual es cierto cuando el LOOCV se implementa de una manera directa. Sin embargo, mostramos que tal proceso redundante no es necesario y que el error de predicción se puede estimar eficientemente utilizando un algoritmo basado en BP. Es posible extender la estimación LOOCV que proponemos a la validación cruzada de K-fold. Como mencionamos en la sección de Métodos, sin embargo, una estimación de este tipo tiene problemas tanto conceptuales como computacionales, es decir, el LOOCV es un caso excepcionalmente conveniente.


Estimación del error LOOCV de los datos de la red. (A) El conjunto de datos original se da como la matriz de adyacencia A de una red. (B) En cada predicción ocultamos una sola pieza de enlace o información no-enlace de A: este enlace no observado o no observado no enlace es el conjunto de prueba, y la matriz de adyacencia A \ (i, j) A \ (i , J) sin la información en ese enlace o no enlace es el conjunto de entrenamiento.

El algoritmo basado en BP que utilizamos para inferir la asignación de clúster fue introducido por Decelle et al.21, 34. Este algoritmo es escalable y funciona bien en redes escasas; Esto es favorable, porque las redes del mundo real suelen ser escasas. De hecho, se sabe que el algoritmo BP alcanza asintóticamente el límite teórico-informativo35, 36 (cuando el número de clústeres es 2) en el sentido de precisión cuando la red es realmente generada a partir del modelo asumido, el modelo de bloqueo estocástico. En el algoritmo original, el número de cúmulos q * está determinado por la energía libre de Bethe, que es equivalente a la probabilidad logarítmica marginal aproximada negativa; Entre los modelos de diferentes (máximos) números de clusters, se selecciona el modelo más parsimonioso con baja energía libre de Bethe. A pesar de su plausibilidad, sin embargo, se sabe que esta prescripción tiene un desempeño pobre en la práctica. Una de las razones es que la estimación que utiliza la energía libre de Bethe se basa excesivamente en la suposición de que la red se genera a partir del modelo de bloques estocásticos, que casi siempre no es precisamente correcto. Mostramos que este problema se puede mejorar sustancialmente mediante la evaluación de errores de validación cruzada en lugar de la energía libre de Bethe mientras se mantienen las otras partes del algoritmo iguales. Con esta mejora, podemos concluir que el algoritmo basado en BP no es sólo una herramienta excelente en el caso ideal, sino que también es útil en la práctica.

Denotamos el conjunto de vértices y enlaces en las redes como V y E, y sus cardinalidades como N y L, respectivamente. A lo largo del presente estudio, consideramos redes escasas no dirigidas, e ignoramos multi-enlaces y auto-bucles para simplificar.


Resultados

Modelo de bloques estocástico


Primero expliquemos cómo se genera una instancia del modelo de bloque estocástico. El modelo de bloque estocástico es un modelo de grafo aleatorio que tiene una estructura modular plantada. La fracción de vértices que pertenecen al clúster σ está especificada por  γ σ; en consecuencia, cada vértice i tiene su asignación de clúster plantada σi{1,,q} donde q* es el número de clústeres. El conjunto de enlaces E se genera conectando pares de vértices de forma independiente y aleatoria de acuerdo con sus asignaciones de clúster. En otras palabras, los vértices i y j con asignaciones de clúster σ i  = σ y σ j  = σ′  están conectados con la probabilidad ω σσ; la matriz ω que especifica las probabilidades de conexión dentro y entre los clústeres se denomina matriz de afinidad. Tenga en cuenta que la matriz de afinidad ω es de O (N-1) cuando la red es escasa.

Como resultado, obtenemos la matriz de adyacencia A. Si bien la generación de instancias de red es un problema directo, la agrupación de grafos es su problema inverso. En otras palabras, inferimos las asignaciones de clúster de los vértices σ o sus distribuciones de probabilidad a medida que aprendemos los parámetros (γ, ω), dada la matriz de adyacencia A y el número de la entrada (máxima) de los conglomerados q. Después de haber obtenido los resultados para varios valores de q, seleccionamos q*. Obsérvese aquí que el valor de entrada q es el número máximo de conglomerados permitidos y que el número real de conglomerados que aparece para un q determinado puede ser menor que q.

Errores de validación cruzada

Consideramos cuatro tipos de errores de validación cruzada. Todos los errores se calculan utilizando los resultados de inferencias basadas en el modelo de bloques estocástico. Denominamos A\(i,j) como la matriz de adyacencia de una red en la que A ij no se observa, es decir, en la que se desconoce si  A ij  = 0 o A ij  = 1. En lo sucesivo generalmente denominamos p (X | Y ) como la probabilidad de X que está condicionada a Y o la probabilidad de Y cuando se observa X.

El proceso de predicción de enlaces es doble: primero, estimamos las asignaciones de clúster de un par de vértices; entonces, predecimos si existe una ventaja. Por lo tanto, la distribución predictiva posterior p(Aij=1|A\(i,j))  del modelo en el que los vértices i y j están conectados dataset dado A\(i,j), o la probabilidad marginal del modelo aprendido para el par de vértices, es la siguiente:

p(Aij=1|A\(i,j))=σi,σjp(Aij=1|σi,σj)p(σi,σj|A\(i,j))=p(Aij=1|σi,σj)A\(i,j),
(1)

donde A\(i,j) es el promedio sobre  y hemos omitido algunos de los parámetros condicionados. El error debe ser pequeño cuando la predicción de existencia de enlace para cada par de vértices es precisa. En otras palabras, la distribución de probabilidad en la que cada elemento tiene probabilidad de ecuación (1) está próxima, en el sentido de la divergencia de Kullback-Leibler (KL), a la distribución real, que se da como la distribución empírica. Por lo tanto, es natural emplear, como medida del error de predicción, la función de error de entropía cruzada 37.
  ,
(2)
donde
X¯i<jX(Aij)/L. Notar que hemos elegido las normalización de tal manera que E Bayes es típicamente O (1) en redes dispersas. Nos referimos a la ecuación (2) como el error de predicción de Bayes, que corresponde a la estimación LOOCV de la complejidad estocástica 38. Siempre que el modelo que utilizamos sea coherente con los datos, la distribución predictiva posterior es óptima como un elemento del error de predicción porque la dependencia intermedia (σ i σ j ) está completamente marginada y da el error más pequeño.
Desafortunadamente, la suposición de que el modelo que usamos es consistente con los datos es a menudo inválido en la práctica. En ese caso, el error de predicción Bayes E Bayes puede no ser óptimo para la predicción. En la ecuación (2), empleamos −
logp(Aij|A\(i,j)) como el error de un par de vértices. En cambio, podemos considerar la probabilidad logarítmica de las asignaciones de clústeres −logp(Aij|σi,σj) ser un elemento fundamental y una medida logp(Aij|σi,σj)A\(i,j) como el error de predicción de un par de vértices. En otras palabras, las asignaciones de clúster (σ i σ j ) se extraen de la distribución posterior, y el error del par de vértice se mide con respecto a las asignaciones fijas. Entonces, la función de error de entropía cruzada correspondiente es

(3)
Nos referimos a la ecuación (3) como el error de predicción de Gibbs. Si la distribución de probabilidad de las asignaciones de clúster es muy alta, entonces E Gibbs estará cerca de E Bayes, y ambas serán relativamente pequeñas si esas asignaciones predicen bien la red real. Alternativamente, podemos medir la estimación máxima a posteriori (MAP) de la ecuación (3). En otras palabras, en lugar de tomar el promedio sobre p(σi,σj|A\(i,j)), seleccionamos las asignaciones más probables para medir el error. Nos referimos a  E MAP(q como el error de predicción.
Finalmente, definimos el error de entrenamiento de Gibbs, al que nos referimos como entrenamiento E. Este error se puede obtener tomando el promedio sobre  p(σ i σ j |A en lugar de la ecuación (3), es decir,
.
(4)

Debido a que hacemos uso de la información con respecto a la existencia del enlace cuando tomamos el promedio, el resultado no es un error de predicción, sino que es la bondad del ajuste del modelo supuesto a los datos dados.

A primera vista, los errores de validación cruzada que presentamos anteriormente pueden parecer inviables desde el punto de vista computacional porque debemos conocer
 con respecto a cada par de vértices. En la sección Métodos, sin embargo, mostramos que tenemos expresiones analíticas de los errores de validación cruzada en términos de los resultados de BP; por lo tanto, la evaluación del modelo para las redes dispersas es muy eficiente.
En las siguientes subsecciones, mostramos el rendimiento de estos errores de validación cruzada para varias redes en relación con el rendimiento de la energía libre de Bethe.

Redes del mundo real

En primer lugar, y lo más importante, mostramos el rendimiento de la energía gratuita de Bethe y los errores de validación cruzada en las redes del mundo real. Las Figuras 1 y 3 muestran los resultados en la red de libros sobre política de los Estados Unidos39 (a los que nos referimos como libros políticos). Esta red es una red de compra cuyos vértices son libros vendidos en Amazon.com, y cada enlace representa un par de libros que compró el mismo comprador; los metadatos del conjunto de datos tienen las etiquetas "conservador", "liberal" y "neutral".

Figura 3

Evaluaciones modelo y clusters inferidos en la red de libros sobre política estadounidense. (a) energía libre de Bethe y (b) errores de predicción y entrenamiento como funciones del número de conglomerados q. Los cuatro datos en (b) son, de arriba abajo, los errores de predicción de Gibbs E Gibbs (triángulos verdes), las estimaciones MAP E MAP de E Gibbs (cuadrados amarillos), los errores de predicción Bayes E Bayes (círculos rojos) y los errores de entrenamiento de Gibbs Entrenamiento E (diamantes azules). Para cada error, el término constante se descuida y el error estándar se muestra en la sombra. (c) Los parámetros aprendidos, ω y γ, se visualizan desde q = 2 a 8. (d) Las asignaciones de clúster que se indican en los metadatos del conjunto de datos; los vértices del mismo color pertenecen al mismo grupo.

La figura 3b muestra que la estimación de validación cruzada del error de predicción de Gibbs E Gibbs se satura favorablemente, mientras que la energía libre de Bethe (figura 3a), el error de predicción de Bayes E Bayes y el entrenamiento E de error de Gibbs disminuyen a medida que aumentamos el número de entrada de clusters q. Aunque la estimación de MAP del error de predicción de Gibbs E MAP a menudo muestra un comportamiento similar al error de predicción de Gibbs E Gibbs, observamos en los resultados de otros conjuntos de datos que no parece ser claramente superior a E Gibbs.

Comparado con el error de predicción de Gibbs E Gibbs, el error de predicción de Bayes E Bayes parece ser más sensible a la suposición de que el modelo de bloques estocástico genera una red, por lo que rara vez observamos la clara saturación del error LOOCV. En una subsección a continuación, mostramos cómo se produce el sobreajuste y el ajuste insuficiente derivando expresiones analíticas para las diferencias entre los errores de validación cruzada.

¿Cómo deberíamos seleccionar el número de clústeres q * de los diagramas de validación cruzada obtenidos? Aunque este problema está bien definido cuando seleccionamos el mejor modelo, es decir, el modelo que tiene el menor error, es común seleccionar el modelo más parsimonioso en lugar del mejor modelo en la práctica. Entonces, ¿cómo determinamos el "modelo más parsimonioso" de los resultados? Este problema no está bien definido, y no hay una prescripción basada en principios obtenida por consenso.

Sin embargo, existe una regla empírica llamada regla de "error estándar uno" 27 que se ha utilizado con frecuencia. Recuerde que cada estimación de validación cruzada se da como un error promedio por enlace; por lo tanto, también podemos medir su error estándar. La regla de "un error estándar" sugiere seleccionar el modelo más simple cuya estimación no es más que un error estándar por encima de la estimación del mejor modelo. En el caso de la red de libros políticos, el mejor modelo es el modelo en el que q = 6. Debido a que el modelo más simple dentro del rango de un error estándar es q = 5, es nuestra elección final.

La partición real para cada valor de q se muestra en las figuras 1 y 3c. Las asignaciones de clúster indicadas en los metadatos se presentan en la Fig. 3d como referencia. En la figura 3c, se visualizan los valores aprendidos de los parámetros ω y γ: un elemento de mayor valor de la matriz de afinidad ω se indica en un color más oscuro, y el tamaño de un elemento refleja la fracción del tamaño del grupo γ σ. Para q = 3, podemos identificar dos comunidades y un clúster que está conectado de manera uniforme a esas comunidades, como se presume en los metadatos. Para q = 5, además, también se detectan los conjuntos de vértices centrales en cada comunidad. Tenga en cuenta que la recuperación de las etiquetas en los metadatos no es nuestro objetivo. Los metadatos no se determinan en función de la estructura de la red y no son la partición de verdad del terreno40.

También se debe tener en cuenta que minimizamos la energía libre de Bethe en el paso de inferencia del clúster en todos los casos. Cuando seleccionamos el número de clústeres q *, es decir, en el paso de selección del modelo, proponemos usar los errores de validación cruzada en lugar de la energía libre de Bethe.

Los resultados de otras redes se muestran en la Fig. 4. Son la red de amistad de un club de karate41, una red de coautoría de científicos que trabajan en redes7 (ver la referencia 42 para detalles de los conjuntos de datos) y la red metabólica de C. elegans43 . Nos referimos a aquellos como Karate Club, Network Science y C. elegans, respectivamente. Los resultados son cualitativamente similares a la red de libros políticos. Tenga en cuenta que la dependencia de estado inicial puede ser sensible cuando el número de entrada de los clústeres q es grande. Por lo tanto, los resultados pueden ser inestables en dicha región.


Figura 4

Resultados de evaluaciones modelo para varias redes del mundo real. Se trazan de la misma manera que la Fig. 3a, b.

De los resultados en las figuras 3 y 4, uno podría concluir que el error de predicción de Gibbs E Gibbs es el único criterio útil en la práctica. Sin embargo, por ejemplo, cuando se utiliza el método de retención en lugar del LOOCV (consulte la sección de Métodos), se puede confirmar que el error de predicción de Bayes E Bayes también se comporta razonablemente.

El error para q = 1

Para la red del club de karate en la figura 4, vemos que los errores siguen disminuyendo a excepción del error de predicción de Gibbs  E Gibbs. Recuerde que, para que el modelo de bloque estocástico con un gran qy un grado promedio bajo sean detectables, se requiere que la red muestre una estructura modular suficientemente fuerte21. Por lo tanto, aunque a priori no sabemos a qué error de predicción se debe hacer referencia, porque la red tiene un grado promedio menor que 5, es difícil creer que los errores distintos de E Gibbs sean apropiados. El error de predicción de Gibbs E Gibbs tiene el menor error en q = 3, y el modelo en el que q = 2 tiene un error dentro del rango de un error estándar de q = 3. Sin embargo, uno podría sospechar que el modelo más parsimonioso es el modelo con q = 1, es decir, el modelo que deberíamos suponer es un grafo aleatorio uniforme, y no hay una estructura modular estadísticamente significativa. En este caso, la probabilidad de conexión para un par de vértices arbitrarios está determinada por un único parámetro, es decir, , y es simplemente  ω=2L/N(N). Además, no hay diferencia entre los errores que enumeramos anteriormente. Por lo tanto,

(5)

Aquí, utilizamos el hecho de que ω = O (N -1) porque consideramos redes dispersas. En cada diagrama de errores de validación cruzada, los términos constantes y O (N -1) se descuidan. El número de vértices y enlaces en la red del club de karate es N = 34 y L = 78, respectivamente, es decir, -logω≃1.97, que es mucho más grande que los errores para q = 2; así concluimos que el número de conglomerados q * = 2.

Modelo de bloque estocástico corregido de grado

Se ha observado que el modelo estándar de bloques estocásticos que explicamos anteriormente a menudo no es adecuado para inferir clusters en redes del mundo real porque muchos de ellos tienen una distribución de grados libre de escala, mientras que el modelo estándar de bloques estocásticos está restringido a tener un Poisson. distribución de grados Esta incoherencia afecta tanto a la inferencia del clúster para un q * dado como a la selección del modelo. Por ejemplo, como se muestra en la figura 5a, encontramos que todos los criterios se sobreponen en gran medida para la red de blogs políticos cuando se utiliza el modelo estándar de bloques estocásticos. La red de blogs políticos es una red de hipervínculos entre blogs sobre política estadounidense (descuidamos las direcciones de los enlaces), que se espera que tenga dos grupos.





Resultados de las evaluaciones de modelos para la red de hipervínculos entre blogs sobre política de los Estados Unidos. (a) Los resultados del modelo estándar y los parámetros aprendidos. (b) Los resultados del modelo corregido en grado y los parámetros aprendidos.



El modelo de bloque estocástico de grado corregido [44, 45] se usa a menudo como una alternativa. Este modelo tiene el parámetro de corrección de grado θ i para cada vértice además de γ y ω, donde θ permite que un grupo tenga una distribución de grados heterogénea. (Consulte la ref. 44 para conocer los detalles del modelo). La evaluación del modelo de validación cruzada puede extenderse directamente al modelo de bloque estocástico de grado corregido: para la inferencia de las asignaciones de conglomerados, el algoritmo BP se puede encontrar en la ref. 46; para los errores de validación cruzada, solo necesitamos reemplazar ωσi,σj para la probabilidad y p(Aij=1|σi,σj) con θiωσi,σjθj en cada caso. Como se muestra en la Fig. 5b, la evaluación es razonable cuando se usa un modelo de bloque estocástico corregido en grados. Aunque el error cae para q ≥ 5, es mejor descartar esta parte porque el número de iteraciones hasta que la convergencia se vuelve relativamente grande allí; lo consideramos como la "solución incorrecta" que se menciona en la ref. 47.

Cuando q = 1, no asumimos el grafo aleatorio de Erdös-Rényi, sino que asumimos el grafo aleatorio que tiene la misma secuencia de grados esperada que el conjunto de datos real7, que es el modelo que se usa a menudo como modelo nulo en modularidad. Por lo tanto, la probabilidad de que los vértices i y j estén conectados es d i d j /2L. Después de algún álgebra, asumiendo que didj/2L1, el error para q = 1 es aproximadamente
11Li=1Ndilogdi+log(2L),
(6)

que es igual a la ecuación (5) cuando la red es regular. En el caso de la red de blogs políticos, el error de validación cruzada para q = 1 es aproximadamente 3.42. (Es 2.42 en el grafo porque se descuida el término constante). Por lo tanto, obtenemos q * = 2.


Redes sintéticas y el umbral de detectabilidad.

Es importante investigar qué tan bien se desempeñan los errores de validación cruzada en una situación crítica, es decir, el caso en el que la red está cerca del grafo aleatorio uniforme. Para lograr este objetivo, observamos el rendimiento en el modelo de bloque estocástico, el modelo que asumimos para la inferencia en sí. Como se explica en la subsección del modelo de bloque estocástico, la cercanía al grafo aleatorio uniforme se especifica con la matriz de afinidad. Aquí, consideramos una estructura de comunidad simple: establecemos ω para los elementos diagonales, y los elementos restantes se configuran en ω out, donde ω in ≥ ω out. Parametrizamos la proximidad al grafo aleatorio uniforme, con ϵ=ωout/ωin; ϵ=0representa que la red se compone de grupos completamente desconectados, y ϵ = 1 representa el grafo aleatorio uniforme. Hay un punto de transición de fase ∗ ∗ por encima del cual es estadísticamente imposible inferir una estructura plantada. Este punto se llama umbral de detectabilidad. Nuestro interés aquí es determinar si el número plantado de conglomerados q * se puede identificar correctamente usando los errores de validación cruzada cuando ϵ se establece para estar cerca de ϵ ∗.

La Figura 6 muestra la energía libre de Bethe y los errores de validación cruzada para los modelos de bloques estocásticos. En cada grafo, establecemos q * = 4, cada grupo tiene 1,000 vértices y el grado promedio c se establece en 8. De abajo hacia arriba, los valores de ϵ
son 0.1, 0.15, 0.2 y 0.25, mientras que el umbral de detectabilidad es ϵ ∗ ≃0.31 21. Tenga en cuenta que cuando el valor de ϵ está cerca de ϵ, las asignaciones de conglomerados inferidas apenas se correlacionan con las asignaciones plantadas; por lo tanto, el resultado está cerca de una conjetura aleatoria de todos modos.

 
Desempeño de los criterios de evaluación del modelo en varios modelos de bloques estocásticos. Los resultados de (a) Bethe energía libre, (b) error de predicción de Bayes E Bayes, (c) error de predicción de Gibbs E Gibbs, (d) estimación MAP del error de predicción de Gibbs E MAP, y (e) error de entrenamiento de Gibbs E entrenamiento son exhibidos. Las líneas en cada gráfica representan los resultados de varios valores de ϵ. 



En todas las gráficas, las curvas de validación se vuelven más suaves a medida que aumentamos el valor de ϵ, lo que indica que es difícil identificar el modelo más parsimonioso. Está claro que la energía libre de Bethe y el error de predicción de Bayes E Bayes se desempeñan mejor que el error de predicción de Gibbs E Gibbs en el presente caso porque las redes que analizamos se corresponden exactamente con el modelo que asumimos. La Figura 6 muestra que el error de predicción de Gibbs E Gibbs y su estimación de MAP E MAP subestiman q * cerca del umbral de detectabilidad. Este hallazgo es consistente con los resultados que obtuvimos para las redes del mundo real que la energía libre de Bethe y el error de predicción de Bayes E Bayes tienden a sobreestimar. De hecho, bajo ciertas suposiciones, podemos deducir que el error de predicción de Bayes E Bayes identifica el número de agrupaciones plantadas hasta el umbral de detectabilidad, mientras que el error de predicción de Gibbs E Gibbs cumple estrictamente cerca del umbral de detectabilidad. (Consulte la sección Métodos para obtener la derivación). Por lo tanto, existe un compromiso entre el error de predicción de Bayes E Bayes y el error de predicción de Gibbs E Gibbs; su superioridad depende de la precisión de la suposición del modelo de bloque estocástico y la borrosidad de la red.

Discusión

Para determinar el número de agrupaciones, ambos propusimos estimaciones de errores de predicción LOOCV utilizando BP y revelamos algunas de las relaciones teóricas entre los errores. Son de principios y escalables y, en la medida en que los examinamos, tienen un buen desempeño en la práctica. A diferencia de los criterios similares a BIC, los errores de predicción no requieren que la consistencia del modelo sea aplicable. Además, aunque solo tratamos los modelos de bloques estocásticos estándar y con corrección de grado, la aplicabilidad de nuestras estimaciones LOOCV no se limita a estos modelos. Con una elección adecuada de modelos de bloques, esperamos que el marco actual también se pueda utilizar en la gran mayoría de las redes del mundo real, como las redes dirigidas, ponderadas y bipartitas y las redes que tienen bordes positivos y negativos. Esto contrasta con algunos criterios que se limitan a estructuras modulares específicas.

El código para los resultados del estudio actual se puede encontrar en la ref. 50. (Consulte la descripción en el mismo para obtener más detalles del algoritmo).

La selección del número de grupos q * a veces puede ser sutil. Por ejemplo, como mencionamos brevemente anteriormente, cuando el algoritmo de inferencia depende sensiblemente de la condición inicial, los resultados de la LOOCV pueden ser inestables; todos los algoritmos comparten este tipo de dificultad siempre que se considere el problema de optimización no convexo. A veces, la curva LOOCV puede ser irregular de tal manera que es difícil determinar el modelo más parco. Para este problema, notamos que hay mucha información además de los errores de predicción que nos ayudan a determinar la cantidad de clusters q *, y debemos tenerlos en cuenta. Por ejemplo, podemos detener la evaluación o descartar el resultado cuando (i) el número de iteraciones hasta que la convergencia sea grande47, como hemos observado en la Fig. 5b, (ii) la partición resultante no muestra un comportamiento significativo, por ejemplo, no patrón claro en la matriz de afinidad, o (iii) el número real de agrupaciones no aumenta a medida que aumenta q. Toda esta información está disponible en la salida de nuestro código.

Es posible que la dificultad de seleccionar el número de grupos q * surja en el propio modelo. La adaptación con los modelos de bloques estocásticos es flexible; por lo tanto, el algoritmo puede inferir no solo las estructuras de distribución y desarticulación, sino también las estructuras más complejas. Sin embargo, la flexibilidad también indica que los modelos ligeramente diferentes podrían adaptarse a los datos tan bien como el modelo más parsimonioso. Como resultado, podemos obtener una curva de LOOCV que disminuye gradualmente para un amplio rango de q. Por lo tanto, debe haber una compensación entre la flexibilidad del modelo y la dificultad de la evaluación del modelo.

A pesar de que la evaluación del modelo basada en la precisión de la predicción es un principio bien aceptado, según nuestro conocimiento, el método que es aplicable a redes modulares a gran escala en el marco bayesiano se discute en este estudio por primera vez. Para una mejor precisión y escalabilidad, creemos que hay más por hacer. Uno podría investigar si los errores de LOOCV funcionan, en cierto sentido, mejor que otros criterios similares a BIC. Las relaciones y tendencias de los errores de LOOCV en comparación con otros criterios de evaluación del modelo ciertamente proporcionarían un trabajo futuro interesante, aunque es poco probable que podamos concluir la superioridad de los criterios sobre los demás28. En la práctica, si la asignación de recursos lo permite, siempre es mejor evaluar múltiples criterios51.



Referencias


1. Barabsi, A.-L. Network Science 1 edn. (Cambridge University Press, 2016).
2. Newman, M. E. J. Networks: An Introduction (Oxford university press, 2010).
3. Fortunato, S. Community detection in graphs. Phys. Rep. 486, 75–174 (2010).
4. Leger, J.-B., Vacher, C. & Daudin, J.-J. Detection of structurally homogeneous subsets in graphs. Stat. Comput. 24, 675–692 (2014).
5. Girvan, M. & Newman, M. E. J. Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99, 7821–7826 (2002).
6. Radicchi, F., Castellano, C., Cecconi, F., Loreto, V. & Parisi, D. Defining and identifying communities in networks. Proc. Natl. Acad. Sci. USA 101, 2658–63 (2004).
7. Newman, M. E. J. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74, 036104 (2006).
8. Lancichinetti, A., Fortunato, S. & Radicchi, F. Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78, 046110 (2008).
9. Holland, P. W., Laskey, K. B. & Leinhardt, S. Stochastic blockmodels: First steps. Soc. Networks 5, 109–137 (1983).
10. Newman, M. E. J. & Girvan, M. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004).
11. Zhang, P. & Moore, C. Scalable detection of statistically significant communities and hierarchies, using message passing for modularity. Proc. Natl. Acad. Sci. USA 111, 18144–18149 (2014).
12. Rosvall, M. & Bergstrom, C. Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. USA 105, 1118–1123 (2008).
13. Rosvall, M. & Bergstrom, C. T. Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems. PloS One 6, e18209 (2011).
14. Newman, M. E. J. Spectral methods for community detection and graph partitioning. Phys. Rev. E 88, 042822 (2013).
15. Shi, J. & Malik, J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 888–905 (2000).
16. Luxburg, U. A tutorial on spectral clustering. Stat. Comput. 17, 395–416 (2007).
17. Krzakala, F. et al. Spectral redemption in clustering sparse networks. Proc. Natl. Acad. Sci. USA 110, 20935–40 (2013).
18. Abbe, E. & Sandon, C. Recovering communities in the general stochastic block model without knowing the parameters. In Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M. & Garnett, R. (eds) Advances in Neural Information Processing Systems 28, 676–684 (Curran Associates, Inc., 2015).
19. Nowicki, K. & Snijders, T. A. B. Estimation and prediction for stochastic blockstructures. J. Amer. Statist. Assoc. 96, 1077–1087 (2001).
20. Daudin, J. J., Picard, F. & Robin, S. A mixture model for random graphs. Stat. Comput. 18, 173–183 (2008).
21. Decelle, A., Krzakala, F., Moore, C. & Zdeborová, L. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E 84, 066106 (2011).
22. Hayashi, K., Konishi, T. & Kawamoto, T. A tractable fully bayesian method for the stochastic block model. arXiv preprint arXiv:1602.02256 (2016).
23. Newman, M. E. J. & Reinert, G. Estimating the number of communities in a network. Phys. Rev. Lett. 117, 078301 (2016).
24. Peixoto, T. P. Parsimonious module inference in large networks. Phys. Rev. Lett. 110, 148701 (2013).
25. Peixoto, T. P. Hierarchical Block Structures and High-Resolution Model Selection in Large Networks. Physical Review X 4, 011047 (2014).
26. Peixoto, T. P. Model selection and hypothesis testing for large-scale network models with overlapping groups. Phys. Rev. X 5, 011033 (2015).
27.  Hastie, T. J., Tibshirani, R. J. & Friedman, J. H. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer series in statistics (Springer, New York, 2009).
28. Arlot, S. & Celisse, A. A survey of cross-validation procedures for model selection. Statist. Surv. 4, 40–79 (2010).
29. Celeux, G. & Durand, J.-B. Selecting hidden markov model state number with cross-validated likelihood. Comput. Stat. 23, 541–564 (2008).
30. Vehtari, A. & Ojanen, J. A survey of bayesian predictive methods for model assessment, selection and comparison. Stat. Surv. 142–228 (2012).
31. Airoldi, E. M., Blei, D. M., Fienberg, S. E. & Xing, E. P. Mixed membership stochastic blockmodels. In Koller, D., Schuurmans, D., Bengio, Y. & Bottou, L. (eds) Advances in Neural Information Processing Systems 21, 33–40 (Curran Associates, Inc., 2009).
32. Hoff, P. Modeling homophily and stochastic equivalence in symmetric relational data. In Platt, J. C., Koller, D., Singer, Y. & Roweis, S. T. (eds) Advances in Neural Information Processing Systems 20, 657–664 (Curran Associates, Inc., 2008).
33. Chen, K. & Lei, J. Network cross-validation for determining the number of communities in network data. arXiv preprint arXiv:1411.1715 (2014).
34. Decelle, A., Krzakala, F., Moore, C. & Zdeborová, L. Inference and Phase Transitions in the Detection of Modules in Sparse Networks. Phys. Rev. Lett. 107, 065701 (2011).
35. Mossel, E., Neeman, J. & Sly, A. Reconstruction and estimation in the planted partition model. Probab. Theory Relat. Fields 1–31 (2014).
36. Massoulié, L. Community detection thresholds and the weak ramanujan property. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ’ 14, 694–703 (ACM, New York, NY, USA, 2014).
37. Bishop, C. M. Pattern Recognition and Machine Learning (Information Science and Statistics) (Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006).
38. Levin, E., Tishby, N. & Solla, S. A. A statistical approach to learning and generalization in layered neural networks. In Proceedings of the Second Annual Workshop on Computational Learning Theory, COLT ’ 89, 245–260 (1989).
39. Newman, M. E. J. Modularity and community structure in networks. Proc. Natl. Acad. Sci. USA 103, 8577–8582 (2006).
40. Peel, L., Larremore, D. B. & Clauset, A. The ground truth about metadata and community detection in networks. arXiv:1608.05878 (2016).
41. Zachary, W. W. An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33, 452–473 (1977).
42. Newman, M. E. J. http://www-personal.umich.edu/~mejn/netdata/ (Date of access: 11/05/2015) (2006).
43. Duch, J. & Arenas, A. Community detection in complex networks using extremal optimization. Phys. Rev. E 72, 027104 (2005).
44. Karrer, B. & Newman, M. E. J. Stochastic blockmodels and community structure in networks. Phys. Rev. E 83, 016107 (2011).
45. Zhao, Y., Levina, E. & Zhu, J. Consistency of community detection in networks under degree-corrected stochastic block models. Ann. Stat. 2266–2292 (2012).
46. Yan, X. et al. Model selection for degree-corrected block models. J. Stat. Mech. Theor. Exp. 2014, P05007 (2014).
47. Newman, M. E. J. & Clauset, A. Structure and inference in annotated networks. Nat. Commun. 7, 11863 (2016).
48. Csiszár, I. Axiomatic characterizations of information measures. Entropy 10, 261 (2008).
49. Amari, S.-i & Cichocki, A. Information geometry of divergence functions. Bulletin of the Polish Academy of Sciences: Technical Sciences 58, 183–195 (2010).
50. Kawamoto, T. https://github.com/tatsuro-kawamoto/graphBIX (Date of access: 13/09/2016) (2016).
51. Domingos, P. A few useful things to know about machine learning. Commun. ACM 55, 78–87 (2012).
52. Mézard, M. & Montanari, A. Information, Physics, and Computation (Oxford University Press, 2009).
53. Opper, M. & Winther, O. Mean field approach to bayes learning in feed-forward neural networks. Phys. Rev. Lett. 76, 1964–1967 (1996).