[SOLVED] Wiring Probability (Random Graph Generator)

nullusadinfinitum · Post by **nullusadinfinitum** » 09 Aug 2011 11:24

Hello,

Would someone be able to explain the theoretical underpinning behind the wiring probability for the random graph generator? What does the value represent? Is there some ratio to calculate with respect to the number of nodes when investigating the small-world phenomenon? Forgive my inexperience.

cezar_1 · Post by **cezar_1** » 09 Aug 2011 22:12

Well,

This generator is based on Watts & Strogatz Alpha Model. The wiring probability is β from the description in Wikipedia:

http://en.wikipedia.org/wiki/Watts_and_Strogatz_model

So, as they write, varying this value makes it possible to interpolate between a regular lattice (β = 0) and a random graph (β = 1) approaching the Erdős–Rényi random graph.

Unfortunately this generator doesn't create a regular ring lattice first, so it's not so usable when you want to investigate the small world phenomenon. If you want to do it try my plugin: http://gephi.org/plugins/complex-generators/ But be careful with Erdos-Renyi Gnp generator, since it contains a little bug. I'll upload the fix soon.

nullusadinfinitum · Post by **nullusadinfinitum** » 10 Aug 2011 09:19

cezar_1 wrote:Well,

This generator is based on Watts & Strogatz Alpha Model. The wiring probability is β from the description in Wikipedia:

http://en.wikipedia.org/wiki/Watts_and_Strogatz_model

So, as they write, varying this value makes it possible to interpolate between a regular lattice (β = 0) and a random graph (β = 1) approaching the Erdős–Rényi random graph.

Unfortunately this generator doesn't create a regular ring lattice first, so it's not so usable when you want to investigate the small world phenomenon. If you want to do it try my plugin: http://gephi.org/plugins/complex-generators/ But be careful with Erdos-Renyi Gnp generator, since it contains a little bug. I'll upload the fix soon.

Thank you for this insightful response. For illustrative purposes, let's say I had a very small graph with just 7 nodes. If I wanted to investigate whether the small-world phenomenon exists, using your complex generators, which generator would be most effective, and what values would I input for it?

cezar_1 · Post by **cezar_1** » 13 Aug 2011 12:52

I'm not sure what you want to do

If you just want to generate a small world network with 7 nodes, you can use any small world generator (Kleinberg, Watts Strogatz Alpha, Watts Strogatz Beta). There are no "optimal" values of parameters, but if you want to get "representative" small world networks just experiment remembering that a small world network have got a 'high' clustering coefficient and its mean-shortest path length should be 'small' (this is not precise, but it can't be defined precisely). You can also look through these papers for more info:

Kleinberg:

http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf
http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf

Watts Strogatz Alpha/Beta:

http://tam.cornell.edu/tam/cms/manage/u ... lworld.pdf
http://www.bsos.umd.edu/socy/alan/stats ... -Ghosh.pdf
http://www.cc.gatech.edu/~mihail/D.8802 ... ts-swp.pdf

hello_kitty · Post by **hello_kitty** » 07 May 2014 08:58

Thanks for sharing links. First link from Cornell University is not working.

Gephi forums

[SOLVED] Wiring Probability (Random Graph Generator)

Re: Wiring Probability (Random Graph Generator)

Re: Wiring Probability (Random Graph Generator)

Re: Wiring Probability (Random Graph Generator)

Re: [SOLVED] Wiring Probability (Random Graph Generator)