All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Protected Attributes | List of all members
NetworKit::ChungLuGenerator Class Reference

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

#include <ChungLuGenerator.h>

Public Member Functions

 ChungLuGenerator (const std::vector< count > &degreeSequence)
 
virtual Graph generate ()
 Generates graph with expected degree sequence seq. More...
 
- Public Member Functions inherited from NetworKit::StaticDegreeSequenceGenerator
 StaticDegreeSequenceGenerator (const std::vector< count > &sequence)
 
virtual bool isRealizable ()
 Erdoes-Gallai test if degree sequence seq is realizable. More...
 
virtual bool getRealizable () const
 
- Public Member Functions inherited from NetworKit::StaticGraphGenerator
virtual ~StaticGraphGenerator ()=default
 Default destructor. More...
 

Protected Attributes

count sum_deg
 
count n
 
- Protected Attributes inherited from NetworKit::StaticDegreeSequenceGenerator
std::vector< countseq
 
short realizable
 

Detailed Description

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) http://aric.hagberg.org/papers/miller-2011-efficient.pdf . It gives a complexity of O(n+m) as opposed to quadratic.

Constructor & Destructor Documentation

NetworKit::ChungLuGenerator::ChungLuGenerator ( const std::vector< count > &  degreeSequence)

Member Function Documentation

Graph NetworKit::ChungLuGenerator::generate ( )
virtual

Generates graph with expected degree sequence seq.

Implements NetworKit::StaticDegreeSequenceGenerator.

Member Data Documentation

count NetworKit::ChungLuGenerator::n
protected
count NetworKit::ChungLuGenerator::sum_deg
protected

The documentation for this class was generated from the following files: