[Networkit] Preferential attachment graph generator

Michael Hamann michael.hamann at kit.edu
Tue Mar 1 17:34:31 CET 2016


On 01.03.2016 17:15 Maximilian Vogel wrote:
> On 29.02.2016 21:18, Christian Staudt wrote:
>> The last part was certainly true. Coincidentally I realized this last
>> week and therefore asked Max to implement the much faster but also
>> simple algorithm by Batagelj and Brandes [1], which he did successfully.

It might also be interesting to implement the recently published
parallel algorithm by Sanders and Schulz, see
http://arxiv.org/abs/1602.07106 if it is not too complicated (but it
claims to be rather simple). They also explain how to make sure the
resulting graph is simple.

> - Batagelj remarks, that any graph can used as input. This option is now
> available in both implementations. (Although I have problems cythonizing
> the overloaded constructors - help appreciated.)

Have a look at the constructor of the Cover class for that, it does
something very similar. If you have still problems please ask a more
detailed question.

> I also vote to rename BarabasiAlbertGenerator to
> PreferentialAttachmentGenerator as it is more descriptive. I'd take care
> of the refactoring, if there aren't any protests. And since we're at it:
> What's the state of the DynamicBarabasiAlbertGenerator? It should be
> refactored for consistency as well, but the underlying question is
> whether it is working/used/maintained and if so, if the new algorithm
> should be implemented there aswell.

I think it could make sense to rename the class, but we could also keep
the old name as it is also widely used. One could also use
BarabasiAlbertPreferentialAttachmentGenerator as name, but that's
probably a bit too long.

I don't know about the dynamic generator, I haven't used it yet.


More information about the NetworKit mailing list