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⁎}${\sigma }_i\in \{1,\dots ,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))$p(A_{ij}=1|A^{\backslash (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),$$\begin{array}{lll}\hfill p\left(A_{ij}=1|A^{\backslash (i,j)}\right)& \hfill =\hfill & \sum _{{\sigma }_i,{\sigma }_j}p\left(A_{ij}=1|{\sigma }_i,{\sigma }_j\right)p\left({\sigma }_i,{\sigma }_j|A^{\backslash (i,j)}\right)\hfill \\ \hfill & \hfill =\hfill & {〈p\left(A_{ij}=1|{\sigma }_i,{\sigma }_j\right)〉}_{A^{\backslash (i,j)}},\hfill \end{array}$$

(1)

donde ⟨⋯⟩A\(i,j)${〈\cdots 〉}_{A^{\backslash (i,j)}}$ es el promedio sobre p(σi,σj|A\(i,j)) 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.

EBayes(q)==−logp(Aij∣∣A\(i,j))¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯−1L∑i<j[Aijlogp(Aij=1∣∣A\(i,j))+(1−Aij)logp(Aij=0∣∣A\(i,j))],$$\begin{array}{l}{ }^{},\hfill \end{array}$$

(2)

donde
X¯¯¯≡∑i<jX(Aij)/L$\overline{X}\equiv {\sum }_{i<j}X(A_{ij})/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))$\log p(A_{ij}|A^{\backslash (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)$\log p(A_{ij}|{\sigma }_i,{\sigma }_j)$ ser un elemento fundamental y una medida ⟨−logp(Aij|σi,σj)⟩A\(i,j)${〈-\log p(A_{ij}|{\sigma }_i,{\sigma }_j)〉}_{A^{\backslash (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

EGibbs(q)=⟨−logp(Aij|σi,σj)⟩A\(i,j)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯.$$$$

(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))$p({\sigma }_i,{\sigma }_j|A^{\backslash (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,

Etraining(q)=⟨−logp(Aij|σi,σj)⟩A¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯..

(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
p(σi,σj|A\(i,j)) 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, p(Aij|σiσj)=ω, y es simplemente  ω=2L/N(N). Además, no hay diferencia entre los errores que enumeramos anteriormente. Por lo tanto,

EBayes=EGibbs=EMAP=Etraining≈1−logω.

(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/2L≪1, el error para q = 1 es aproximadamente
1−1L∑i=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).