Class BarabasiAlbertGenerator¶

Inheritance Relationships¶

Class Documentation¶

class BarabasiAlbertGenerator : public NetworKit::StaticGraphGenerator¶

Generates a scale-free graph using the Barabasi-Albert preferential attachment model.

Public Functions

BarabasiAlbertGenerator() = default¶

BarabasiAlbertGenerator(count k, count nMax, count n0 = 0, bool batagelj = true)¶

This generator implements the preferential attachment model as introduced by Barabasi and Albert[1]. The original algorithm is very slow and thus, the much faster method from Batagelj and Brandes[2] is implemented and the current default. The original method is no longer supported and the batagelj parameter will be removed in future releases. [1] Barabasi, Albert: Emergence of Scaling in Random Networks http://arxiv.org/pdf/cond-mat/9910332.pdf [2] ALG 5 of Batagelj, Brandes: Efficient Generation of Large Random Networks https://kops.uni-konstanz.de/bitstream/handle/123456789/5799/random.pdf?sequence=1 Running time is O(n+m)

The generator will emit a simple graph, where all new nodes are initially connected to k random neighbors.

Parameters:

• k – Number of attachments per node

• nMax – Number of nodes in the graph

• n0 – Number of connected nodes to begin with

• batagelj – Specifies whether to use Batagelj and Brandes’s method (much faster) rather than the naive one; default: true

BarabasiAlbertGenerator(count k, count nMax, const Graph &initGraph, bool batagelj = true)¶

This generator implements the preferential attachment model as introduced by Barabasi and Albert[1]. The original algorithm is very slow and thus, the much faster method from Batagelj and Brandes[2] is implemented and the current default. The original method is no longer supported and the batagelj parameter will be removed in future releases. [1] Barabasi, Albert: Emergence of Scaling in Random Networks http://arxiv.org/pdf/cond-mat/9910332.pdf [2] ALG 5 of Batagelj, Brandes: Efficient Generation of Large Random Networks https://kops.uni-konstanz.de/bitstream/handle/123456789/5799/random.pdf?sequence=1 Running time is O(n+m)

The generator will emit a simple graph (given that the seed graph is simple), where all new nodes are initially connected to k random neighbors.

Parameters:

• k – Number of attachments per node

• nMax – Number of nodes in the graph

• initGraph – The initial graph to start from

• batagelj – Specifies whether to use Batagelj and Brandes’s method (much faster) rather than the naive one; default: true

virtual Graph generate() override¶