I also asked in SO here a few days ago, thought it may be also interesting for physics-related answers.
I would like to model a network as a system. A particular topology (configuration of edges between vertices) is a state-of-order of the system (a micro-state). I am trying to compute the entropy of a specific topology as a measure of the complexity of information embedded in that topological structure.
I don’t have a degree in physics, I would like to have answers that can help in creating a concept of entropy applied to networks (particularly small-world networks), as systems embedding information in their topology.
Below, I share my reasoning and doubts.
I first thought to make an analogy with Shannon entropy applied to strings: Here entropy is a measure of the randomness of a string as a sum of probability to have certain digits happenings. Similarly, I then thought that entropy may hold for an Erdős–Rényi random network, and the measure could reflect the randomness of an edge between a pair of vertexes.
- Does Shannon entropy hold for non-random types of networks?
As a second approach, I thought that according to Boltzmann’s definition, entropy is the multiplicity of equivalent states.
How could equivalent topologies be modelled (or how to can we compute similarity between two networks)?
How to measure how much a state of order of a particular topology is “uncommon”, with respect to all other possible configurations?
Should I attempt to model a topology as a probability over all possible distributions of edges (complete network)?