Detección de Comunidades Curso Redes y Sistemas Complejos
Curso Redes y Sistemas Complejos

Detección de Comunidades
en Redes

Unidad del curso Redes y Sistemas Complejos dedicada a detección de comunidades. Recorre fundamentos matemáticos, intuición de modelos y métodos algorítmicos, desde enfoques clásicos basados en modularidad hasta modelos generativos e inferencia sobre particiones.

01
In

Introducción y Problema Formal

Muchas redes del mundo real —redes sociales, biológicas, tecnológicas— exhiben comunidades: subconjuntos de nodos densamente interconectados internamente y escasamente conectados con el resto. Identificarlas revela organización funcional, jerarquía estructural y dinámica de difusión.

Definición formalDado un grafo \(G=(V,E)\), el problema consiste en encontrar una partición \(\mathcal{C}=\{C_1,\ldots,C_k\}\) de \(V\) tal que los nodos dentro de una misma comunidad estén más conectados entre sí que con nodos de otras comunidades. En la práctica, esta intuición se operacionaliza mediante una función objetivo (por ejemplo, modularidad) o mediante un modelo generativo (por ejemplo, SBM); no existe una definición universal única de “comunidad”.
Info
Maximizar modularidad exactamente es NP-duro (Brandes et al., 2008). Por eso los algoritmos prácticos usan heurísticas, relajaciones espectrales o inferencia estadística.
No solapadas (hard)
  • Cada nodo en exactamente una comunidad
  • Louvain, Leiden, SBM, LPA
  • \(\sigma:V\to\{1,\ldots,k\}\)
Solapadas (soft)
  • Un nodo puede pertenecer a varios grupos
  • OSLOM, BigCLAM, SBM mixto
  • Vector de pertenencia \(\in[0,1]^k\)
02
Q

Modularidad: La Función Objetivo Central

La modularidad de Newman & Girvan (2004) mide la calidad de una partición comparando la fracción de aristas dentro de comunidades con la fracción esperada bajo un modelo nulo.

Modularity Q — Newman & Girvan (2004)
\[Q=\frac{1}{2m}\sum_{ij}\left[A_{ij}-\frac{k_ik_j}{2m}\right]\delta(\sigma_i,\sigma_j)\]

Donde \(A_{ij}\) es la adyacencia, \(k_i\) el grado del nodo \(i\), \(m\) el número de aristas, \(\delta(\sigma_i,\sigma_j)=1\) si los nodos comparten comunidad. La matriz de modularidad \(B_{ij}=A_{ij}-k_ik_j/2m\) permite escribir, para una bipartición codificada por \(s_i\in\{+1,-1\}\), \(Q=\tfrac{1}{4m}\mathbf{s}^\top\mathbf{B}\,\mathbf{s}\).

Aviso
Límite de resolución (Fortunato & Barthélemy, 2007): Q no puede detectar comunidades cuyo número de aristas internas sea \(O(\sqrt{m})\). Comunidades pequeñas son fundidas con otras en redes grandes.
03
CN

Greedy Modularity Optimization

Clauset, Newman & Moore (2004): si \(e_{ij}\) es la fracción de aristas entre comunidades \(i\) y \(j\), y \(a_i=\sum_j e_{ij}\), entonces la variación de Q al fusionarlas es:

Incremento de Q al fusionar i y j
\[\Delta Q_{ij}=2\left(e_{ij}-a_ia_j\right)\]

donde \(a_i\) y \(a_j\) son las fracciones de extremos de arista incidentes en cada comunidad. Esta es la forma estándar cuando \(e_{ij}\) ya está normalizado por el número total de aristas.

Inicializar: cada nodo es su propia comunidad. Calcular \(\Delta Q_{ij}\) para pares adyacentes.
Seleccionar el par \((i,j)\) con mayor \(\Delta Q_{ij}\) y fusionar.
Actualizar la cola de prioridades y las entradas afectadas de \(\Delta Q\) usando estructuras dispersas.
Detener cuando \(\Delta Q_{ij}\leq0\) para todos los pares.

Complejidad: \(O(md\log n)\), donde \(d\) es la profundidad del dendrograma. Produce un dendrograma jerárquico completo.

Dendrograma de fusiones — cada nivel es una ronda de ΔQ
0123 4567 891011 A B C ΔQ≤0 nivel fusión →
04
λ

Métodos Espectrales

Los métodos espectrales usan la estructura algebraica del grafo —sus autovalores y autovectores— para detectar comunidades. Existen dos variantes principales que parten de objetos matriciales distintos.

Variante 1 — Bipartición por la matriz de modularidad (Newman, 2006)

Newman (2006) observó que maximizar la modularidad Q es equivalente a encontrar la mejor bipartición del grafo usando la matriz de modularidad \(\mathbf{B}\).

Matriz de modularidad — Newman (2006)
\[B_{ij}=A_{ij}-\frac{k_ik_j}{2m},\quad Q=\frac{1}{4m}\mathbf{s}^\top\mathbf{B}\,\mathbf{s},\quad s_i\in\{+1,-1\}\]

El problema discreto sobre \(\mathbf{s}\in\{+1,-1\}^n\) es difícil. Newman (2006) lo relaja a un problema espectral sobre variables reales: el eigenvector de mayor autovalor de \(\mathbf{B}\), llamado \(\mathbf{u}_1\), maximiza la relajación cuadrática. Luego se usa el signo de sus componentes como regla de corte: \(\sigma_i = +1\) si \(u_{1i} > 0\) y \(\sigma_i = -1\) si \(u_{1i} < 0\). Para obtener \(k > 2\) comunidades, se aplica el procedimiento recursivamente a subgrafos o se recurre a variantes espectrales multivía.

λ Bipartición espectral: el signo de u₁ separa los dos grupos
GRAFO ORIGINAL + + + + − − − − signo de u₁ EIGENVECTOR PRINCIPAL u₁ DE B + + + + − − corte: signo 0 u₁ > 0 → grupo A u₁ < 0 → B Regla de corte: σᵢ = sign(u₁ᵢ); es una aproximación espectral del problema discreto Para k > 2: aplicar bipartición recursivamente a cada subgrafo (Newman 2006)

Lectura: la matriz \(\mathbf{B}\) captura si dos nodos están más conectados de lo esperado bajo el modelo nulo. El eigenvector principal de \(\mathbf{B}\) separa direcciones estructurales opuestas; cortar por el signo es la heurística espectral estándar para obtener una bipartición, no una prueba de optimalidad global del problema discreto.

Nota
La bipartición espectral de Newman es esencialmente determinista para \(k=2\), salvo simetrías o degeneraciones que dejan empates de signo o subespacio. Para \(k>2\) la recursión puede acumularse y no garantiza el óptimo global de \(Q\).

Variante 2 — Clustering espectral del Laplaciano (Shi & Malik 2000; Ng, Jordan & Weiss 2002)

El enfoque más general usa el Laplaciano del grafo. Cada nodo queda embebido en \(\mathbb{R}^k\) usando \(k\) eigenvectores; las comunidades emergen como nubes separadas en ese espacio.

Laplaciano normalizado (Shi & Malik, 2000)
\[\mathcal{L}=\mathbf{D}^{-1/2}\mathbf{L}\mathbf{D}^{-1/2}=\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2},\quad 0=\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_n\]

Para \(k\) comunidades: tomar los \(k\) primeros eigenvectores de \(\mathcal{L}\), formar la matriz \(\mathbf{U}\in\mathbb{R}^{n\times k}\) y aplicar \(k\)-means a las filas. El número de autovalores próximos a cero revela el número de comunidades a través del eigengap: el salto brusco entre \(\lambda_k\) y \(\lambda_{k+1}\).

El segundo eigenvector del Laplaciano no normalizado \(\mathbf{L}=\mathbf{D}-\mathbf{A}\) se llama vector de Fiedler y separa el grafo en dos por su cuello de botella. La desigualdad de Cheeger lo conecta con la conductancia: \(\lambda_2/2 \leq h(G) \leq \sqrt{2\lambda_2}\).

λ Eigengap + embedding: cómo el espectro revela k comunidades
ESPECTRO DE AUTOVALORES DE ℒ 0 λ₁≈0 λ₂≈0 λ₃≈0 EIGENGAP heurística: sugiere k = 3 λ₄ λ₅ λ₆ EMBEDDING EN (u₂, u₃) → k-means u₂ u₃ A B C ① Calcular ℒ ② Extraer eigenvectores u₁…uₖ ③ Embeber nodos en ℝᵏ ④ k-means sobre las filas de U Un eigengap marcado sugiere un k plausible; no determina por sí solo un k óptimo universal

Lectura (izquierda): tres autovalores ≈ 0 son consistentes con una estructura de tres bloques en este ejemplo. El eigengap es una señal diagnóstica útil, pero no una regla exacta para todo grafo. Lectura (derecha): cada nodo es un punto en el espacio de eigenvectores (u₂, u₃); si las nubes quedan bien separadas, \(k\)-means puede recuperar la partición con buena calidad.

Marco
La desigualdad de Cheeger conecta \(\lambda_2\) (Fiedler) con la conductancia del grafo: \(\lambda_2/2\leq h(G)\leq\sqrt{2\lambda_2}\). Un \(\lambda_2\) pequeño indica una red cerca de desconectarse — es el cuello de botella estructural.
05
GN

Girvan–Newman

Girvan & Newman (2002): las aristas entre comunidades concentran la mayor parte de los caminos más cortos.

Edge Betweenness Centrality
\[b_e=\sum_{s\neq t}\frac{\sigma_{st}(e)}{\sigma_{st}}\]

El algoritmo calcula \(b_e\) (\(O(mn)\) por BFS), elimina la arista máxima, recalcula, y repite. Se retorna la partición con mayor Q. Complejidad total: \(O(m^2n)\). Solo viable para \(n\lesssim10^4\).

Betweenness de aristas: los puentes concentran el flujo
A B C b = 32 4 nodos × 8 nodos b = 32 8 nodos × 4 nodos b_int ≈ 3 b_int ≈ 3 b_int ≈ 3 Paso 1: eliminar arista de mayor b (un puente) → Paso 2: recalcular b → Paso 3: repetir

Lectura: las aristas naranjas gruesas son los puentes — concentran todos los caminos más cortos entre grupos distintos (b = 4×8 = 32). Las aristas internas tienen betweenness ≈ 3, un orden de magnitud menor. El algoritmo elimina iterativamente la arista de mayor b y recalcula hasta que el grafo se divide en componentes, revelando las comunidades. Se retorna la partición de mayor Q.

Clave
Las aristas puente concentran flujo de caminos más cortos porque toda ruta entre comunidades distintas debe cruzarlas.
06
Lv

Método de Louvain

Blondel et al. (2008): dos fases iterativas que optimizan Q. En la práctica escala a redes de \(10^8\) nodos con complejidad empírica \(O(m)\)–\(O(m\log m)\) (no hay cota formal).

Ganancia de Q al mover nodo i a comunidad C
\[\Delta Q=\frac{k_{i,\mathrm{in}}}{m}-\frac{\Sigma_{\mathrm{tot}}\cdot k_i}{2m^2}\]

donde \(k_{i,\mathrm{in}}\) = aristas de \(i\) hacia \(C\), \(\Sigma_{\mathrm{tot}}\) = suma de grados en \(C\), \(m\) = aristas totales. (Forma simplificada del original Blondel et al., 2008.)

Fase 1: cada nodo se mueve a la comunidad vecina que más aumenta Q. Fase 2: las comunidades se contraen en super-nodos y se repite.

Lectura: Fase 1 (izquierda): cada nodo se mueve a la comunidad vecina que más sube Q — los nodos se "autoorganizan" en clusters densos. Fase 2 (derecha): cada cluster se contrae en un super-nodo (gran círculo punteado con nodos internos visibles). Al super-grafo se le aplica de nuevo la Fase 1.

Aviso
Traag et al. (2019) mostraron que Louvain puede producir comunidades arbitrariamente mal conectadas e incluso desconectadas. Ese problema motivó el desarrollo de Leiden.
Fase 1 y Fase 2: de nodos a super-nodos
FASE 1 — Movimiento local A (K₄) B (K₄) → Fase 2 FASE 2 — Super-nodos sA sB
07
Le

Algoritmo de Leiden

Traag, Waltman & van Eck (2019): tres fases que mejoran Louvain y evitan comunidades desconectadas.

Movimiento local: parte con una fase del mismo espíritu que Louvain, optimizando localmente la función objetivo elegida.
Refinamiento: revisa cada comunidad internamente y la subdivide si es necesario para evitar componentes mal conectados. Esta fase es más sutil que una simple regla local por nodo.
Agregación: construir el super-grafo usando la partición refinada, no la salida cruda de la fase local.
Idea rigurosa de la Fase 2
Leiden no agrega directamente las comunidades encontradas por movimiento local. Primero las refina en subcomunidades bien conectadas respecto de la función objetivo elegida; solo después construye el super-grafo. La garantía central es conectividad interna, no una simple regla local por nodo.
Constant Potts Model (función objetivo generalizada)
\[\mathcal{H}=-\sum_c\left[e_c-\gamma\binom{n_c}{2}\right]\]
Fase 2 de Leiden: verificar conectividad antes de agregar
Louvain: falla 0 1 2 3 4 5 6 7 8 A∪C desconectada → Leiden F2 Leiden: refinado A B C

Lectura: Louvain (izquierda) puede dejar A y C dentro de la misma comunidad aunque el subgrafo inducido no sea conexo. Leiden (derecha) refina la partición antes de agregar y, en este ejemplo, termina con tres comunidades conexas. La idea central es que la conectividad interna pasa a ser parte explícita del procedimiento.

Garantía clave (Traag et al., 2019)Leiden proporciona garantías de conectividad interna y de optimalidad local bajo su esquema de refinamiento, pero no garantiza el óptimo global de la función objetivo. Su mejora central respecto de Louvain es excluir comunidades finales desconectadas.
08
Im

Infomap

Rosvall & Bergstrom (2008): detectar comunidades ≡ minimizar los bits para describir una caminata aleatoria.

Map Equation
\[L(\mathcal{M})=q_\curvearrowleft H(\mathcal{Q})+\sum_i p_i^\circlearrowleft H(\mathcal{P}_i)\]

donde \(q_\curvearrowleft\) es la frecuencia de cruce entre módulos, \(H(\mathcal{Q})\) la entropía del código de módulos y \(H(\mathcal{P}_i)\) la del código de nodos en el módulo \(i\). Una buena partición permite reusar códigos locales.

Codebook global vs modular: la misma trayectoria, menos bits
Sin módulos (3 bits/paso) n₀ = 000 n₁ = 001 n₂ = 010 n₃ = 011 n₄ = 100 n₅ = 101 Trayectoria 0→1→2→0→3→4: 000·001·010·000·011·100 = 18 bits → módulos Con módulos (~2 bits/paso) Módulo A: n₀=00 n₁=01 n₂=10 EXIT=11 Módulo B: n₃=00 n₄=01 n₅=10 EXIT=11 Módulos: A=0 B=1 0→1→2→0→EXIT→B→3→4: 00·01·10·00 + 11·1·00·01 = 14 bits

Lectura: la figura usa un código fijo ilustrativo para explicar por qué un codebook modular puede ser más eficiente que uno global cuando la caminata queda atrapada dentro de módulos. No es todavía el valor exacto de la Map Equation optimizada, sino una simplificación didáctica de la intuición de compresión.

Matiz
Infomap no optimiza modularidad y por tanto no hereda directamente el límite de resolución de Q. Aun así, puede exhibir otros sesgos de escala según la dinámica y la red analizada.
09
LP

Label Propagation (LPA)

Raghavan, Albert & Kumara (2007): \(O(m)\) por iteración. En la práctica converge en pocas rondas (típicamente \(T\leq5\) en redes con estructura clara), pero la convergencia no está formalmente garantizada.

Regla de actualización (asincrónica)
\[\ell_i\leftarrow\arg\max_\ell\sum_{j\in N(i)}\mathbb{1}[\ell_j=\ell]\]

Cada nodo adopta la etiqueta más frecuente entre sus vecinos. Altamente no determinista: distintas ejecuciones producen particiones distintas. Reportar siempre el promedio de múltiples runs.

Lectura (izquierda): el nodo bridge (n2) recibe 2 votos de A (P,P) y 1 voto de B (Q) — la mayoría local (2>1) gana. Lectura (derecha): si el bridge actualiza primero (round 0 aún), ve empate entre 3 etiquetas distintas y puede elegir la de B — contaminando toda la comunidad A. Por eso se requieren R≥100 runs.

Regla de votación: el nodo puente adopta la mayoría local
Votación en nodo bridge (nodo 2) n2 bridge n0 P 1 voto n1 P 1 voto n3 Q 1 voto P:2 votos > Q:1 voto → n2 adopta P No-determinismo si n2 actualiza primero Round 0: n0=P, n1=Q, n2=R, n3=S Si n2 va PRIMERO: ve {P,Q,S} → empate → elige S (etiqueta de B) Luego n0 ve {Q, S} → empate → S Luego n1 ve {S, S} → S gana A puede migrar a B en esa corrida Solución: R≥100 runs + co-clasificación
10
SB

Stochastic Block Model (SBM)

En el enfoque SBM, la detección de comunidades puede formularse como un problema de inferencia bayesiana o de inferencia estadística sobre particiones latentes. Eso permite cuantificar incertidumbre y estudiar límites fundamentales de detectabilidad.

SBM Bernoulli básicoCada nodo \(v\) se asigna a un bloque \(\sigma_v\in\{1,\ldots,k\}\) según una distribución previa \(p\). Condicional en \(\sigma\), las aristas son independientes y \(P(A_{uv}=1)=W_{\sigma_u\sigma_v}\).
Degree-Corrected SBM (Karrer & Newman, 2011)
\[A_{ij}\sim \mathrm{Poisson}\!\left(\theta_i\theta_j\,\omega_{\sigma_i\sigma_j}\right)\]
Umbral de Kesten–Stigum — SBM disperso, simétrico, 2 bloques iguales
\[(a-b)^2>2(a+b)\;\;\text{(detección débil posible)}\]
SBM: proceso generativo W → grafo; inferencia: grafo → W, σ
Matriz W (parámetro) 1.0 .04 .00 .04 1.0 .04 .00 .04 1.0 A B C A B C → genera Grafo generado A ← infiere Parámetros inferidos σ (bloques asignados): n0,n1,n2,n3 → A n4,n5,n6,n7 → B Ŵ estimada (MLE): Ŵ[A][A] = 1.00 Ŵ[A][B] = 0.063 Selección k: automática k=3 (minimiza MDL)

Lectura: La matriz W (izquierda) tiene diagonal dominante: bloques del mismo color se conectan con alta probabilidad (verde intenso), bloques distintos muy raramente (celdas casi vacías). La flecha "genera" produce el grafo observado. La flecha "infiere" es el proceso inverso: dados solo los nodos y aristas (sin colores), recuperamos W y σ. Los colores se "descubren" automáticamente.

Límite
En el SBM disperso, simétrico y de 2 bloques iguales, el umbral de Kesten–Stigum marca una barrera información-teórica: por debajo de ella no puede recuperarse la partición mejor que azar.
11
Rb

Robustez de Comunidades

Evaluar una partición comunitaria no es solo reportar \(Q\). En esta unidad conviene separar al menos tres preguntas. Concordancia externa: si existe una partición de referencia \(\mathcal{T}\), ¿qué tan cerca queda la partición estimada \(\hat{\mathcal{C}}\)? Acuerdo entre soluciones: si corro el algoritmo con distintas semillas, distintos parámetros de resolución o distintos niveles de una jerarquía, ¿las particiones resultantes se parecen entre sí? Estabilidad local: ¿qué pares de nodos permanecen juntos de manera consistente y cuáles quedan en zonas de frontera? NMI y ARI sirven para comparar particiones dos a dos; la matriz de co-clasificación resume estabilidad par-a-par sobre muchas corridas.

Tabla de contingencia entre dos particiones
\[ N_{ij}=|A_i\cap B_j|,\quad a_i=\sum_jN_{ij},\quad b_j=\sum_iN_{ij},\quad \sum_{ij}N_{ij}=n \]

Si \(\mathcal{A}=\{A_i\}\) y \(\mathcal{B}=\{B_j\}\) son dos particiones del mismo conjunto de nodos, la tabla \(N_{ij}\) resume cómo se redistribuyen esos nodos entre ambas. Ese es el objeto básico detrás de NMI y ARI: las etiquetas nominales pueden permutarse, pero la estructura de solapamiento entre bloques permanece. Si las corridas no incluyen exactamente los mismos nodos —por filtrado, missing data o preprocesamiento distinto—, estas métricas ya no son directamente comparables sin alinear antes el universo de nodos.

1 — NMI y ARI para comparar particiones

NMI — Danon et al. (2005)
\[ \text{NMI}(\mathcal{A},\mathcal{B})=\frac{-2\sum_{ij}N_{ij}\ln\!\left(\tfrac{N_{ij}N}{N_iN_j}\right)}{\sum_iN_i\ln\!\left(\tfrac{N_i}{N}\right)+\sum_jN_j\ln\!\left(\tfrac{N_j}{N}\right)} \]

NMI mide cuánta información comparten dos particiones. Vale \(1\) cuando son idénticas y se acerca a \(0\) cuando son casi independientes. Si una de las dos particiones es una referencia externa, NMI se interpreta como concordancia con esa referencia. Si ambas provienen de distintas semillas, distintos valores del parámetro de resolución \(\gamma\), distintos cortes jerárquicos o incluso distintos algoritmos sobre el mismo grafo, NMI se interpreta como acuerdo entre soluciones. En ese segundo uso, un NMI alto no prueba que la solución sea “correcta”; solo indica que las particiones comparadas son parecidas. Su limitación principal es que no corrige por acuerdo esperado al azar: particiones muy finas o sobre-fragmentadas pueden mantener NMI moderada aunque el error estructural ya sea importante.

Adjusted Rand Index (ARI) — Hubert & Arabie (1985)
\[ \text{Sean }S_R=\sum_{ij}\tbinom{n_{ij}}{2},\quad S_A=\sum_i\tbinom{a_i}{2},\quad S_B=\sum_j\tbinom{b_j}{2},\quad S_N=\tbinom{n}{2} \] \[ \text{ARI}=\frac{S_R-S_AS_B/S_N}{\tfrac{1}{2}(S_A+S_B)-S_AS_B/S_N} \]

ARI compara pares de nodos: pregunta cuántos pares quedan juntos en ambas particiones y cuántos quedan separados en ambas, corrigiendo ese acuerdo por el valor esperado bajo el modelo nulo de Hubert–Arabie con tamaños marginales fijos. Por eso ARI \(\approx 0\) significa “acuerdo no mejor que azar” en ese esquema, ARI \(=1\) indica coincidencia exacta y valores negativos significan desacuerdo mayor que el esperado. Igual que NMI, ARI puede usarse tanto contra una referencia externa como entre salidas de distintas semillas o escalas. La diferencia es interpretativa: sin referencia externa, ARI mide reproducibilidad o consistencia entre soluciones, no exactitud. En redes con comunidades de tamaños desiguales, ARI suele castigar con más fuerza una gran fusión errónea o una fragmentación masiva que NMI.

Matiz
NMI y ARI no exigen un benchmark sintético para ser útiles: pueden compararse dos particiones obtenidas con distintas semillas, distintos valores de \(\gamma\), distintas escalas jerárquicas o distintos algoritmos sobre el mismo conjunto de nodos. En ese caso miden acuerdo entre soluciones, no verdad de terreno. Si existe una referencia externa —por ejemplo una partición plantada en un benchmark sintético, definido más abajo, o metadatos observados—, entonces sí pueden leerse como métricas de concordancia externa. Además, un desacuerdo fuerte entre escalas no siempre significa inestabilidad: puede reflejar una estructura genuinamente multiescala del grafo. Y, aun con acuerdo alto, ninguna de las dos métricas informa por sí sola si las comunidades son conexas, interpretables o estructuralmente plausibles.

2 — Co-clasificación cuando una sola corrida no basta

Co-assignment / co-clasificación — Monti et al. (2003)
\[ C_{ij}=\frac{\#\{r:\sigma_i^{(r)}=\sigma_j^{(r)}\}}{R},\quad C_{ij}\in[0,1] \]

La matriz \(C\) no compara contra una verdad de terreno. Resume estabilidad empírica: \(C_{ij}\) alto significa que \(i\) y \(j\) terminan juntos en la mayoría de las \(R\) corridas o perturbaciones; \(C_{ij}\) intermedio señala nodos de frontera o soluciones ambiguas; \(C_{ij}\) bajo indica separación consistente. Cuando \(C\) muestra bloques nítidos, la partición es estable. Cuando aparecen franjas difusas, lo que suele estar fallando no es un nodo aislado sino la frontera entre comunidades. En ese sentido, \(C\) es complementaria a NMI/ARI: estas últimas resumen el acuerdo a nivel de partición completa, mientras que \(C\) localiza dónde se concentra la inestabilidad.

Matiz
En Louvain, Leiden con aleatoriedad interna o LPA, \(C\) mide sobre todo estabilidad algorítmica. En un SBM inferido por MCMC, \(C\) puede aproximar una probabilidad posterior de co-pertenencia, pero solo si la cadena está bien mezclada, se tomaron suficientes muestras y se manejó correctamente el problema de label switching. Umbralizar \(C\) en \(0.5\) o \(0.7\) para producir una partición de consenso es una heurística útil, no una garantía teórica.

Si el algoritmo es completamente determinista, repetirlo sobre el mismo grafo no agrega información. En ese caso, el uso correcto de \(C\) exige introducir variabilidad controlada: bootstrap de aristas, remoción pequeña de enlaces, resampling temporal o alguna perturbación comparable del grafo.

3 — LFR Benchmark como experimento controlado

LFR Benchmark — Lancichinetti et al. (2008)
\[ P(k)\propto k^{-\tau_1},\qquad P(s)\propto s^{-\tau_2},\qquad \mu_i=\frac{k_{i,\text{ext}}}{k_i} \] \[ k_{i,\text{in}}=(1-\mu_i)k_i,\qquad k_{i,\text{ext}}=\mu_i k_i \]

El benchmark LFR (Lancichinetti–Fortunato–Radicchi) extiende el planted-partition clásico y es mucho más realista para redes complejas, porque no asume grados homogéneos ni comunidades del mismo tamaño. En cambio, genera redes con distribuciones tipo ley de potencia tanto para los grados como para los tamaños de comunidad, algo mucho más cercano a lo que se observa en muchas redes empíricas. Por eso se usa como banco de pruebas para comparar algoritmos en condiciones controladas, pero no triviales. Sigue siendo, sin embargo, un modelo sintético: sirve para evaluar recuperación frente a una verdad plantada, no para agotar toda la variedad estructural de redes observadas en la práctica.

El parámetro clave es \(\mu\), la fracción de grado externo de cada nodo. Cuando \(\mu\) es pequeño, la mayoría de las aristas permanece dentro de la comunidad plantada y la estructura es fácil de recuperar. A medida que \(\mu\) crece, la señal comunitaria se debilita. En promedio, \(\mu\approx0.5\) significa que un nodo tiene tanto grado interno como externo; eso suele volver difícil la recuperación, pero no debe leerse como un umbral universal de “sin estructura” para toda realización finita. La dificultad también depende de \(n\), del grado medio, de los exponentes \(\tau_1,\tau_2\) y del rango de tamaños comunitarios.

Protocolo
Una evaluación rigurosa con LFR no entrega un solo número, sino curvas de desempeño. La práctica estándar es: fijar \(n\), grado medio, exponente de grados \(\tau_1\), exponente de tamaños de comunidad \(\tau_2\) y rango de tamaños; barrer varios valores de \(\mu\); generar múltiples grafos por valor de \(\mu\); correr cada algoritmo con varias semillas si es estocástico; reportar media y dispersión de NMI y ARI contra la partición plantada; y, además, resumir el acuerdo entre semillas o resoluciones mediante NMI/ARI entre corridas y mediante co-clasificación, junto con chequeos estructurales como conectividad interna (Park et al., 2024).

La lectura correcta en este contexto es la siguiente: NMI y ARI resumen concordancia con la partición plantada, la matriz de co-clasificación resume estabilidad frente a aleatoriedad o perturbaciones, y LFR es el laboratorio sintético donde ambas cosas pueden medirse conjuntamente de manera controlada.

12
Tb

Tabla Comparativa

MétodoParadigmaComplejidadEscalaDetermin.Res.Limit
Greedy CNMOptim. Q\(O(md\log n)\)MedioSíSí
EspectralÁlgebra linealDepende del eigensolverBajo–MedioNo*Depende
Girvan–NewmanDivisivo\(O(m^2n)\)BajoSíSí
LouvainOptim. Q local\(O(m)\)*Muy altoNoSí
LeidenQ + refinam.\(O(m)\)*Muy altoNoSí
InfomapTeoría info.\(O(m)\) empíricoAltoNoNo directamente
LPAPropagación\(O(m)\) por rondaMuy altoNoNo directamente
SBMInf. bayesianaDepende del inferidorMedioNoNo directamente

* Louvain y Leiden suelen escalar casi linealmente en \(m\) en la práctica, pero no existe una cota simple única aplicable a todas las implementaciones.
* En métodos espectrales, la parte lineal-algebraica puede ser determinista; la etapa de \(k\)-means introduce variabilidad si se usa inicialización aleatoria.

Ref
Rf

Referencias

– –
–
–
—
Paso actual
–
∑ Fórmula clave
–
Métricas