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 sequential = true)¶

This generator uses the preferential attachment model as introduced by Barabasi and Albert[1], implemented in the much faster method from Batagelj and Brandes[2] per default where the running time is O(n+m). Furthermore there is a parallel version from Sanders and Schulz[3] implemented. This implementation can be selected by setting sequential=false. Empirically, the parallel version shows better runtimes (when executed multi-threaded).

[1] Barabasi, Albert: Emergence of Scaling in Random Networks [2] ALG 5 of Batagelj, Brandes: Efficient Generation of Large Random Networks [3] Peter Sanders, Christian Schulz: Scalable generation of scale-free graphs

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

• sequential – Specifies whether to use Batagelj and Brandes’s method (sequential) or a parallel variant. Default: true.

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

This generator uses the preferential attachment model as introduced by Barabasi and Albert[1], implemented in the much faster method from Batagelj and Brandes[2] per default where the running time is O(n+m). Furthermore there is a parallel version from Sanders and Schulz[3] implemented. This implementation can be selected by setting sequential=false. Empirically, the parallel version shows better runtimes (when executed multi-threaded).

[1] Barabasi, Albert: Emergence of Scaling in Random Networks [2] ALG 5 of Batagelj, Brandes: Efficient Generation of Large Random Networks [3] Peter Sanders, Christian Schulz: Scalable generation of scale-free graphs

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

• initGraph – The initial graph to start from

• sequential – Specifies whether to use Batagelj and Brandes’s method (sequential) or a parallel variant. Default: true.

virtual Graph generate() override¶