Agrupamiento (teoría de grafos)

En teoría de grafos y análisis de redes sociales, el agrupamiento o agrupabilidad[1]​ (en inglés, clustering) es una propiedad de un grafo o red social, que generaliza la noción de equilibrio estructural.

Los niveles de agrupabilidad se pueden cuantificar a través de coeficientes de agrupamiento. De estos conceptos han derivado en la actualidad diversos algoritmos de agrupamiento utilizados en minería de datos.

Historia

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]​

Definición formal

Grafo signado desequilibrado pero agrupable, porque de sus 9 ciclos, ninguno tiene una sola arista negativa. Los 4 agrupamientos posibles son , , y , pudiendo unirse .

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]​

Teorema 1. Un grafo signado no dirigido es agrupable si y sólo si no contiene ciclos con exactamente una arista negativa.
(si el grafo es dirigido, reemplazar «ciclos» por «semiciclos»)


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]​

Teorema 2. Dado un grafo signado no dirigido completo, las siguientes aseveraciones son equivalentes:

  • El grafo es agrupable.
  • El grafo tiene un agrupamiento único.
  • El grafo no tiene ningún ciclo con exactamente una arista negativa.
  • El grafo no tiene ningún ciclo de longitud 3 con exactamente una arista negativa.

(si el grafo es dirigido, reemplazar «ciclo» por «semiciclo»)


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 (ambas relaciones positivas), que conectan dos nodos de un mismo nivel y en un mismo agrupamiento (o camarilla);
  • Díadas (ambas relaciones negativas), que conectan dos nodos de un mismo nivel pero de distinto agrupamiento;
  • Díadas (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.


Problema de agrupamiento

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]​

Coeficiente de agrupamiento

Artículo principal: Coeficiente de agrupamiento

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]​

Véase también

Referencias

  1. ↑ a b c d e f g h i j k l Wasserman y Faust, 2013, «Equilibrio estructural y transitividad», pp. 241-268.
  2. ↑ Harary, F. (1953). «On the notion of balance of a signed graph». Michigan Mathematical Journal 2 (2): 143-146. doi:10.1307/mmj/1028989917. 
  3. ↑ Davis, J. A. (1967). «Clustering and structural balance in graphs». Human Relations 20 (2): 181-187. doi:10.1177/001872676702000206. 
  4. ↑ Davis, J. A. (1968). «Social structures and cognitive structures». En Abelson, R. P.; Aronson, E.; W. J. McGuire; Newcomb, T. M.; Rosenberg, M. J.; Tannenbaum, O. H., eds. Theories of cognitive consistency. Chicago: Rand McNally. 
  5. ↑ Leinhardt, S. (1968). The development of structure in the interpersonal relations of children. Tesis doctoral, Departamento de Sociología, Universidad de Chicago. 
  6. ↑ Leinhardt, S. (1972). «Development change in the sentiment structure of children's groups». American Sociological Review 37 (2): 202-212. doi:10.2307/2094028. 
  7. ↑ a b Davis, J. A.; Leinhardt, S. (agosto de 1968). «The structure of positive interpersonal relations in small groups». 1968 Annual Meeting of the American Sociological Association. Boston, Massachusetts. 
  8. ↑ a b Davis, J. A.; Leinhardt, S. (1972). «The structure of positive interpersonal relations in small groups». En Berger, J., ed. Sociological Theories in Progress. Boston: Houghton Mifflin. 
  9. ↑ Davis, J. A. (1970). «Clustering and hierarchy in interpersonal relations: Testing two theoretical models on 742 sociograms». American Sociological Review 35 (5): 843-852. doi:10.2307/2093295. 
  10. ↑ Cartwright, D.; Harary, F. (1970). «Ambivalence and indifference in generalizations of structural balance». Behavioral Science 15 (6): 497-513. doi:10.1002/bs.3830150604. 
  11. ↑ Kaplan, K. J. (1972). «On the ambivalence-indifference problem in attitude theory and measurement: A suggested modification in the semantic differential technique». Psychological Bulletin 77 (5): 361-372. doi:10.1037/h0032590. 
  12. ↑ Holland, P. W.; Leinhardt, S. (1971). «Transitivity in structural models of small groups». Comparative Group Studies 2 (2): 107-124. doi:10.1177/104649647100200201. 
  13. ↑ Cartwright, D.; Harary, F. (1956). «Structural balance: A generalization of Heider's theory». Psychological Review 63 (5): 277-292. doi:10.1037/h0046049. 
  14. ↑ Harary, F.; Norman, R. Z.; Cartwright, D. (1965). Structural models: An introduction to the theory of directed graphs. Nueva York: John Wiley and Sons. 
  15. ↑ Cartwright, D.; Harary, F. (1979). «Balance and clusterability: An overview». En Holland, P. W.; Leinhardt, S., eds. Perspectives on social network research. Nueva York: Academic Press. 
  16. ↑ Cartwright, D.; Harary, F. (1968). «On the coloring of signed graphs». Elemente der Mathematik 23: 85-89. 

Bibliografía

  • 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.