n_iter with parallel edges allowed

classic Classic list List threaded Threaded
8 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