[Networkit] Preferential attachment graph generator

Christian Staudt christian.staudt at kit.edu
Tue Mar 1 17:51:08 CET 2016

I think you’ve got that under control, but please check if you haven’t done so yet:
- the resulting graph cannot have multi-edges and should not have self-loops
- make sure the .fit method still does what it’s supposed to do, using the new algorithm


> I also vote to rename BarabasiAlbertGenerator to PreferentialAttachmentGenerator as it is more descriptive

I’m all for descriptive names, but also for consistency, so not sure what to do with the ErdosRenyiGenerator, the ChungLuGenerator, the HavelHakimiGenerator and the DorogovtsevMendesGenerator after we’ve opened that can of worms. (At least we’ve already avoided the VonLoozMeyerhenkeKrioukovGenerator.)

> On 01 Mar 2016, at 17:15, Maximilian Vogel <maximilian.vogel at student.kit.edu> 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.
> The new algorithm is already in the Dev branch and finally the default choice for the BarabasiAlbertGenerator. There are a few things to note (k = number of attachments per node, n = number of nodes, m = number of edges, n0 = initally connected nodes):
> - 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.)
> - Batagelj's method runs in O(n+m) where m = k*n. As the algorithm doesn't check for duplicates, the resulting number of edges is actually smaller than k*n. This highly depends on the ratio n/k: the smaller it is, the more duplicates are to expect.
> - This is also the reason, why the old method hasn't been removed: Although it is much slower (partly because of resampling), it is guarenteed to generate (n-n0)*k + n0-1 edges.
> - Another subtlety: The old algorithm has to have at least n0 >= k connected nodes to begin with. This doesn't apply for Batagelj's method and the few experiments I made, showed that the new implementation yields more edges with n0=0 than with n0=k.
> 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.
> Best,
> Max
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20160301/d36eaea2/attachment.sig>

More information about the NetworKit mailing list