Estructura de comunidades
Esta heterogeneidad de las conexiones sugiere que la red tiene ciertas divisiones naturales.
Aun así en algunos casos una representación mejor podría ser una dónde los vértices pertenezcan a más de una comunidad.
Existen redes que no tienen ninguna estructura de comunidades significativa.
El método funciona bien en muchas aplicaciones para las cuales fue inicialmente concebido pero es menos adecuado para encontrar estructura de comunidades en redes generales pues encontrará comunidades sin importar si están implícitas en la estructura, y solo encontrará un número fijo de comunidades.
[7] Otro método para detectar estructuras de comunidades es el agrupamiento jerárquico.
Luego se agrupan los nodos similares en comunidades de acuerdo a dicha medida.
Existen varios esquemas comunes para realizar el agrupamiento, los dos más sencillos sonː agrupamiento de enlace-simple, en el cual se considera que dos grupos son comunidades separadas si y solo si para todo par de nodos en diferentes grupos la similitud es menor que un umbral, y agrupamiento de enlace-comleto, en el cual se cumple que dentro de cada grupo todo par de nodos tiene una similitud mayor que un umbral.
Dado que una búsqueda exhaustiva por todas las posibles particiones de la red es normalmente impracticable, los algoritmos prácticos se basan en métodos aproximados de optimización tales con algoritmos golosos, recosido simulado, u optimización espectral, con diferentes enfoques basados en velocidad y exactitud.
[10][11] Un enfoque popular es el método Louvain, que iterativamente optimiza comunidades locales hasta que la modularidad global no puede ser mejorada a través de modificaciones a la distribución de comunidades actual.
La mayor parte de los métodos en la literatura están basados en el modelo de bloque estocástico[16] así como variantes que incluyen afiliación mixta,[17][18] grado-corrección,[19] y estructuras jerárquicas.
No es sorprendente que existan múltiples enfoques para detectar comunidades en una red basados la detección de cliques en un grafo y en el análisis de como estos se superponen dado que los nodos no pueden estar más densamente conectados que en un clique.
La unión de estos cliques forma un grafo cuyas componentes conexas definen comunidades.
Es decir comunidades que son las componentes conexas del grafo clique.
Luego esta estructura se degrada agregando o eliminando aristas de forma que cada vez es más difícil detectar las comunidades originales.
Al final, la red llega a un punto donde es esencialmente aleatoria.
