Agrupamiento (teoria de grafos)

En teoria de grafos i anàlisis de rets socials, el agrupamiento o agrupabilidad (en inglés: clustering) és una propietat d'un grafo o ret social, que generalisa la noció d'equilibri estructural.

Els nivells de agrupabilidad es poden quantificar a través de coeficients de agrupamiento. D'estos conceptes han derivat en l'actualitat diversos algoritmes de agrupamiento utilisats en mineria de senyes.

Història

Harary (1953) va demostrar que en un grafo signado equilibrat, els actors o vèrtiços poden particionarse en dos subgrups, agrupacions o clusters, de modo que dins de cada subgrup els actors es relacionen positivament, i entre abdós subgrups, tots es relacionen negativament. No obstant, Davis (1967) va corroborar empíricamente que en la realitat les rets o grafos no solen estar equilibrades, i per tant posseïxen més de dos agrupamientos. D'esta manera, va propondre la noció de agrupamiento com una generalisació del concepte d'equilibri. Si ben la seua generalisació es va enfocar inicialment en els grafos complets, els seus resultats es poden estendre fàcilment a grafos incomplets.

Poc despuix, entre 1968 i 1973, distints investigadors varen reunir casi 800 rets socials per a verificar empíricamente si el agrupamiento de Davis sobre grafos signados era suficientment expressiu per a l'estudi de casos reals. Els resultats varen revelar que moltes de les rets eren dirigides, en varis nodos apuntant a uns atres pero sense que estos uns atres apuntaren a ells de regrés, per lo que els resultats principals de agrupabilidad considerant semiciclos no semblaven ser suficients. Ademés, varen descobrir que les relacions signadas eren poc comuns. En este context, Davis y Leinhardt (1968) varen propondre els «conglomerats per rancs» per a considerar agrupabilidad en dígrafs signados complets;Cartwright y Harary (1970) i Kaplan (1972) varen ampliar el concepte per a grafos ponderats signados, i Holland y Leinhardt (1971) per a dígrafs no signados.

Definició formal

Erro al crear miniatura:

Grafo signado desequilibrat pero agrupable, perque dels seus 9 cicles, cap té una sola aresta negativa. Els 4 agrupamientos possibles són $\{b,d,f\}$, $\{a\}$, $\{c\}$ i $\{e\}$, podent unir-se $\{a,e\}$.

Un grafo signado és agrupable o té agrupamiento si els seus nodos es poden dividir en un número finito de subconjunts (cridats agrupamientos o clusters) tals que les aresta positives del grafo conecten a nodos en un mateix subconjunt, i les arestes negatives conecten a nodos en subconjunts distints.

En general, el següent resultat caracterisa als grafos agrupables d'acort als cicles que conté:

Un grafo signado és vacuamente agrupable si no posseïx cicles ni semiciclos; és agrupable llimitat si complix les condicions de la Teorema 1 per a cicles de llongitut 3, pero no per a cicles de llongitut major, i és S-agrupable si posseïx S agrupamientos.

Note que tot grafo signado equilibrat és agrupable, i té com a molt dos agrupamientos; és dir, és 2-agrupable. Ademés, dit tipo de grafos no admeten cicles signados negatius de llongitut 3 conformats únicament per arestes negatives. El concepte de agrupabilidad és més general que el d'equilibri estructural, perque sí accepta este tipo de cicles. Si el grafo és complet, per a testear el seu agrupabilidad solament basta considerar els cicles de llongitut 3:

Si el grafo és complet, al seu únic agrupamiento també se'ls coneix com clique o caçola.

L'última asseveració de la Teorema 2 explica l'importància de les tríades en l'anàlisis de rets socials i els actuals algoritmes de agrupamiento. Si es relaixa la condició de relacions no dirigides (o simètriques) a dirigides (o asimètriques), igualment basta centrar-se solament en les tríades, com es pot vore en el concepte d'agrupamiento per rancs.

Agrupamiento per rancs

Vore també: Agrupamiento jeràrquic

Erro al crear miniatura:

Les 16 tríades possibles per a agrupamiento per rancs en dígrafs signados complets.

El agrupamiento per rancs (en anglés, ranked clusterability), també conegut com l'estudi de conglomerats per rancs, és una relaixació de la agrupabilidad per a dígrafs signados complets, que admet agrupamientos o conglomerats en nivells jeràrquics distints. De forma anàloga a l'última asseveració de la Teorema 2, en este cas basta considerar únicament les tríades del grafo. Aixina com en grafos no dirigits hi ha huit tríades possibles, en este cas són setze, dins de les quals solament es poden donar tres tipos de díadas, distribuïdes en dos nivells o rancs diferents depenent dels seus signes:

• Díadas $\mathtt{\text{++}}$ (abdós relacions positives), que conecten dos nodos d'un mateix nivell i en un mateix agrupamiento (o caçola);
• Díadas $\mathtt{\text{--}}$ (abdós relacions negatives), que conecten dos nodos d'un mateix nivell pero de distint agrupamiento;
• Díadas $\mathtt{\text{+-}}$ (relacions opostes), que conecten dos nodos de distint nivell i agrupamiento, sent el que rep la relació positiva el que està en el agrupamiento de més alt nivell.

Vore també

• Equilibri estructural
• Algoritme de agrupamiento
• Coeficient de agrupamiento
• Anàlisis de grups

Bibliografia

• (2013) Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques. OCLC 871814053. ISBN 978-84-7476-631-8.