[Networkit] Hyperbolic graph generator
Moritz von Looz
moritz.looz-corswarem at kit.edu
Thu Sep 22 17:40:06 CEST 2016
thanks for your interest and your detailed experiments!
I'm the first author of , allow me to shed some light on this mystery. :-)
We have two different generation algorithms for hyperbolic random graphs.
The algorithm described in  is for a temperature of zero, in  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  is still faster than the quadratic approach in .
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  and .
However, the calculations get a little funky for high temperatures, which is presumably why the authors of  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,
 Krioukov, et al. Hyperbolic Geometry of Complex Networks. 2010
 Aldecoa, et al. Hyperbolic Graph Generator. 2015
 Looz et al. Generating massive complex networks with hyperbolic geometry faster in practice. 2016
 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  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 . Their authors claim that
> the user can manipulate the four parameters using their proposed generator.
> But I realized after reading , that  takes too much time to generate
> large networks. So I went for . 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
> 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?
> *  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 ( pg. 2)?
> I know that it's a lot of questions and appreciate any help.
> * On NetworKit jupyter notebooks documentation page, only the "NetworKit
> User Guide" link is working.
>  Krioukov, et al. Hyperbolic Geometry of Complex Networks. 2010
>  Aldecoa, et al. Hyperbolic Graph Generator. 2015
>  Looz and Ozdayi. Generating massive complex networks with hyperbolic
> geometry faster in practice. 2016
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
More information about the NetworKit