[Networkit] NetworKit Digest, Vol 35, Issue 3

Moritz von Looz moritz.looz-corswarem at kit.edu
Fri Oct 7 13:01:06 CEST 2016


Hey Daniel,

I'm glad I could help.

A temperature of 10 is quite high, the implementation of Aldecoa et al. for example considers it equivalent to infinity for the purposes of the model.

For a graph with 5k nodes, average degree 5 and T=10, R is ~167.085 and \beta is 0.1. When looking at Equation 41 of "Hyperbolic geometry of complex networks", the paper by Krioukov et al. introducing the model,
the difference in edge probability for node pairs with distance 100 or 200 is still significant (0.998770601 vs 0.035571189), but long-range edges are frequent enough to approach the Erdos-Reyni-model.

Many network parameters already change significantly for values of t between 0 and 1, see the last page of https://arxiv.org/pdf/1509.01990v2.pdf for some examples.

As for the rising number of components: yes, that is exactly what happens. Connections are more local, the graph diameter increases and the graph finally becomes disconnected.

All the best,
Moritz

Am 06.10.2016 um 20:50 schrieb Daniel N. R. da Silva:
> 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
>> ****************************************
>>
> 
> 
> 



More information about the NetworKit mailing list