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)?
Answer
For all definitions of entropy, you have to define an ensemble of states to define the respective probabilities (this is related, if not equivalent to the macrostate). For example when you calculate the Shannon entropy of a string, you assume an ensemble of possible strings (and their likelihood) given by the probability of certain letters in your language of choice. For a sufficiently long string, you can estimate those probabilities from the string itself and thus “bootstrap” your ensemble.
So, to do something similar for networks, you first have to define an appropriate ensemble of networks that you want to consider. These would be your “equivalent topologies”. What makes sense here depends on how you want to interpret your entropy or, from another point of view, what properties of the network you consider variable for the purpose of encoding information. One way you may want to consider are network null models a.k.a. network surrogates. There are several methods available for obtaining such¹, but note that the properties of the underlying ensemble differ and are not always obvious.
Some further remarks:
Assuming that each network is its own microstate, the Shannon and the Gibbs entropy should be equivalent, except for a constant factor.
You may want to take a look at Phys. Rev. Lett. 102, 038701, which applies thermodynamic concepts to networks, though I never found out what ensemble they are considering.
how to can we compute similarity between two networks
There are several proposals of a distance metrics for network, starting with the Euclidean distance of the adjancency matrix. Unfortunately, I do not have a good citation at hand.
For any reasonable ensemble, you end up with a gargantuan amount of networks/microstates. Therefore it is usually not feasible to empirically estimate the probability of all microstates or even a given microstate. Instead, you have to estimate the probability density for a neighbourhood of microstates. For this you need the above distance.
¹ I tried to cite all of them in the introduction of this paper of mine, but that’s not entirely up to date.
No comments:
Post a Comment