[Networkit] Hyperbolic graph generator

Moritz von Looz moritz.looz-corswarem at kit.edu
Thu Sep 22 17:40:06 CEST 2016


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
> 



More information about the NetworKit mailing list