[Networkit] Preferential attachment graph generator

Maximilian Vogel maximilian.vogel at student.kit.edu
Tue Mar 1 17:15:39 CET 2016

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.


More information about the NetworKit mailing list