So, I had a brain fart the other day and I was curious if someone with a little more knowledge could tell me if someone tried this before and how it failed.
Basically, the problem is that sampling uniformly from graphs of certain classes of biological interest ("scale-free", "power-law") is difficult: even though it can be shown that such probability measures exist, the pmfs are egregious.
The brain fart was this: given an objective function H on some state space, under sufficiently "nice" conditions on the setup of the problem, simulated annealing converges (asymptotically) to a uniform distribution on the ground states of H (the "minimizers"). If we build an H on graph-space such that power-law graphs are in the "ground state", then we can actually use SA to sample (asymptotically) uniformly over power-law graphs.
The choice of H seems to be the kicker, but it doesn't seem impossible---for example, letting H be the sup-norm of the difference between the empirical degree distribution and the best-fit power-law, perhaps with some suitable transform applied that takes everything within an epsilon-ball of zero to zero, seems like a reasonable choice that has the requisite properties.
So, I had a brain fart the other day and I was curious if someone with a little more knowledge could tell me if someone tried this before and how it failed.
Basically, the problem is that sampling uniformly from graphs of certain classes of biological interest ("scale-free", "power-law") is difficult: even though it can be shown that such probability measures exist, the pmfs are egregious.
The brain fart was this: given an objective function H on some state space, under sufficiently "nice" conditions on the setup of the problem, simulated annealing converges (asymptotically) to a uniform distribution on the ground states of H (the "minimizers"). If we build an H on graph-space such that power-law graphs are in the "ground state", then we can actually use SA to sample (asymptotically) uniformly over power-law graphs.
The choice of H seems to be the kicker, but it doesn't seem impossible---for example, letting H be the sup-norm of the difference between the empirical degree distribution and the best-fit power-law, perhaps with some suitable transform applied that takes everything within an epsilon-ball of zero to zero, seems like a reasonable choice that has the requisite properties.