n_iter with parallel edges allowed

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

n_iter with parallel edges allowed

Snehal Shekatkar
Hi Tiago,

From the documentation for random_rewire : "If parallel_edges = False, parallel edges are not placed during rewiring. In this case, the returned graph will be a uncorrelated sample from the desired ensemble only if n_iter is sufficiently large."

If I set "model = 'configuration'" and "parallel_edges = True, self_loops = True", will "n_inter = 1" suffice?

Thank you
SS


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Tiago Peixoto
Administrator
Am 20.07.20 um 13:08 schrieb Snehal Shekatkar:
> If I set "model = 'configuration'" and "parallel_edges = True,
> self_loops = True", will "n_inter = 1" suffice?

Yes.

--
Tiago de Paula Peixoto <[hidden email]>
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Snehal Shekatkar
Thanks Tiago. I have a related question: suppose self-loops and multi-edges are not allowed. Now according to the documentation, graphs are generated using "Efficient Markov Chain based on edge swaps". However, I could not find the description of the algorithm in the documentation or the references therein. I have gone through the Karrer-Newman paper as well as your paper "Entropy of stochastic blockmodel ensembles", and both do not describe the algorithm about any rewiring using Markov chains. Could you kindly point me to the actual algorithm?

Thank you
SS


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Tuesday, July 21, 2020 8:31 PM, Tiago de Paula Peixoto <[hidden email]> wrote:

> Am 20.07.20 um 13:08 schrieb Snehal Shekatkar:
>
> > If I set "model = 'configuration'" and "parallel_edges = True,
> > self_loops = True", will "n_inter = 1" suffice?
>
> Yes.
>
> -------
>
> Tiago de Paula Peixoto [hidden email]
>
> graph-tool mailing list
> [hidden email]
> https://lists.skewed.de/mailman/listinfo/graph-tool


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Tiago Peixoto
Administrator
Am 22.07.20 um 08:49 schrieb Snehal Shekatkar:
> Thanks Tiago. I have a related question: suppose self-loops and multi-edges are not allowed. Now according to the documentation, graphs are generated using "Efficient Markov Chain based on edge swaps". However, I could not find the description of the algorithm in the documentation or the references therein. I have gone through the Karrer-Newman paper as well as your paper "Entropy of stochastic blockmodel ensembles", and both do not describe the algorithm about any rewiring using Markov chains. Could you kindly point me to the actual algorithm?

This is the usual edge-swapping algorithm that has been discovered and
re-discovered many times since the 50s. You can find a good description
in the recent paper: https://arxiv.org/abs/1608.00607

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Snehal Shekatkar
Thanks so much Tiago, I highly appreciate the help. I think it would be useful to put one such reference along with others in the random_rewire docs. Please consider this if it makes sense.

Thanks and regards,
SS


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Wednesday, July 22, 2020 12:47 PM, Tiago de Paula Peixoto <[hidden email]> wrote:

> Am 22.07.20 um 08:49 schrieb Snehal Shekatkar:
>
> > Thanks Tiago. I have a related question: suppose self-loops and multi-edges are not allowed. Now according to the documentation, graphs are generated using "Efficient Markov Chain based on edge swaps". However, I could not find the description of the algorithm in the documentation or the references therein. I have gone through the Karrer-Newman paper as well as your paper "Entropy of stochastic blockmodel ensembles", and both do not describe the algorithm about any rewiring using Markov chains. Could you kindly point me to the actual algorithm?
>
> This is the usual edge-swapping algorithm that has been discovered and
> re-discovered many times since the 50s. You can find a good description
> in the recent paper: https://arxiv.org/abs/1608.00607
>
> Best,
> Tiago
>
> --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> Tiago de Paula Peixoto [hidden email]
>
> graph-tool mailing list
> [hidden email]
> https://lists.skewed.de/mailman/listinfo/graph-tool


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Snehal Shekatkar
Hi Tiago,

Sorry for bothering again. A small query: If the graph size is say 10^4, and the degrees are drawn from the discrete-power law or some other right-skewed distribution for which the second moment diverges, would n_iter = 1000 be enough for the Markov chain to saturate? Is there a rule of thumb for choosing n_iter when the scaling index of the power-law and the graph size are given?

Thanks and regards,
SS


‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Wednesday, July 22, 2020 2:22 PM, Snehal Shekatkar <[hidden email]> wrote:

> Thanks so much Tiago, I highly appreciate the help. I think it would be useful to put one such reference along with others in the random_rewire docs. Please consider this if it makes sense.
>
> Thanks and regards,
> SS
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> On Wednesday, July 22, 2020 12:47 PM, Tiago de Paula Peixoto [hidden email] wrote:
>
> > Am 22.07.20 um 08:49 schrieb Snehal Shekatkar:
> >
> > > Thanks Tiago. I have a related question: suppose self-loops and multi-edges are not allowed. Now according to the documentation, graphs are generated using "Efficient Markov Chain based on edge swaps". However, I could not find the description of the algorithm in the documentation or the references therein. I have gone through the Karrer-Newman paper as well as your paper "Entropy of stochastic blockmodel ensembles", and both do not describe the algorithm about any rewiring using Markov chains. Could you kindly point me to the actual algorithm?
> >
> > This is the usual edge-swapping algorithm that has been discovered and
> > re-discovered many times since the 50s. You can find a good description
> > in the recent paper: https://arxiv.org/abs/1608.00607
> > Best,
> > Tiago
> >
> > Tiago de Paula Peixoto [hidden email]
> > graph-tool mailing list
> > [hidden email]
> > https://lists.skewed.de/mailman/listinfo/graph-tool


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Tiago Peixoto
Administrator
Am 23.07.20 um 08:31 schrieb Snehal Shekatkar:
> Sorry for bothering again. A small query: If the graph size is say
> 10^4, and the degrees are drawn from the discrete-power law or some
> other right-skewed distribution for which the second moment diverges,
> would n_iter = 1000 be enough for the Markov chain to saturate? Is
> there a rule of thumb for choosing n_iter when the scaling index of
> the power-law and the graph size are given?

Unfortunately, there is no known rule of thumb to know how fast the
chain mixes. My inclination is to say that 1000 sweeps is often enough,
but I would encourage you to experiment and draw your own conclusions.

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Snehal Shekatkar
Thanks so much Tiago!


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Thursday, July 23, 2020 1:35 PM, Tiago de Paula Peixoto <[hidden email]> wrote:

> Am 23.07.20 um 08:31 schrieb Snehal Shekatkar:
>
> > Sorry for bothering again. A small query: If the graph size is say
> > 10^4, and the degrees are drawn from the discrete-power law or some
> > other right-skewed distribution for which the second moment diverges,
> > would n_iter = 1000 be enough for the Markov chain to saturate? Is
> > there a rule of thumb for choosing n_iter when the scaling index of
> > the power-law and the graph size are given?
>
> Unfortunately, there is no known rule of thumb to know how fast the
> chain mixes. My inclination is to say that 1000 sweeps is often enough,
> but I would encourage you to experiment and draw your own conclusions.
>
> ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> Tiago de Paula Peixoto [hidden email]
>
> graph-tool mailing list
> [hidden email]
> https://lists.skewed.de/mailman/listinfo/graph-tool


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Snehal Shekatkar
Hi Tiago,

From the documentation of deg_sampler: "This function is called once per vertex, but may be called more times, if the degree sequence cannot be used to build a graph."

Now suppose my deg_sampler sometimes returns values greater than N-1, and if I don't want to generate a graph with multi-edges and self-loops, such values will be discarded. But suppose for first few vertices, drawn values were less than N (and hence are accepted) and the next value is greater than N-1. Now will all the values generated so far discarded or only the last value? I feel that discarding only the last value will create a bias if I want to sample degrees from a particular probability distribution. Could you please clarify this?

Thank you
SS


‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Thursday, July 23, 2020 2:09 PM, Snehal Shekatkar <[hidden email]> wrote:

> Thanks so much Tiago!
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> On Thursday, July 23, 2020 1:35 PM, Tiago de Paula Peixoto [hidden email] wrote:
>
> > Am 23.07.20 um 08:31 schrieb Snehal Shekatkar:
> >
> > > Sorry for bothering again. A small query: If the graph size is say
> > > 10^4, and the degrees are drawn from the discrete-power law or some
> > > other right-skewed distribution for which the second moment diverges,
> > > would n_iter = 1000 be enough for the Markov chain to saturate? Is
> > > there a rule of thumb for choosing n_iter when the scaling index of
> > > the power-law and the graph size are given?
> >
> > Unfortunately, there is no known rule of thumb to know how fast the
> > chain mixes. My inclination is to say that 1000 sweeps is often enough,
> > but I would encourage you to experiment and draw your own conclusions.
> >
> > Tiago de Paula Peixoto [hidden email]
> > graph-tool mailing list
> > [hidden email]
> > https://lists.skewed.de/mailman/listinfo/graph-tool


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Tiago Peixoto
Administrator
Am 28.08.20 um 12:09 schrieb Snehal Shekatkar:
> Hi Tiago,
>
> From the documentation of deg_sampler: "This function is called once per vertex, but may be called more times, if the degree sequence cannot be used to build a graph."
>
> Now suppose my deg_sampler sometimes returns values greater than N-1, and if I don't want to generate a graph with multi-edges and self-loops, such values will be discarded. But suppose for first few vertices, drawn values were less than N (and hence are accepted) and the next value is greater than N-1. Now will all the values generated so far discarded or only the last value? I feel that discarding only the last value will create a bias if I want to sample degrees from a particular probability distribution. Could you please clarify this?

What the algorithm does is to sample the degrees for all vertices first,
and check if the final sequence is graphical. If it's not, then a random
node is selected, and its degree is re-sampled, and the test is done
again. This is repeated, until the sequence obtained is graphical.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Snehal Shekatkar
Thanks Tiago for the reply. Here is a script for generating a random regular graph as an example:

def generate_rrg(n, k):

    g = gt.random_graph(n, deg_sampler = lambda : k, directed = False,
        verbose = True, n_iter = 1000)

    return g

Since verbose is True, this prints what is happening. Now when I run generate_rrg(n = 10, k = 11), the following is printed and script never stops:

adding vertices: 1 of 10 (10%)

This is giving me impression that the algorithm is adding one vertex at a time. Since every time added vertex has degree 11 in this case, the algorithm is not moving ahead because that will lead to multi/self edges (if my interpretation is right). The verbose message looks difficult to explain using your description. Am I missing something obvious?

Thanks and regards,
SS




Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Friday, September 4, 2020 12:44 PM, Tiago de Paula Peixoto <[hidden email]> wrote:

> Am 28.08.20 um 12:09 schrieb Snehal Shekatkar:
>
> > Hi Tiago,
> > From the documentation of deg_sampler: "This function is called once per vertex, but may be called more times, if the degree sequence cannot be used to build a graph."
> > Now suppose my deg_sampler sometimes returns values greater than N-1, and if I don't want to generate a graph with multi-edges and self-loops, such values will be discarded. But suppose for first few vertices, drawn values were less than N (and hence are accepted) and the next value is greater than N-1. Now will all the values generated so far discarded or only the last value? I feel that discarding only the last value will create a bias if I want to sample degrees from a particular probability distribution. Could you please clarify this?
>
> What the algorithm does is to sample the degrees for all vertices first,
> and check if the final sequence is graphical. If it's not, then a random
> node is selected, and its degree is re-sampled, and the test is done
> again. This is repeated, until the sequence obtained is graphical.
>
> Best,
> Tiago
>
> ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> Tiago de Paula Peixoto [hidden email]
>
> graph-tool mailing list
> [hidden email]
> https://lists.skewed.de/mailman/listinfo/graph-tool


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Tiago Peixoto
Administrator
Am 04.09.20 um 19:01 schrieb Snehal Shekatkar:

> Thanks Tiago for the reply. Here is a script for generating a random regular graph as an example:
>
> def generate_rrg(n, k):
>
>     g = gt.random_graph(n, deg_sampler = lambda : k, directed = False,
>         verbose = True, n_iter = 1000)
>
>     return g
>
> Since verbose is True, this prints what is happening. Now when I run generate_rrg(n = 10, k = 11), the following is printed and script never stops:
>
> adding vertices: 1 of 10 (10%)
>
> This is giving me impression that the algorithm is adding one vertex at a time. Since every time added vertex has degree 11 in this case, the algorithm is not moving ahead because that will lead to multi/self edges (if my interpretation is right). The verbose message looks difficult to explain using your description. Am I missing something obvious?
In the initial placement it does indeed test if each degree is below the
maximum possible before continuing. This a necessary but not sufficient
condition being able to build a graph. After the initial degrees have
been sampled, it proceeds as I had explained.

You're attempting to generate an impossible graph, so I don't understand
what you were expecting would happen.

Best,
Tiago


Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Snehal Shekatkar
Hi Tiago,

Of course I showed the impossible graph example on purpose just to see whether all the vertices are added at once or one by one. If I try to generate other graphs, the verbose changes so quickly that the only line I see is "Added 10 vertices" etc. So okay, it checks the maximum degree before proceeding. This was not immediately obvious to me from your previous message although I was expecting that.

But now I have the same question: since in the initial placement the algorithm checks whether all the degrees are less than maximum possible, how is this done? For my impossible graph, would it be that the first degree sequence would be 11, 11, ..., 11, and then it would throw away the whole degree sequence and generate new one (obviously it would again generate all 11, and would never be able to build the graph)? Or would it simply generate degree for the first vertex, and unless it is less than max-possible, it would keep attempting to change it? I think it does the later (that is why verbose says "added 1 vertex"). If so, can we say that the initial degree sequence is drawn from a specified distribution?

Thanks and regards,
SS


‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Saturday, September 5, 2020 12:56 AM, Tiago de Paula Peixoto <[hidden email]> wrote:

> Am 04.09.20 um 19:01 schrieb Snehal Shekatkar:
>
> > Thanks Tiago for the reply. Here is a script for generating a random regular graph as an example:
> > def generate_rrg(n, k):
> >
> >     g = gt.random_graph(n, deg_sampler = lambda : k, directed = False,
> >         verbose = True, n_iter = 1000)
> >
> >     return g
> >
> >
> > Since verbose is True, this prints what is happening. Now when I run generate_rrg(n = 10, k = 11), the following is printed and script never stops:
> > adding vertices: 1 of 10 (10%)
> > This is giving me impression that the algorithm is adding one vertex at a time. Since every time added vertex has degree 11 in this case, the algorithm is not moving ahead because that will lead to multi/self edges (if my interpretation is right). The verbose message looks difficult to explain using your description. Am I missing something obvious?
>
> In the initial placement it does indeed test if each degree is below the
> maximum possible before continuing. This a necessary but not sufficient
> condition being able to build a graph. After the initial degrees have
> been sampled, it proceeds as I had explained.
>
> You're attempting to generate an impossible graph, so I don't understand
> what you were expecting would happen.
>
> Best,
> Tiago
>
> Tiago de Paula Peixoto [hidden email]
>
> graph-tool mailing list
> [hidden email]
> https://lists.skewed.de/mailman/listinfo/graph-tool


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Tiago Peixoto
Administrator
Am 05.09.20 um 03:26 schrieb Snehal Shekatkar:
> But now I have the same question: since in the initial placement the algorithm checks whether all the degrees are less than maximum possible, how is this done? For my impossible graph, would it be that the first degree sequence would be 11, 11, ..., 11, and then it would throw away the whole degree sequence and generate new one (obviously it would again generate all 11, and would never be able to build the graph)? Or would it simply generate degree for the first vertex, and unless it is less than max-possible, it would keep attempting to change it? I think it does the later (that is why verbose says "added 1 vertex").

It does the latter.

> If so, can we say that the initial degree sequence is drawn from a specified distribution?

Graphical degree sequences are *never* composed of i.i.d. degrees, since
they must fulfill the Erdős–Gallai inequality. For (uniformly) sparse
graphs, most sequences of i.i.d. degrees will fulfill it with high
probability, so we can say the degrees are approximately independent.
But as long as some degrees become large, this is no longer true.

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: n_iter with parallel edges allowed

Snehal Shekatkar
I see. Thanks so much Tiago!


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Sunday, September 6, 2020 11:09 PM, Tiago de Paula Peixoto <[hidden email]> wrote:

> Am 05.09.20 um 03:26 schrieb Snehal Shekatkar:
>
> > But now I have the same question: since in the initial placement the algorithm checks whether all the degrees are less than maximum possible, how is this done? For my impossible graph, would it be that the first degree sequence would be 11, 11, ..., 11, and then it would throw away the whole degree sequence and generate new one (obviously it would again generate all 11, and would never be able to build the graph)? Or would it simply generate degree for the first vertex, and unless it is less than max-possible, it would keep attempting to change it? I think it does the later (that is why verbose says "added 1 vertex").
>
> It does the latter.
>
> > If so, can we say that the initial degree sequence is drawn from a specified distribution?
>
> Graphical degree sequences arenever composed of i.i.d. degrees, since
> they must fulfill the Erdős–Gallai inequality. For (uniformly) sparse
> graphs, most sequences of i.i.d. degrees will fulfill it with high
> probability, so we can say the degrees are approximately independent.
> But as long as some degrees become large, this is no longer true.
>
> ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> Tiago de Paula Peixoto [hidden email]
>
> graph-tool mailing list
> [hidden email]
> https://lists.skewed.de/mailman/listinfo/graph-tool


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool