Conectividad y descentralización en componentes

Sistemas descentralizados y el estado invisible: Cohesión multiconectada de baja densidad en Redes Sociales de gran escala en Tlaxcala, México

Douglas R. White, Michael Schnegg, y Lilyan A. Brudner 1999
Este material está basado en trabajo apoyado por la National Science Foundation con la subvención No. 9978282.

Tabla 2:	Nivel de conectividad (generando subgrupos limitados)
Conceptos de Cohesión	1-Componente Conectado (1-)	2-Conectado (bicomponente)	3-Conectado (tricomponente)	...	k-Conectado (k-componente)
Escala de Cohesión:	Vulnerable a desconexión	Potencialmente gran escala, Baja densidad	Agrupados dentro de bicomponentes	...	Jerárquicamente agrupado

Definición 1: A un (1) componente de una red (o grafo) es un conjunto máximo de nodos y arcos tales que cada par de nodos está conectado tres componentes (desconectado).
Definición 2: Una de dos componentes de una red (o grafo) es un conjunto máximo de nodos y arcos tales que cada par de nodos está conectado por dos o más caminos independientes (tres subgrafos gris claro).
Definición 3: Una de tres componentes de una red (o grafo) es un conjunto máximo de nodos y arcos tales que cada par de nodos está conectado por tres o más caminos independientes (subgrafo gris).
Definición General 4: Un k-componente de una red (o grafo) es un conjunto máximo de nodos y arcos de tal manera que cada par de nodos está conectado por k o más caminos independientes (no hay ejemplos anteriores para k> 2).

Las hipótesis generales:
(a) Biconectividad es una fuente de emergente, potencialmente descentralizada de cohesión social que puede ocurrir (con efectos observables) a baja densidad en (los bicomponentes de) las redes sociales relativamente estable.

(b) Esto es especialmente cierto para las relaciones que tienen muy alta "moneda" o de soporte vital relevancia, como las relaciones de poder político, la transmisión de la propiedad, o el parentesco y conexiones matrimoniales.

(c) Por lo tanto, la clase social, las élites, y los sistemas de matrimonio riqueza transmisión están especialmente bien adaptados para el análisis.

• Una red descentralizada con biconectividad puede tener efectos más cohesionadas que una red centralizada o una mayor escala de cohesión de grupos localmente más cohesivos.
• El mecanismo es el potencial para los circuitos de retroalimentación positiva auto-amplificación o.
• Además, cuanto mayor es la conectividad ("redundancia"), menos vulnerabilidad a la desconexión. Máxima conectividad = minimo punto de corte (eliminación mínima de nodo para la desconexión): el teorema de Menger.
• Por lo tanto, la energía, la información o los recursos pueden circular o redistribuidos en mayores k-componentes con mayor eficacia.
• Bicomponentes son fáciles de identificar en gráficos grandes en o tiempo lineal (max (V, E)), V = vértices, E = bordes.
• Bicomponentes no son "cerrados", pero irradian lazos hacia el exterior en los patrones conectivo con forma de árbol, posiblemente 1-conectados a otros bicomponentes. Los nodos en su perímetro pueden incluso ser más central en la gráfica general (nodo 9, en el ejemplo, se conecta dos bicomponentes).
• En una red grande con suficiente (pero a menudo bajo) densidad, un gigante de dos componentes puede ser la fuente de la participación fuertemente cohesionada en ámbitos institucionales principales del grupo (aunque no todo el mundo biconexas por relaciones de alto divisas tendrá alta cohesión). Otros pueden ser 1-conectado al componente gigante. Esto da lugar a una estructura de tres partes:
• el núcleo biconexas gigante 
• su periferia, 1 conectado con el núcleo gigante  
• los márgenes, en separadas 1-componentes
• Conexiones dentro de una de dos componentes no necesitan ser homogénea: las interacciones locales o k-componentes de orden superior dentro bicomponentes pueden dar lugar a otras propiedades globales o subgrupo emergentes.
• k-componentes de orden superior también son fácilmente computable: tricomponents en o tiempo lineal (V + E) [Hopcroft y Tarjan 1973], y todos los k-componentes en baja polinomio tiempo o (. V ** 5 ** E 2) [Aun y Tarjan 1975] o en tiempo casi lineal en computación paralela.

(d) la evolución dinámica de 1-conectividad y biconectivitdad (y conectividades de orden superior que tienen ambos efectos globales "gigante" de componentes y efectos de interacción localizadas) puede dar lugar a transiciones de fase en las configuraciones de red (un posible ejemplo: la co-evolución de los estados y mercados en la Florencia renacentista).


Fuente