Class ChungLuGenerator

Inheritance Relationships

Base Type

Class Documentation

class ChungLuGenerator : public NetworKit::StaticDegreeSequenceGenerator

Given an arbitrary degree sequence, the Chung-Lu generative model will produce a random graph with the same expected degree sequence.

see Chung, Lu: The average distances in random graphs with given expected degrees and Chung, Lu: Connected Components in Random Graphs with Given Expected Degree Sequences. Aiello, Chung, Lu: A Random Graph Model for Massive Graphs describes a different generative model which is basically asymptotically equivalent but produces multi-graphs.

This follows the implementation of Joel Miller and Aric Hagberg’s “Efficient Generation of Networks with Given Expected Degrees” (2011) . It gives a complexity of O(n+m) as opposed to quadratic.

Public Functions

ChungLuGenerator(const std::vector<count> &degreeSequence)
virtual Graph generate() override

Generates graph with expected degree sequence seq.