Aleatorización que preserva el grado

La aleatorización que preserva el grado es una técnica utilizada en la ciencia de redes que tiene como objetivo evaluar si las variaciones observadas en un grafo dado podrían ser simplemente un artefacto de las propiedades estructurales inherentes del grafo, en lugar de propiedades únicas de los nodos, en una red observada.

Catalogada ya en 1996, ^{[ 1 ]} la implementación más simple de aleatorización que preserva el grado se basa en un algoritmo de Monte Carlo que reorganiza, o "reconecta", la red al azar de tal manera que, con un número suficiente de reconectaciones, la distribución de grados de la red es idéntica a la distribución de grados inicial de la red, aunque la estructura topológica de la red se ha vuelto completamente distinta de la red original.

La aleatorización que preserva el grado, si bien tiene muchas formas diferentes, generalmente adopta la forma de un enfoque relativamente simple: para cualquier red que consta de${\displaystyle N}$nodos con${\displaystyle E}$Seleccione dos nodos vinculados diádicamente. Para cada uno de estos pares diádicos, intercambie las aristas de manera que los nuevos pares diádicos no coincidan. Tras un número suficiente de estos desajustes, la red irá perdiendo progresivamente su topografía original observada.

Como es común con los algoritmos basados ​​en cadenas de Markov , se desconoce el número de iteraciones, o reconfiguraciones individuales, que deben ocurrir en un grafo dado para que el grafo sea suficientemente aleatorio y distinto del grafo original, aunque Espinoza ^{[ 2 ]} afirma que un umbral mínimo seguro es${\displaystyle QE}$, dónde${\displaystyle Q}$"es al menos 100" (Espinoza). Otros han aportado información sobre este tema, incluido un autor que afirma que un mínimo seguro podría ser al menos${\displaystyle {\frac {E}{2}}\cdot \ln(1/\varepsilon )}$, dónde${\displaystyle 10^{-7}\leq \varepsilon \leq 10^{-6}}$, aunque en última instancia el valor correcto de${\displaystyle \varepsilon }$Actualmente se desconoce. ^{[ 3 ] [ 4 ]}

Hay varios casos en los que la investigación publicada ha empleado explícitamente la aleatorización que preserva el grado para analizar las propiedades de la red. Dekker ^{[ 5 ]} utilizó la reconfiguración para modelar con mayor precisión las redes sociales observadas mediante la adición de una variable secundaria,${\displaystyle \pi }$, lo que introduce un sesgo de apego de alto grado. Liu et al. ^{[ 6 ]} han empleado además la aleatorización que preserva el grado para afirmar que la Centralidad de Control , una métrica que identifican, cambia poco en comparación con la Centralidad de Control de un modelo de Erdős-Rényi que contiene el mismo número de${\displaystyle N}$nodos en sus simulaciones - Liu et al. también han utilizado modelos de aleatorización que preservan el grado en trabajos posteriores que exploran la controlabilidad de la red . ^{[ 7 ]}

Además, se ha realizado algún trabajo para investigar cómo se puede utilizar la aleatorización que preserva el grado para abordar las consideraciones de anonimato en la investigación de datos en red, lo cual se ha demostrado que es motivo de preocupación en el análisis de redes sociales , como en el caso de un estudio de Lewis et al. ^{[ 8 ] [ 9 ]} En última instancia, el trabajo realizado por Ying y Wu, partiendo de una base de aleatorización que preserva el grado y luego proponiendo varias modificaciones, ha mostrado avances moderados en la protección del anonimato sin comprometer la integridad de la utilidad subyacente de la red observada. ^{[ 10 ]}

Además, el método es similar a los modelos de grafos aleatorios exponenciales ampliamente utilizados y popularizados en las ciencias sociales, ^{[ 11 ] [ 12 ]} y, de hecho, a las diversas formas de modelar redes comparándolas con redes observadas para identificar y teorizar sobre las diferencias expresadas en redes reales. Es importante destacar que la aleatorización que preserva el grado proporciona un diseño algorítmico simple para que quienes estén familiarizados con la programación puedan aplicar un modelo a una red observada disponible.

A continuación se presenta un pequeño ejemplo que muestra cómo se puede aplicar la aleatorización que preserva el grado a una red observada, con el fin de comprenderla frente a variaciones aleatorias, manteniendo al mismo tiempo la distribución de grados de la red. La Asociación de Investigadores de Internet (AIIMS ) cuenta con una lista de correo que constituye la mayor parte de los hilos de discusión relacionados con su trabajo. En ella, los miembros publican actualizaciones sobre sus investigaciones, próximas conferencias, convocatorias de artículos y participan en debates sustanciales sobre su campo. Estos correos electrónicos pueden, a su vez, constituir un grafo de red dirigido y temporal, donde los nodos son cuentas de correo electrónico individuales pertenecientes a la lista y las aristas son casos en los que una dirección de correo electrónico responde a otra en la misma lista.

En esta red observada, las propiedades de la lista de correo son relativamente fáciles de calcular: para una red de 3235 cuentas de correo electrónico individuales y 9824 intercambios en total, la reciprocidad observada de la red es de aproximadamente 0,074, y la longitud media de la ruta es de aproximadamente 4,46. ¿Podrían estos valores derivarse simplemente de la naturaleza de la estructura inherente de la red?

Aplicando el${\displaystyle {\frac {E}{2}}\cdot \ln(1/\varepsilon )}$Según la regla general, esta red requeriría aproximadamente 67.861 reconfiguraciones de aristas individuales para construir un grafo con grado preservado suficientemente aleatorio. Si construimos muchos grafos aleatorios que preservan el grado a partir del grafo real, podemos crear un espacio de probabilidad para características como la reciprocidad y la longitud media del camino, y evaluar hasta qué punto la red podría haber expresado estas características al azar. Se generaron 534 redes utilizando la aleatorización con preservación del grado. Dado que tanto la reciprocidad como la longitud media del camino en este grafo siguen una distribución normal, y que la desviación estándar para ambas es demasiado estrecha para incluir el caso observado, podemos suponer razonablemente que esta red expresa características no aleatorias (y, por lo tanto, susceptibles de mayor análisis teórico y modelado).

• Conjunto de datos proporcionado como ejemplo