Measures on vertices and edges in a social network

Abstract

Aquest treball utilitza la teoria de grafs i la teoria de jocs per estudiar xarxes socials modelades com a grafs signats, amb un enfocament en la clusterabilitat. Després de presentar els jocs de disrupció i estudiar els índexs de poder de Banzhaf i Shapley-Shubik en els vèrtexs, es proposen 6 mesures sobre les arestes. Totes elles tenen com a objectiu mesurar la importància d’una aresta en fer que un graf signat no sigui "clusteritzable" (agrupable en clústers). Tanmateix, provenen de fonts d'inspiració diferents i també es comporten de manera diversa. El càlcul d’aquests índexs de poder per a tots els grafs signats connexos de 4 vèrtexs ens permet identificar, i en alguns casos demostrar, certes relacions entre ells.

Este trabajo utiliza la teoría de grafos y la teoría de juegos para estudiar redes sociales modeladas como grafos signados, con un enfoque en la clusterabilidad. Tras presentar los juegos de disrupción y estudiar los índices de poder de Banzhaf y Shapley-Shubik en los vértices, se proponen 6 medidas sobre las aristas. Todas ellas tienen como objetivo medir la importancia de una arista en hacer que un grafo signado no sea "clusterizable" (agrupable en clústers). Sin embargo, provienen de distintas fuentes de inspiración y también se comportan de manera diferente. El cálculo de estos índices de poder para todos los grafos signados conexos de 4 vértices nos permite identificar, y en algunos casos demostrar, ciertas relaciones entre ellos.

This work uses graph theory and game theory to study social networks modeled as signed graphs, focusing on clusterability. After presenting the disruption games and studying the Banzhaf and Shapley- Shubik power indices on vertices, 6 measures on edges are proposed. All of them aim to measure the importance of an edge in making a signed graph non-clusterable. However, they come from different sources of inspiration and they behave differently too. The computations of these power indices for all signed connected graphs of 4 vertices allow us to identify and prove, in some cases, some relations between them.