Agrupamiento (teoría de grafos)

Harary (1953) demostró que en un grafo signado equilibrado, los actores o vértices pueden particionarse en dos subgrupos, agrupaciones o clusters, de modo que dentro de cada subgrupo los actores se relacionan positivamente, y entre ambos subgrupos, todos se relacionan negativamente.[2] Sin embargo,Davis (1967) corroboró empíricamente que en la realidad las redes o grafos no suelen estar equilibradas, y por tanto poseen más de dos agrupamientos.[3][4] De este modo, propuso la noción de agrupamiento como una generalización del concepto de equilibrio. Si bien su generalización se enfocó inicialmente en los grafos completos, sus resultados se pueden extender fácilmente a grafos incompletos.[1]

Poco después, entre 1968 y 1973, distintos investigadores reunieron casi 800 redes sociales para verificar empíricamente si el agrupamiento de Davis sobre grafos signados era suficientemente expresivo para el estudio de casos reales. Los resultados revelaron que muchas de las redes eran dirigidas, con varios nodos apuntando a otros pero sin que estos otros apuntasen a ellos de vuelta, por lo que los resultados principales de agrupabilidad considerando semiciclos no parecían ser suficientes. Además, descubrieron que las relaciones signadas eran poco comunes.[5][6][7][8][9] En este contexto,Davis y Leinhardt (1968) propusieron los «conglomerados por rangos» para considerar agrupabilidad en dígrafos signados completos;Cartwright y Harary (1970) y Kaplan (1972) ampliaron el concepto para grafos ponderados signados,[10][11] y Holland y Leinhardt (1971) para dígrafos no signados.[12][1]

Grafo signado desequilibrado pero agrupable, porque de sus 9 ciclos, ninguno tiene una sola arista negativa. Los 4 agrupamientos posibles son ${\displaystyle \{b,d,f\}}$, ${\displaystyle \{a\}}$, ${\displaystyle \{c\}}$ y ${\displaystyle \{e\}}$, pudiendo unirse ${\displaystyle \{a,e\}}$.

Un grafo signado es agrupable o tiene agrupamiento si sus nodos se pueden dividir en un número finito de subconjuntos (llamados agrupamientos o clusters) tales que las arista positivas del grafo conectan a nodos en un mismo subconjunto, y las aristas negativas conectan a nodos en subconjuntos distintos.[1]

En general, el siguiente resultado caracteriza a los grafos agrupables de acuerdo a los ciclos que contiene:[1]

Un grafo signado es vacuamente agrupable si no posee ciclos ni semiciclos;[13] es agrupable limitado si cumple las condiciones del Teorema 1 para ciclos de longitud 3, pero no para ciclos de longitud mayor,[14] y es S-agrupable si posee S agrupamientos.[15]

Note que todo grafo signado equilibrado es agrupable, y tiene a lo sumo dos agrupamientos; es decir, es 2-agrupable. Además, dicho tipo de grafos no admiten ciclos signados negativos de longitud 3 conformados únicamente por aristas negativas. El concepto de agrupabilidad es más general que el de equilibrio estructural, porque sí acepta este tipo de ciclos.[1] Si el grafo es completo, para testear su agrupabilidad solo basta considerar los ciclos de longitud 3:[1]

Si el grafo es completo, a su único agrupamiento también se les conoce como clique o camarilla.[1]

La última aseveración del Teorema 2 explica la importancia de las tríadas en el análisis de redes sociales y los actuales algoritmos de agrupamiento. Si se relaja la condición de relaciones no dirigidas (o simétricas) a dirigidas (o asimétricas), igualmente basta centrarse solo en las tríadas, como se puede ver en el concepto de agrupamiento por rangos.

Agrupamiento por rangos

Véase también: Agrupamiento jerárquico

Las 16 tríadas posibles para agrupamiento por rangos en dígrafos signados completos.

El agrupamiento por rangos (en inglés, ranked clusterability), también conocido como el estudio de conglomerados por rangos,[1] es una relajación de la agrupabilidad para dígrafos signados completos, que admite agrupamientos o conglomerados en niveles jerárquicos distintos. De forma análoga a la última aseveración del Teorema 2, en este caso basta considerar únicamente las tríadas del grafo.[7] Así como en grafos no dirigidos hay ocho tríadas posibles, en este caso son dieciséis, dentro de las cuales solo se pueden dar tres tipos de díadas, distribuidas en dos niveles o rangos diferentes dependiendo de sus signos:[8]

• Díadas ${\displaystyle {\texttt {++}}}$ (ambas relaciones positivas), que conectan dos nodos de un mismo nivel y en un mismo agrupamiento (o camarilla);
• Díadas ${\displaystyle {\texttt {--}}}$ (ambas relaciones negativas), que conectan dos nodos de un mismo nivel pero de distinto agrupamiento;
• Díadas ${\displaystyle {\texttt {+-}}}$ (relaciones opuestas), que conectan dos nodos de distinto nivel y agrupamiento, siendo el que recibe la relación positiva el que está en el agrupamiento de más alto nivel.

Dado un grafo signado, el problema de agrupamiento o problema de agrupabilidad consiste en determinar cuántos agrupamientos tiene. Si el grafo es completo, para corroborar si es agrupable basta con revisar sus ciclos de longitud 3, pero para los demás grafos, se puede revisar primero los ciclos de longitud 3, luego los de longitud 4, y así sucesivamente; si en algún momento se encuentra un ciclo con exactamente una arista negativa, entonces el grafo no será agrupable y no es necesario seguir verificando los ciclos restantes.[1]

Este problema está relacionado con el problema de coloración de grafos, donde los agrupamientos son representados como colores.[16][1]

El grado de agrupabilidad de un grafo signado se puede cuantificar mediante índices de agrupabilidad o coeficientes de agrupamiento, de manera análoga al índice de equilibrio usado en equilibrio estructural. Existen índices que consideran las aristas, o bien los (semi-)ciclos del grafo.[1]

• Equilibrio estructural
• Algoritmo de agrupamiento
• Coeficiente de agrupamiento
• Análisis de grupos

• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053.