[Networkit] Preferential attachment graph generator
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 , 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