Model de blocs estocàstics

Un exemple del cas assortit per al model de blocs estocàstics.

El model de blocs estocàstics és un model generatiu per a gràfics aleatoris. Aquest model tendeix a produir gràfics que contenen comunitats, subconjunts de nodes caracteritzats per estar connectats entre si amb densitats de vores particulars. Per exemple, les vores poden ser més freqüents dins de comunitats que entre comunitats. La seva formulació matemàtica va ser introduïda per primera vegada el 1983 en el camp de les xarxes socials per Holland et al. El model de blocs estocàstics és important en l'estadística, l'aprenentatge automàtic i la ciència de xarxes, on serveix com a punt de referència útil per a la tasca de recuperar l'estructura de la comunitat en dades de gràfics.

El model de blocs estocàstics pren els paràmetres següents:

• El nombre $n$ de vèrtexs;
• una partició del conjunt de vèrtexs $\{1,\dots ,n\}$ en subconjunts discontinus $C_1,\dots ,C_r$, anomenades comunitats;
• un simètric $r\times r$ matriu $P$ de probabilitats de vora.

El conjunt d'arestes es mostra aleatòriament de la següent manera: dos vèrtexs qualsevol $u\in C_i$ i $v\in C_j$ estan connectats per una aresta amb probabilitat $P_{ij}$. Un exemple de problema és: donat un gràfic amb $n$ vèrtexs, on es mostren les vores tal com es descriu, recupereu els grups $C_1,\dots ,C_r$.

Gran part de la literatura sobre detecció algorítmica de comunitats aborda tres tasques estadístiques: detecció, recuperació parcial i recuperació exacta.

Detecció: L'objectiu dels algorismes de detecció és simplement determinar, donat un gràfic mostrat, si el gràfic té una estructura de comunitat latent. Més precisament, es podria generar un gràfic, amb alguna probabilitat prèvia coneguda, a partir d'un model de blocs estocàstics conegut i, en cas contrari, a partir d'un model Erdos-Renyi similar. La tasca algorítmica és identificar correctament quin d'aquests dos models subjacents ha generat el gràfic.

Recuperació parcial: En la recuperació parcial, l'objectiu és determinar aproximadament la partició latent en comunitats, en el sentit de trobar una partició que estigui correlacionada amb la partició veritable significativament millor que una suposició aleatòria.

Recuperació exacta: En la recuperació exacta, l'objectiu és recuperar exactament la partició latent en comunitats. Les mides de la comunitat i la matriu de probabilitats poden ser conegudes o desconegudes.