Class ChungLuGeneratorAlamEtAl¶

Nested Relationships¶

Inheritance Relationships¶

Class Documentation¶

class ChungLuGeneratorAlamEtAl : private NetworKit::StaticGraphGenerator¶

The Chung-Lu generative model produces a random graph for a given expected degree sequence. For reference, see the original model proposed by Chung and Lu in [1] and [2]. This implementation follows a newer parallelizable algorithm [3] by M. Alam, M. Khan et al.: The time complexity is O(m/p + delta + p), where m is the number of edges, p are the number of threads, and delta is the number of distinct node degrees from the input sequence. Furthermore the space complexity is O(delta) for each of the p threads.

[1] F. Chung, L. Lu: The Average Distance in a Random Graph with Given Expected Degree

[2] F. Chung, L. Lu: Connected Components in Random Graphs with Given Expected Degree Sequences

[3] M. Alam, M. Khan, et al.: An Efficient and Scalable Algorithmic Method for Generating Large-Scale Random Graphs

Public Functions

ChungLuGeneratorAlamEtAl(const std::vector<count> &degreeSequence, bool parallel = false)¶

virtual Graph generate() override¶

Generates graph with expected degree sequence seq.