También pregunté en SO aquí hace unos días, pensé que también podría ser interesante para respuestas relacionadas con la física.
Me gustaría modelar una red como un sistema. Una topología particular (configuración de aristas entre vértices) es un estado de orden del sistema (un microestado). Estoy tratando de calcular la entropía de una topología específica como medida de la complejidad de la información incrustada en esa estructura topológica.
No tengo un título en física, me gustaría tener respuestas que puedan ayudar a crear un concepto de entropía aplicado a las redes (en particular, las redes de mundo pequeño), como sistemas que incorporan información en su topología.
A continuación, comparto mis razonamientos y dudas.
Primero pensé en hacer una analogía con la entropía de Shannon aplicada a cadenas: aquí la entropía es una medida de la aleatoriedad de una cadena como una suma de probabilidad de que ocurran ciertos dígitos. De manera similar, luego pensé que la entropía podría ser válida para una red aleatoria de Erdős-Rényi y que la medida podría reflejar la aleatoriedad de un borde entre un par de vértices.
Como segundo enfoque, pensé que según la definición de Boltzmann, la entropía es la multiplicidad de estados equivalentes.
¿Cómo podrían modelarse topologías equivalentes (o cómo podemos calcular la similitud entre dos redes)?
¿Cómo medir cuánto es “poco común” un estado de orden de una topología particular, con respecto a todas las demás configuraciones posibles?
¿Debo intentar modelar una topología como una probabilidad sobre todas las posibles distribuciones de bordes (red completa)?
Para todas las definiciones de entropía, debe definir un conjunto de estados para definir las probabilidades respectivas (esto está relacionado, si no es equivalente al macroestado). Por ejemplo, cuando calcula la entropía de Shannon de una cadena, asume un conjunto de posibles cadenas (y su probabilidad) dado por la probabilidad de ciertas letras en su idioma de elección. Para una cadena lo suficientemente larga, puede estimar esas probabilidades a partir de la propia cadena y, por lo tanto, "arrancar" su conjunto.
Entonces, para hacer algo similar con las redes, primero debe definir un conjunto apropiado de redes que desee considerar. Estas serían sus "topologías equivalentes". Lo que tiene sentido aquí depende de cómo quieras interpretar tu entropía o, desde otro punto de vista, qué propiedades de la red consideras variables a efectos de codificar la información. Una forma que puede considerar son los modelos nulos de red, también conocidos como sustitutos de red. Hay varios métodos disponibles para obtener tales¹, pero tenga en cuenta que las propiedades del conjunto subyacente difieren y no siempre son obvias.
Algunas observaciones adicionales:
Suponiendo que cada red es su propio microestado, la entropía de Shannon y Gibbs debería ser equivalente, excepto por un factor constante.
Es posible que desee echar un vistazo a Phys. Rev. Lett. 102, 038701 , que aplica conceptos termodinámicos a las redes, aunque nunca descubrí qué conjunto están considerando.
¿Cómo podemos calcular la similitud entre dos redes?
Hay varias propuestas de una métrica de distancia para la red, comenzando con la distancia euclidiana de la matriz de adyacencia. Desafortunadamente, no tengo una buena cita a mano.
Para cualquier conjunto razonable, terminas con una cantidad gigantesca de redes/microestados. Por lo tanto, generalmente no es factible estimar empíricamente la probabilidad de todos los microestados o incluso de un microestado dado. En cambio, debe estimar la densidad de probabilidad para una vecindad de microestados. Para esto necesitas la distancia anterior.
¹ Traté de citarlos a todos en la introducción de este artículo mío , pero eso no está del todo actualizado.