I wonder if we can obtain asymptotic results in the same manner...
I wonder if we can obtain asymptotic results in the same manner...
A related [question](https://mathoverflow.net/questions/384683/random-permutations-without-double-rises-avoiding-consecutive-pattern-underli/384947#384947) on Mathoverflow.
A related [question](https://mathoverflow.net/questions/384683/random-permutations-without-double-rises-avoiding-consecutive-pattern-underli/384947#384947) on Mathoverflow.
The article provides an extension of Boltzmann sampling to the realm of labeled combinatorial structures, enumerated by exponential generating functions and constructed using the box product.
----
[Boltzmann sampling](https://en.wikipedia.org/wiki/Boltzmann_sampler) is a general, pretty fast, technique for generate uniformely random combinatorial structures specified by structural equations.
The key idea of Boltzmann sampling can be illustrated by the following example.
Suppose you have a generating function
$$f(x) = x + x^2 + x^2 + x^3 + x^3 + x^3 + x^3 + x^4 ...$$
corresponding to the one object of size one, two objects of size 2, four objects of size 3, etc.
If you set, for example, $x = \frac{1}{2}$ then
$$f\left(\frac{1}{2}\right) = \frac{1}{2} + \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^4 ...$$
Now let's take $x$ such that $f(x) < \infty$, and chose an integer $k$. As you think, it quickly becomes clear that you can use this to chose a random object of size $k$. The probability equals precisely $\frac{x^k}{f(x)}$. For a given $k$ it is uniform.
The elaboration of this idea in the context of structural equations (a.k.a. recursive decompositions, [symbolic method](https://en.wikipedia.org/wiki/Symbolic_method_%28combinatorics%29)) leads you to Boltzmann sampling technique. And knowing the values of generating functions together with corresponding recursive decompositions will allow you to generate a random object according to a uniform probability measure for any size. Shifting $x$ you will shift the mean size of a generating object.
See [Boltzmann Samplers For The Random Generation Of Combinatorial Structures](https://www.researchgate.net/publication/2562585_Boltzmann_Samplers_For_The_Random_Generation_Of_Combinatorial_Structures) paper
by Duchon, Flajolet, Louchard and Schaeffer for such elaboration.
The article provides an extension of Boltzmann sampling to the realm of labeled combinatorial structures, enumerated by exponential generating functions and constructed using the box product.
----
[Boltzmann sampling](https://en.wikipedia.org/wiki/Boltzmann_sampler) is a general, pretty fast, technique for generate uniformely random combinatorial structures specified by structural equations.
The key idea of Boltzmann sampling can be illustrated by the following example.
Suppose you have a generating function
$$f(x) = x + x^2 + x^2 + x^3 + x^3 + x^3 + x^3 + x^4 ...$$
corresponding to the one object of size one, two objects of size 2, four objects of size 3, etc.
If you set, for example, $x = \frac{1}{2}$ then
$$f\left(\frac{1}{2}\right) = \frac{1}{2} + \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^4 ...$$
Now let's take $x$ such that $f(x) < \infty$, and chose an integer $k$. As you think, it quickly becomes clear that you can use this to chose a random object of size $k$. The probability equals precisely $\frac{x^k}{f(x)}$. For a given $k$ it is uniform.
The elaboration of this idea in the context of structural equations (a.k.a. recursive decompositions, [symbolic method](https://en.wikipedia.org/wiki/Symbolic_method_%28combinatorics%29)) leads you to Boltzmann sampling technique. And knowing the values of generating functions together with corresponding recursive decompositions will allow you to generate a random object according to a uniform probability measure for any size. Shifting $x$ you will shift the mean size of a generating object.
See [Boltzmann Samplers For The Random Generation Of Combinatorial Structures](https://www.researchgate.net/publication/2562585_Boltzmann_Samplers_For_The_Random_Generation_Of_Combinatorial_Structures) paper
by Duchon, Flajolet, Louchard and Schaeffer for such elaboration.
See also these 2 related questions on MathOverflow:
https://mathoverflow.net/questions/384683/random-permutations-without-double-rises
https://mathoverflow.net/questions/14863/random-alternating-permutations
See also these 2 related questions on MathOverflow:
https://mathoverflow.net/questions/384683/random-permutations-without-double-rises
https://mathoverflow.net/questions/14863/random-alternating-permutations
Hello, are you aware of any open source implementation of this algorithm ?
Hello, are you aware of any open source implementation of this algorithm ?
Some nice presentations on the topic:
- https://www.irif.fr/~habib/Documents/cours_4-2015.pdf
- http://igm.univ-mlv.fr/AlgoB/algoperm2012/04Paul.pdf
- http://www.lirmm.fr/~paul/Talks/talk-06-algo-sem-McGill.pdf
Some nice presentations on the topic:
- https://www.irif.fr/~habib/Documents/cours_4-2015.pdf
- http://igm.univ-mlv.fr/AlgoB/algoperm2012/04Paul.pdf
- http://www.lirmm.fr/~paul/Talks/talk-06-algo-sem-McGill.pdf
>See table 3 from https://arxiv.org/abs/1811.10705
This is with $n=50$ nodes. It seems that the behavior is not the same for $n$ large:
- I think that in a large ER, if the proba of connection $p$ is not too large or too small, then it is rare to find a group of nodes with the same neighbors outside the group (i.e. find a module). Can you prove that?
- I don't think that the code https://github.com/antonovvk/decmod is buggy.
>See table 3 from https://arxiv.org/abs/1811.10705
This is with $n=50$ nodes. It seems that the behavior is not the same for $n$ large:
- I think that in a large ER, if the proba of connection $p$ is not too large or too small, then it is rare to find a group of nodes with the same neighbors outside the group (i.e. find a module). Can you prove that?
- I don't think that the code https://github.com/antonovvk/decmod is buggy.
[Almost all finite graphs are asymmetric](https://en.wikipedia.org/wiki/Asymmetric_graph#Random_graphs). There is no pair of vertices with common neighborhood.
[Almost all finite graphs are asymmetric](https://en.wikipedia.org/wiki/Asymmetric_graph#Random_graphs). There is no pair of vertices with common neighborhood.
Comments: