Núcleo-periferia, k-core y organización de soporte

COMPLEXA · Ciencias de la Complejidad y Teoría del Caos
Módulo 19. Arquitecturas de redes y modelos generativos

185.1. Tener muchos vecinos y disponer de soporte colectivo

Un nodo puede conectar con numerosas hojas que solo dependen de él. Su grado es alto, pero ninguna de esas hojas contribuye a una organización densamente interconectada. Otra red puede contener un grupo pequeño cuyos integrantes mantienen varias conexiones entre sí. Cada nodo tiene menos vecinos que el centro de la estrella, aunque pertenece a una estructura de soporte recíproco más exigente. Las dos situaciones requieren medidas diferentes.

La expresión núcleo-periferia suele describir una arquitectura en la que una parte de la red mantiene relaciones densas o centrales, mientras otra participa de manera menos interconectada. El significado exacto depende del modelo. Puede interesar una concentración de enlaces, una posición en rutas, una dependencia funcional o un patrón de intercambio entre bloques. Llamar «núcleo» a todos esos objetos no los convierte en la misma estructura.

El concepto de $k$-core, que procede del análisis de grado mínimo de Seidman (1983), permite una definición precisa. Un $k$-core es el subgrafo inducido máximo en el que cada nodo tiene al menos $k$ vecinos dentro del propio subgrafo. La condición es colectiva; un nodo con muchos vecinos en la red original puede quedar fuera, porque algunos de ellos pueden quedar excluidos al aplicar el mismo requisito a todos.

En una estrella, las hojas tienen grado uno. Para buscar un dos-core se retiran y el centro pierde todos sus vecinos. La estructura completa desaparece. En un triángulo, cada nodo conserva dos vecinos dentro del grupo, por lo que los tres sobreviven. El grado del centro de una estrella enorme puede superar ampliamente al de cualquier nodo del triángulo; la pertenencia al dos-core responde a otra pregunta.

Esta descomposición es útil cuando importa la participación en un conjunto que se sostiene mediante conexiones internas. También puede usarse como resumen estructural, incluso sin una interpretación dinámica. Para hablar de soporte funcional hay que justificar que la cantidad de vecinos mide realmente recursos o condiciones de funcionamiento. Un enlace puede registrar amistad, transferencia o correlación; esos significados no implican necesariamente el mismo mecanismo de mantenimiento.

Examinaremos la eliminación iterativa que define los $k$-cores, un ejemplo completo de ocho nodos y la diferencia con los modelos de núcleo-periferia. Después estudiaremos cómo una pérdida pequeña puede desencadenar una cascada bajo una regla de soporte y por qué esa cascada no equivale necesariamente a desconectar la red. La distinción permitirá usar la estructura sin atribuirle propiedades dinámicas aún no especificadas.

185.2. La definición y sus consecuencias

Sea un grafo simple no dirigido $G=(V,E)$. Para un conjunto de nodos $S\subseteq V$, el subgrafo inducido conserva todos los enlaces originales cuyos dos extremos pertenecen a $S$. El grado interno de un nodo cuenta solo vecinos dentro de ese conjunto. El $k$-core es el mayor conjunto en el que todos los integrantes tienen grado interno de al menos $k$.

La palabra «mayor» puede precisarse por inclusión. Si dos conjuntos cumplen la condición, su unión también la cumple, porque cada nodo conserva al menos los vecinos que tenía dentro de su conjunto original. Por tanto, existe un único conjunto máximo, aunque pueda estar vacío.

El $k$-core puede estar desconectado. Dos triángulos separados forman juntos el dos-core de su unión. Si interesa una región conectada de soporte, deben examinarse las componentes del core. Confundir la pertenencia al mismo nivel de core con la accesibilidad mutua llevaría a una conclusión falsa incluso en este ejemplo elemental.

Los conjuntos están anidados. Todo nodo que pertenece al core de grado mínimo $k+1$ pertenece también al de grado mínimo $k$. El número de core de un nodo, que denotaremos $c_i$, es el mayor $k$ para el que sobrevive. Los nodos aislados tienen número cero y las hojas, uno. El máximo de estos números es la degeneración del grafo.

La cota $c_i\leq k_i$ es inmediata, porque el grado interno no puede superar al grado original. La desigualdad puede ser muy amplia, como muestra el centro de la estrella. Un nodo de grado alto puede tener número de core bajo si sus vecinos no conservan suficientes conexiones entre sí o con otros nodos que sobrevivan al proceso.

Pertenecer a un $k$-core tampoco exige estar en un clique de tamaño $k+1$. Un ciclo largo es un dos-core y no contiene triángulos. Las condiciones de grado mínimo permiten soporte distribuido a través de una estructura extensa, mientras que un clique impone que cada pareja esté conectada, una exigencia mucho más fuerte.

La definición no depende de una disposición gráfica. Un nodo dibujado en el centro puede tener número de core uno y otro situado en un extremo de la figura puede pertenecer al core más alto. Los algoritmos de visualización suelen colocar los nodos según fuerzas artificiales o criterios de legibilidad. La posición en la imagen puede ayudar a explorar una red, pero la pertenencia se calcula a partir de los enlaces.

185.3. Eliminar nodos sin perder la condición correcta

Para obtener un $k$-core se eliminan repetidamente los nodos cuyo grado dentro del conjunto actual es menor que $k$. Al retirarlos, disminuyen los grados de sus vecinos y pueden aparecer nuevas violaciones. El procedimiento termina cuando todos los nodos restantes cumplen el requisito o cuando no queda ninguno. La iteración es esencial, porque una sola revisión de los grados originales puede retener nodos inválidos.

El resultado final es independiente de cualquier orden admisible de eliminación. Un nodo que tiene menos de $k$ vecinos en el conjunto actual no puede pertenecer a ningún $k$-core contenido en él, de modo que retirarlo no excluye una solución válida. Repetir ese argumento muestra que todos los nodos eliminados debían quedar fuera y que el conjunto final es precisamente el máximo buscado.

La independencia del resultado no implica que todas las historias intermedias sean iguales. Si se retiran simultáneamente los nodos inválidos, pueden contarse rondas de eliminación. Si se procesan uno a uno, la secuencia depende de la elección y del orden de actualización. Una duración medida en rondas paralelas no debe compararse directamente con el número de operaciones de un algoritmo secuencial.

El proceso puede implementarse con una cola de nodos por debajo del umbral. Al retirar uno, se actualizan solo sus vecinos aún presentes; con estructuras adecuadas no hace falta recalcular todos los grados. Para obtener la descomposición completa hay procedimientos que ordenan los nodos por grados residuales y calculan sus niveles de core de manera eficiente.

La lógica del algoritmo debe conservar la diferencia entre grado residual y número de core. Durante una eliminación secuencial, un nodo puede quedar con grado pequeño porque otros de su mismo nivel ya fueron procesados. Tomar ese último grado como su nivel puede subestimar su pertenencia. Una implementación correcta mantiene el nivel de eliminación o usa las actualizaciones apropiadas para la descomposición completa.

En redes pequeñas, la verificación puede hacerse de forma independiente. Para cada umbral se comprueba que todos los nodos retenidos tienen suficientes vecinos internos y que ningún conjunto mayor puede satisfacerlo. La segunda condición se apoya en la historia de eliminaciones. La comparación con ejemplos conocidos, como árboles, ciclos y cliques, detecta errores frecuentes sin depender de una visualización.

Los árboles con al menos una arista tienen degeneración uno, porque siempre tienen hojas y la búsqueda de un dos-core acaba vaciándolos. Un ciclo tiene degeneración dos y un clique de $q$ nodos, $q-1$. Estas referencias muestran que la medida describe una forma específica de cohesión interna, distinta del tamaño total o del grado máximo observado.

185.4. Una descomposición completa de ocho nodos

Construyamos una red cuyo centro contiene un clique de cuatro nodos, numerados del uno al cuatro. El nodo cinco se conecta con uno y dos. El nodo seis se conecta solo con cinco. El siete se conecta con uno y con ocho. No hay otros enlaces. Los grados iniciales son cinco, cuatro, tres, tres, tres, uno, dos y uno, respectivamente.

Todos los nodos pertenecen al uno-core porque no hay aislados. Para buscar el dos-core, primero se retiran seis y ocho, que tienen un solo vecino. Al desaparecer ocho, el siete queda conectado únicamente con uno y también debe retirarse. El nodo cinco pierde a seis, pero conserva sus conexiones con uno y dos. El conjunto final contiene los cinco primeros nodos.

Al buscar el tres-core, el nodo cinco no puede sobrevivir después de retirar seis, porque solo le quedan dos vecinos. El siete y el ocho tampoco cumplen el requisito. Una vez eliminados esos nodos, permanece el clique de cuatro, donde cada integrante tiene exactamente tres vecinos. Ese conjunto es el tres-core.

No existe cuatro-core. Aunque uno y dos tenían grados originales de cinco y cuatro, parte de sus conexiones terminaba en nodos que no podían satisfacer el umbral. El clique restante tiene grado interno tres y se elimina por completo al exigir cuatro.

El nodo cinco y los nodos tres y cuatro comparten grado original, pero pertenecen a niveles distintos. El cinco tiene una de sus conexiones con una hoja que no contribuye al tres-core, mientras que los otros dos mantienen sus tres vecinos dentro de un grupo que satisface colectivamente el requisito. La diferencia no se observa al examinar únicamente el número de enlaces de cada nodo.

Otra discrepancia es la del siete, que tiene grado dos y no pertenece al dos-core. Uno de sus vecinos es una hoja y la pérdida de esa hoja lo deja sin soporte suficiente. El cálculo detecta una dependencia encadenada que no aparece en una revisión local de un solo paso.

La descomposición permite formular preguntas precisas, como qué enlaces conectan niveles, qué atributos se distribuyen en cada uno o cómo cambia la pertenencia bajo perturbaciones. Todavía no indica que los nodos del nivel tres sean los más útiles para una intervención; esa evaluación dependerá del proceso que se quiera modificar, de la posibilidad de actuar sobre cada nodo y del resultado que se pretenda mejorar.

185.5. Núcleo-periferia y k-core no son equivalentes

Los modelos de núcleo-periferia de Borgatti y Everett (2000) modelan patrones de relaciones entre posiciones estructurales. Una forma idealizada contiene un núcleo densamente conectado, una periferia con pocos enlaces internos y numerosas relaciones entre ambos. El patrón describe una división de la red y las densidades de sus bloques. La descomposición en cores usa, en cambio, un requisito de grado interno aplicado a todos los nodos retenidos.

La diferencia puede mostrarse con una red ideal de nueve nodos. Tres forman un clique central. Los otros seis no se conectan entre sí, pero cada uno se conecta con los tres centrales. Los nodos centrales tienen grado ocho y los periféricos, grado tres. Por sus densidades, la arquitectura núcleo-periferia es muy marcada; el bloque periférico está vacío, mientras el central y el cruzado están completos.

Sin embargo, todos los nodos tienen número de core tres. La red completa satisface ese grado mínimo. Al exigir cuatro, se retiran los seis periféricos y los tres centrales quedan con grado dos, por lo que también desaparecen. La descomposición no separa los dos papeles estructurales porque mide una propiedad distinta de la división entre bloques.

El ejemplo impide usar ambos términos como sinónimos. Un núcleo denso puede depender de conexiones con la periferia para alcanzar cierto grado mínimo; una periferia muy conectada al núcleo puede compartir su número de core. La palabra «central» también puede aludir a rutas o a capacidad de intermediación, que no intervienen directamente en ninguno de esos requisitos de densidad.

Una red puede contener varios núcleos o una organización gradual sin una partición binaria clara. Forzar dos grupos puede ocultar módulos densos separados o posiciones intermedias. Algunos modelos asignan valores continuos de pertenencia; otros comparan estructuras de bloques alternativas. La elección debe justificarse por la pregunta y contrastarse con referencias que conserven la heterogeneidad relevante de grados.

La densidad del núcleo tampoco establece una dirección de dependencia. Si los enlaces registran suministro, la periferia puede abastecer al centro de recursos esenciales. Si registran demanda, la actividad central puede existir precisamente porque atiende a los nodos periféricos. La descripción topológica no determina quién sostiene funcionalmente a quién; para saberlo hay que conocer qué circula por las relaciones.

Para comunicar resultados conviene nombrar la medida exacta (número de core, pertenencia a un bloque denso, intermediación o posición en un modelo núcleo-periferia). La precisión permite comparar métodos sin esperar que produzcan siempre la misma clasificación. Sus desacuerdos pueden revelar aspectos complementarios de la arquitectura; leerlos como errores de cálculo presupone una centralidad única.

La misma red de nueve nodos permite comprobar otra diferencia. Si retiramos un nodo periférico, los ocho restantes siguen formando un tres-core. Si retiramos uno central, cada periférico queda con solo dos vecinos; todos salen y los dos centrales restantes tampoco pueden sostener el umbral. La pérdida final es completa. Todos los nodos tenían el mismo número de core, pero su eliminación tiene efectos distintos. Esta asimetría surge de cómo se distribuye el soporte, una información que la etiqueta individual de pertenencia no recoge.

185.6. Soporte mínimo y cascadas de retirada

La eliminación que define un core puede interpretarse como una dinámica bajo condiciones específicas. Supongamos que cada nodo permanece activo únicamente si conserva al menos $k$ vecinos activos y que, una vez desactivado, no vuelve a activarse. Si todos comienzan activos, el conjunto final coincide con el $k$-core. Una retirada inicial de nodos se modela aplicando el mismo procedimiento al subgrafo que queda.

La regla describe un requisito mínimo de soporte, pero su pertinencia debe justificarse. Puede aproximar un proceso donde una organización necesita varios proveedores activos o una actividad depende de suficientes participantes. Si los recursos son sustituibles, tienen intensidades desiguales o pueden almacenarse, contar vecinos puede ser insuficiente.

Un clique de cuatro nodos satisface un umbral tres. Si se elimina una sola arista, sus dos extremos quedan con grado dos y se desactivan. Los dos nodos restantes pierden soporte y también se retiran. El tres-core desaparece por completo, aunque el grafo sin esa arista sigue conectado. El criterio de soporte con ese umbral es más exigente que el de conectividad.

Si el umbral fuera dos, la misma eliminación no destruiría el conjunto, porque todos conservarían al menos dos vecinos. El resultado depende del requisito funcional supuesto. Informar que la red es «frágil» sin especificar frente a qué perturbación y bajo qué regla mezcla propiedades que pueden cambiar de manera independiente.

Las cascadas pueden ampliarse cuando una eliminación reduce los grados de nodos cercanos al umbral, que a su vez dejan a otros sin soporte. El tamaño final de la retirada depende del número de nodos eliminados al inicio, de su posición y de la distribución de márgenes de soporte. Un grupo con grados muy superiores al umbral puede absorber pérdidas que desestabilizan a otro de igual tamaño situado justo en el límite.

La dinámica deja de coincidir con el core ordinario si se permite recuperación, si los umbrales cambian o si aparecen enlaces nuevos durante el proceso. Un nodo desactivado podría volver a funcionar después de recibir apoyo externo. Una regla con activación y desactivación puede producir estados dependientes de la historia o actividad variable. El resultado del proceso monotónico sigue siendo una referencia útil, aunque no tiene por qué representar esas extensiones.

El análisis de daño aleatorio puede estudiar distribuciones de tamaños del core bajo un mecanismo de pérdida definido. El daño dirigido a nodos de cierta posición plantea otra pregunta. Compararlos ayuda a separar vulnerabilidad promedio y exposición a perturbaciones específicas. No debe elegirse una forma de ataque solo porque produzca el mayor colapso si ese mecanismo no es plausible en el sistema considerado.

185.7. Cohesión interna, conectividad y rutas alternativas

Un número de core elevado garantiza un mínimo de vecinos internos, pero no que el conjunto sea difícil de separar en grandes regiones. Dos cliques de cuatro nodos unidos por una sola arista tienen todos sus nodos en el tres-core. La arista que los une es un puente. El soporte local de cada clique no produce redundancia en la conexión entre ambos.

En procesos que necesitan coordinación global, cada grupo puede sostener actividad internamente mientras el intercambio entre grupos depende de un enlace. Retirar ese enlace conserva los dos tres-cores y destruye la accesibilidad mutua. Una medida basada solo en tamaños de cores podría no registrar la pérdida de comunicación que interesa al problema.

La conectividad por vértices o por aristas mide cuántos elementos deben retirarse para separar el grafo. Las componentes biconexas y los puntos de articulación describen otras formas de soporte de rutas. No son intercambiables con el grado mínimo, aunque existan relaciones y cotas entre estas propiedades. La pregunta debe determinar qué vulnerabilidad se calcula.

La densidad media tampoco reemplaza el requisito local. Un grupo puede tener una zona muy densa y varios nodos apenas conectados y, aun así, una densidad promedio alta; el core elimina los que no alcanzan el mínimo interno. Por el contrario, una red extensa con grado mínimo moderado puede ser un core grande y tener baja densidad respecto de todas las parejas posibles. El tamaño cambia la relación entre densidad y cantidad de vecinos.

Las distancias internas pueden ser largas incluso dentro de un dos-core. Un ciclo de miles de nodos satisface el requisito, pero entre dos posiciones opuestas hay que recorrer muchos enlaces. Si el proceso exige respuestas rápidas, además de la existencia del core deben incorporarse longitudes, velocidades o tiempos de transmisión compatibles con la dinámica.

También puede haber heterogeneidad funcional dentro de un mismo nivel. En el ejemplo de ocho nodos, los cuatro del clique comparten número tres, pero uno recibe más conexiones externas que los demás. Si esas conexiones transportan demanda o perturbaciones, su exposición difiere. El core clasifica soporte interno y deja abierta la distribución de cargas y relaciones hacia fuera.

Una caracterización útil puede combinar el nivel de core con componentes, puentes y flujos. La combinación debe responder a preguntas concretas; acumular métricas no garantiza comprensión. Si interesa mantener conectadas dos regiones, se estudian sus rutas; si interesa sostener actividad con un umbral de apoyo, se examina el core correspondiente. La misma red puede ser resistente bajo un criterio y vulnerable bajo otro.

185.8. Direcciones, pesos y signos modifican el requisito

En redes dirigidas puede exigirse un mínimo de entradas y otro de salidas dentro del conjunto. Un nodo que recibe muchas conexiones y no envía ninguna cumple una función diferente de uno que mantiene ambas formas de participación. Un core dirigido con umbrales $(k_{\mathrm{ent}},k_{\mathrm{sal}})$ retiene únicamente nodos que satisfacen los dos requisitos después de las eliminaciones correspondientes.

Simetrizar antes del cálculo puede ocultar esa distinción. Una cadena de suministro orientada podría parecer un conjunto conectado con soporte suficiente al ignorar las flechas, aunque algunos nodos carezcan de proveedores internos o de destinos. Si la función exige ambas cosas, deben conservarse las direcciones. Si solo interesa la existencia de contacto, la simetrización puede ser adecuada, pero responde a otra pregunta.

Los pesos no negativos permiten sustituir el requisito de grado por uno de fuerza interna. Cada nodo necesita que la suma de magnitudes de sus enlaces dentro del conjunto alcance un umbral. El procedimiento sigue siendo monotónico, porque al retirar nodos la fuerza interna de los restantes no aumenta. La eliminación iterativa conserva una interpretación de soporte acumulado, siempre que sumar pesos sea pertinente.

El umbral de fuerza tiene unidades. Si los pesos son transferencias por semana, exigir una suma de diez significa diez unidades por semana. Cambiar la ventana temporal sin ajustar el umbral modifica la selección. También hay que distinguir cantidad total y diversidad de fuentes; un nodo sostenido por un único proveedor intenso puede superar el umbral de fuerza y fallar un requisito de varios vecinos independientes.

Los signos requieren más cuidado. Si se suman pesos positivos y negativos, retirar un vecino inhibidor puede aumentar la suma interna. La monotonía usada para justificar la eliminación deja de ser válida, de modo que el algoritmo del core positivo no puede trasladarse directamente a un criterio firmado. Puede ser necesario definir requisitos separados para apoyo y antagonismo o especificar una dinámica que determine cómo se combinan.

En redes con varios tipos de enlace, puede exigirse soporte en cada capa. Un nodo quizá necesite proveedores, personal y comunicación, sin que una abundancia de un recurso compense la ausencia de otro. La eliminación puede propagarse entre capas porque la actividad de un nodo conecta esos requisitos. El modelo debe declarar qué recursos son complementarios y cuáles sustituibles.

Estas extensiones muestran que el core es una familia de construcciones basada en una regla de pertenencia. Su interpretación mejora cuando la regla se expresa en términos observables y conserva las propiedades matemáticas que usa el algoritmo. Cambiar de grado a fuerza o añadir signos puede alterar las unidades, la monotonía y el significado del soporte.

185.9. Estabilidad de la clasificación ante datos incompletos

Un enlace ausente puede reducir el grado interno de varios nodos a través de una cascada de eliminación. Por ello, el error en el número de core no siempre queda localizado en los extremos del enlace omitido. El caso extremo es el clique de cuatro con umbral tres, en el que perder una sola relación en el registro elimina todo el core aunque el sistema real mantenga sus seis aristas.

La sensibilidad depende del margen respecto del umbral. Si muchos nodos tienen exactamente $k$ vecinos dentro de un $k$-core, pequeñas pérdidas pueden alterar su pertenencia. Si disponen de bastante más soporte, algunas omisiones no cambian el resultado. Examinar esos márgenes da información que el número de core no contiene.

Cuando los enlaces se estiman estadísticamente, una opción es calcular la descomposición en varias redes compatibles con la incertidumbre de los datos. Puede informarse la frecuencia de pertenencia a cada nivel o la variación del tamaño del core. Esa frecuencia describe estabilidad bajo el modelo de incertidumbre usado; no equivale necesariamente a una probabilidad objetiva de que el nodo sea esencial.

La elección de un umbral para binarizar pesos también puede producir saltos. Un enlace apenas por debajo del corte desaparece por completo, aunque sea casi indistinguible de otro apenas por encima. Comparar un intervalo de umbrales justificados ayuda a localizar clasificaciones frágiles. La persistencia de un resultado en muchas variantes es informativa solo si esas variantes corresponden a incertidumbres o decisiones plausibles.

La cobertura de nodos importa tanto como la de enlaces. Un subgrafo inducido omite conexiones hacia nodos externos, por lo que los números de core dentro de él no pueden superar los que tendrían esos nodos en el grafo completo sin cambios de aristas. La restricción puede hacer desaparecer soporte que pasa fuera de la muestra. Comparar regiones con coberturas distintas exige reconocer esa asimetría.

Si se agregan nodos o se proyecta una red bipartita, la relación anterior deja de aplicarse directamente. Una proyección puede crear cliques entre todos los participantes de un mismo evento y elevar artificialmente la cohesión aparente respecto de una interpretación de interacción directa. El core de la proyección describe la red proyectada; su significado depende de que esas conexiones representen el soporte que se quiere estudiar.

185.10. Elegir una intervención según el mecanismo

Supongamos que el objetivo es conservar el grupo de cuatro nodos del ejemplo inicial bajo un requisito de tres apoyos internos. Ese grupo está justo en el límite, con exactamente tres vecinos por integrante. Añadir una conexión desde un miembro a una hoja no lo protege frente al mismo proceso, porque la hoja no puede satisfacer el umbral. El grado original aumenta, pero el soporte colectivo del tres-core permanece igual.

Una intervención eficaz bajo esa regla tendría que incorporar apoyo que también sobreviva al requisito o modificar el umbral funcional. Puede añadirse un nuevo nodo conectado a suficientes integrantes y capaz de cumplir su propia condición. Puede introducirse un recurso externo que se modele explícitamente como apoyo independiente. Cada posibilidad cambia el sistema de una manera distinta y debe evaluarse con sus costos y restricciones.

Si el objetivo fuera mantener comunicación entre dos cliques, reforzar el puente o crear otra ruta podría ser prioritario aunque no cambie ningún número de core. Si interesara reducir tiempos de viaje, quizá convendría un atajo. Por eso el nodo de core más alto no tiene por qué ser el mejor objetivo de intervención.

La descripción final debería indicar qué conjunto se encontró, qué requisito cumple y cómo varía bajo perturbaciones pertinentes. También debe distinguir el resumen estructural de la hipótesis funcional que lo usa. Un core es una propiedad bien definida del grafo; un sistema que se mantiene gracias a cierto número de apoyos es un modelo de proceso. Vincular ambos permite obtener predicciones comprobables y reconocer cuándo la arquitectura disponible no basta para resolver la pregunta.

Referencias

Borgatti, S. P. y Everett, M. G. (2000). Models of core/periphery structures. Social Networks, 21(4), 375–395. DOI.

Seidman, S. B. (1983). Network structure and minimum degree. Social Networks, 5(3), 269–287. DOI.