[Networkit] NetworKit Digest, Vol 35, Issue 3

Daniel N. R. da Silva danielnascramos at gmail.com
Thu Oct 6 20:50:38 CEST 2016


Hey Moritz,

First of all, I'd like to apologize for taking so long to answer you back.
The last week I was very busy with other things. Nevertheless, your answers
were extremely helpful.

Concerning to the Power Law issue: This pretty much happens as I increase
the temperature. For instance: n=1000, k=10, g=2.5, t=10

Another thing that I've found pretty interesting is that using a lower
temperature I've got more components, e.g, my graph gets more disconnected.
Please correct me if I wrong; The reason of that phenomena is related to
the fact that the lower the temperature the higher the probability of two
nodes connection depends on their distance.

I uploaded a file https://www.dropbox.com/s/ott4at5hfrdzpkc/values.csv?dl=0
where my observations can be noted.

Thanks and Best Regards.


2016-09-23 0:15 GMT-03:00 <networkit-request at ira.uni-karlsruhe.de>:

> Send NetworKit mailing list submissions to
>         networkit at ira.uni-karlsruhe.de
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
> or, via email, send a message with subject or body 'help' to
>         networkit-request at ira.uni-karlsruhe.de
>
> You can reach the person managing the list at
>         networkit-owner at ira.uni-karlsruhe.de
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of NetworKit digest..."
>
>
> Today's Topics:
>
>    1. Re: Hyperbolic graph generator (Henning Meyerhenke)
>    2. Re: Hyperbolic graph generator (Moritz von Looz)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Thu, 22 Sep 2016 09:03:35 +0200
> From: Henning Meyerhenke <henning.meyerhenke at kit.edu>
> To: "Daniel N. R. da Silva" <danielnascramos at gmail.com>
> Cc: "NetworKit: a toolkit for high-performance network analysis"
>         <networkit at ira.uni-karlsruhe.de>
> Subject: Re: [Networkit] Hyperbolic graph generator
> Message-ID: <ff4b4f3b-f73a-400e-a95e-2cd9995e46fc at kit.edu>
> Content-Type: text/plain; charset="windows-1252"
>
> Dear Daniel,
>
> Thank you very much for your interest and your feedback.
>
> Moritz (cc) will be back from vacation on Monday. I am sure he will be
> able to shed light on these issues and provide the necessary support via
> the mailing list.
>
> Best regards,
> Henning
>
>
> Am 22.09.16 um 04:22 schrieb Daniel N. R. da Silva:
> > I'm interested in using the static Hyperbolic Random Geometric Graph
> > Generator (HRGGG) - that's quite a name :) -
> > (networkit.generators.HyperbolicGenerator) and got some doubts.
> >
> > I read [1] and according to its authors, HRGG have four parameters to be
> > manipulated: number of nodes, ~average degree, ~power law exponent, and
> > temperature. Looking for a generator, I found [2]. Their authors claim
> > that the user can manipulate the four parameters using their proposed
> > generator. But I realized after reading [3], that [2] takes too much
> > time to generate large networks. So I went for [3]. But reading it, I
> > realized that, roughly speaking, the temperature parameter is fixed at
> > 0, not a function anymore, i.e, the generator uses a more specific
> > model: the threshold random hyperbolic graphs one (unit-disk graphs in
> > hyperbolic space).
> >
> > So I got a little confused with the function docstring in NetworKit
> > library:
> >
> > HyperbolicGenerator(n, k=6, gamma=3, T=0) Parameters ---------- n :
> > integer number of nodes k : double average degree gamma : double
> > exponent of power-law degree distribution T : double temperature of
> > statistical model
> >
> > My questions (using networkit generator):
> >
> > * T has a default value of 0, but I was able to manipulate it. Am I
> > supposed to do this kind of manipulation?
> >
> > * I did some preliminary tests using T > 0 and noted that the degree
> > distribution got pretty weird, plotting it, it did not seem to be
> > Poisson or Power Law. Also, I increased the power law exponent, and as I
> > did it, the degree distribution started to look more like a Poisson
> > distribution centered around the average degree. Concerning to the
> > clustering coefficient, when I increased the Power Law exponent, the
> > clustering decreased. Moreover, as T increased, the clustering
> > coefficient substantially decreased. Are those things supposed to happen?
> >
> > * [2] claims that when the power law exponent and the temperature
> > approach inf, the hyperbolic graph degenerates to Erdos Renyi Random
> > Graph Model. Does Networkit generator have the same properties/regimes
> > presented on Table 1 ([2] pg. 2)?
> >
> > I know that it's a lot of questions and appreciate any help.
> >
> > Ps:
> >
> > * On NetworKit jupyter notebooks documentation page, only the "NetworKit
> > User Guide" link is working.
> >
> >
> >
> > [1] Krioukov, et al. Hyperbolic Geometry of Complex Networks. 2010
> >
> > [2] Aldecoa, et al. Hyperbolic Graph Generator. 2015
> >
> > [3] Looz and Ozdayi. Generating massive complex networks with hyperbolic
> > geometry faster in practice. 2016
> >
> >
> >
> > _______________________________________________
> > NetworKit mailing list
> > NetworKit at ira.uni-karlsruhe.de
> > https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
> >
>
> --
>
> ==========================================================
> Karlsruhe Institute of Technology (KIT)
> Institute of Theoretical Informatics (ITI)
>
> Prof. Dr. Henning Meyerhenke
> Theoret. Informatics / Parallel Computing
>
> Phone: +49-721-608-41876
> Web: http://parco.iti.kit.edu/henningm/
>
> KIT - The Research University in the Helmholtz Association
> ==========================================================
>
> -------------- next part --------------
> A non-text attachment was scrubbed...
> Name: smime.p7s
> Type: application/pkcs7-signature
> Size: 5399 bytes
> Desc: S/MIME Cryptographic Signature
> URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/
> 20160922/1da0b6f0/attachment-0001.p7s>
>
> ------------------------------
>
> Message: 2
> Date: Thu, 22 Sep 2016 11:40:06 -0400
> From: Moritz von Looz <moritz.looz-corswarem at kit.edu>
> To: <danielnascramos at gmail.com>
> Cc: networkit at ira.uni-karlsruhe.de
> Subject: Re: [Networkit] Hyperbolic graph generator
> Message-ID: <3b166f3e-9d46-aa8d-0d9c-052c9f9a86d4 at kit.edu>
> Content-Type: text/plain; charset="windows-1252"
>
> Hey Daniel,
>
> thanks for your interest and your detailed experiments!
>
> I'm the first author of [3], allow me to shed some light on this mystery.
> :-)
>
> We have two different generation algorithms for hyperbolic random graphs.
>
> The algorithm described in [3] is for a temperature of zero, in [4] we
> present an algorithm for non-zero temperatures.
> Since the more general algorithm is slower, NetworKit decides which of
> them to use based on the temperature argument.
> The algorithm described in [4] is still faster than the quadratic approach
> in [2].
>
> So yes, your are supposed to do this kind of manipulation and it should
> give consistent results.
>
> A decreasing clustering coefficient is supposed to happen, since a larger
> temperature means that the probability of two nodes being connected depends
> less on their distance.
> For infinite temperatures, the model indeed degenerates into Erdos-Reyni,
> since all node pairs have an equal probability of having an edge.
> Erdos-Reyni has a clustering coefficient of effectively zero.
> Since these results are properties of the model, not the generation
> algorithm, it is similar in [2] and [4].
>
> However, the calculations get a little funky for high temperatures, which
> is presumably why the authors of [2] treat values of T>10 as effectively
> infinity, have implemented an explicit cutoff and just use an
> Erdos-Reyni model in this case.
> We haven't done that, so generated graphs at high temperatures might
> differ slightly.
>
> The degree distribution not being a power law is concerning. Again, in the
> limiting case this is to be expected, since Erdos-Reyni does not yield a
> power-law degree distribution. At which values did this occur?
>
> Does this help?
>
> All the best,
> Moritz
>
>
> [1] Krioukov, et al. Hyperbolic Geometry of Complex Networks. 2010
>
> [2] Aldecoa, et al. Hyperbolic Graph Generator. 2015
>
> [3] Looz et al. Generating massive complex networks with hyperbolic
> geometry faster in practice. 2016
>
> [4] Looz and Meyerhenke, Querying Probabilistic Neighborhoods in Spatial
> Data Sets Efficiently. 2016
>
>
>
> Am 21.09.2016 um 22:22 schrieb Daniel N. R. da Silva:
> > I'm interested in using the static Hyperbolic Random Geometric Graph
> > Generator (HRGGG) - that's quite a name :) -
> > (networkit.generators.HyperbolicGenerator) and got some doubts.
> >
> > I read [1] and according to its authors, HRGG have four parameters to be
> > manipulated: number of nodes, ~average degree, ~power law exponent, and
> > temperature. Looking for a generator, I found [2]. Their authors claim
> that
> > the user can manipulate the four parameters using their proposed
> generator.
> > But I realized after reading [3], that [2] takes too much time to
> generate
> > large networks. So I went for [3]. But reading it, I realized that,
> roughly
> > speaking, the temperature parameter is fixed at 0, not a function
> anymore,
> > i.e, the generator uses a more specific model: the threshold random
> > hyperbolic graphs one (unit-disk graphs in hyperbolic space).
> >
> > So I got a little confused with the function docstring in NetworKit
> > library:
> >
> > HyperbolicGenerator(n, k=6, gamma=3, T=0) Parameters ---------- n :
> integer
> > number of nodes k : double average degree gamma : double exponent of
> > power-law degree distribution T : double temperature of statistical model
> >
> > My questions (using networkit generator):
> >
> > * T has a default value of 0, but I was able to manipulate it. Am I
> > supposed to do this kind of manipulation?
> >
> > * I did some preliminary tests using T > 0 and noted that the degree
> > distribution got pretty weird, plotting it, it did not seem to be Poisson
> > or Power Law. Also, I increased the power law exponent, and as I did it,
> > the degree distribution started to look more like a Poisson distribution
> > centered around the average degree. Concerning to the clustering
> > coefficient, when I increased the Power Law exponent, the clustering
> > decreased. Moreover, as T increased, the clustering coefficient
> > substantially decreased. Are those things supposed to happen?
> >
> > * [2] claims that when the power law exponent and the temperature
> approach
> > inf, the hyperbolic graph degenerates to Erdos Renyi Random Graph Model.
> > Does Networkit generator have the same properties/regimes presented on
> > Table 1 ([2] pg. 2)?
> >
> > I know that it's a lot of questions and appreciate any help.
> >
> > Ps:
> >
> > * On NetworKit jupyter notebooks documentation page, only the "NetworKit
> > User Guide" link is working.
> >
> >
> >
> > [1] Krioukov, et al. Hyperbolic Geometry of Complex Networks. 2010
> >
> > [2] Aldecoa, et al. Hyperbolic Graph Generator. 2015
> >
> > [3] Looz and Ozdayi. Generating massive complex networks with hyperbolic
> > geometry faster in practice. 2016
> >
> >
> >
> > _______________________________________________
> > NetworKit mailing list
> > NetworKit at ira.uni-karlsruhe.de
> > https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
> >
>
>
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
>
> ------------------------------
>
> End of NetworKit Digest, Vol 35, Issue 3
> ****************************************
>



-- 
*Atenciosamente,*

*Daniel N. R. da Silva*
*I don't believe in excuses. I believe in hard work as the prime solvent of
life's problems (**J. C. Penney)*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20161006/b56f03c8/attachment-0001.html>


More information about the NetworKit mailing list