17.4: Agrupación

Última actualización
Guardar como PDF

Page ID: 115771

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

La excentricidad, las centralidades y la coreza introducidas sobre todo dependen de toda la topología de la red (excepto la centralidad de grado). En este sentido, capturan algunos aspectos macroscópicos de la red, a pesar de que estamos calculando esas métricas para cada nodo. En contraste, existen otros tipos de métricas que solo capturan propiedades topológicas locales. Esto incluye métricas de agrupamiento, es decir, cuán densamente conectados están los nodos entre sí en un área localizada en una red. Hay dos métricas ampliamente utilizadas para esto:

Coeficiente de agrupamiento

\[C(i) = \frac{| \begin{Bmatrix} \begin{Bmatrix} j,k \end{Bmatrix}| d(i,j) =d(i,k) = d(j,k) =1 \end{Bmatrix} |}{ deg(i) (deg(i)-1)/2 } \label{(17.25)} \]

El denominador es el número total de pares de nodos posibles dentro de$i$ la vecindad del nodo, mientras que el numerador es el número de pares de nodos realmente conectados entre ellos. Por lo tanto, el coeficiente de agrupamiento del nodo$i$ calcula la probabilidad de que sus vecinos también sean vecinos de los demás. Tenga en cuenta que esta métrica asume que la red no está dirigida. El siguiente coeficiente de agrupamiento promedio se usa a menudo para medir el nivel de agrupación en clústeres en toda la red:

\[C =\frac{\sum_{i} {C(i)}}{n} \label{(17.26)} \]

Transitividad

\[C_{T} =\frac{| \begin{Bmatrix} (i,j,k)| d(i,j) =d(i,k) =d(j,k) =1 \end {Bmatrix}|}{ | \begin{Bmatrix} (i,j,k )| d(i,j) =d(i,k) =1| \end{Bmatrix} }\label{(17.27)} \]

Esto es muy similar a los coeficientes de agrupamiento, pero se define contando tripletes de nodos conectados en toda la red. El denominador es el número de tripletes de nodo conectados (es decir, un nodo$i$,, y dos de sus vecinos,$j$ y$k$), mientras que el numerador es el número de dichos tripletes donde también$j$ está conectado$k$. Esto captura esencialmente el mismo aspecto de la red que el coeficiente de agrupamiento promedio, es decir, cuán localmente agrupada está la red, pero la transitividad también se puede calcular en redes dirigidas. También trata cada triángulo de manera más uniforme, a diferencia del coeficiente de agrupamiento promedio que tiende a subestimar la contribución de tripletes que involucran nodos altamente conectados.

Nuevamente, calcular estas métricas de clustering es muy fácil en NetworkX:

$Código 17.11.PNG$

Ejercicio$\PageIndex{1}$

Generar (1) una red aleatoria Erd"os-R'enyi, (2) una red de mundo pequeño WattsStrogatz, y (3) una red Barab'asi-Albert libre de escala de tamaño y densidad comparables, y compararlos con respecto a cuán localmente agrupados están.

El coeficiente de agrupamiento fue introducido por primera vez por Watts y Strogatz [56], donde mostraron que sus redes de pequeños mundos tienden a tener una agrupación muy alta en comparación con sus contrapartes aleatorias. El siguiente código replica su experimento computacional, variando la probabilidad de recableado$p$:

$Código 17.12.PNG$

$Código 17.12 pt2.PNG$

$Código 17.12 pt3.PNG$

El resultado se muestra en la Fig. 17.4.1, donde la longitud de ruta característica (L) y el coeficiente de agrupamiento promedio (C) se trazan como sus fracciones a los valores basales (L0, C0) obtenidos de una red puramente regular g0. Como puede ver en la figura, la red se vuelve muy pequeña (L baja) pero permanece altamente agrupada (C alta) en el valor intermedio de p alrededor$10^{−2}$. Este es el régimen de parámetros donde surgen las redes de pequeños mundos de Watts-Strogatz

Figura$\PageIndex{1}$: Salida visual del Código 17.12.