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

The LFR clustered graph generator as introduced by Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. More...

#include <LFRGenerator.h>

Public Member Functions

 LFRGenerator (count n)
 Initialize the LFR generator for n nodes. More...
 
void setDegreeSequence (std::vector< count > degreeSequence)
 Set the given degree sequence. More...
 
void generatePowerlawDegreeSequence (count avgDegree, count maxDegree, double nodeDegreeExp)
 Generate and set a power law degree sequence using the given average and maximum degree with the given exponent. More...
 
void setCommunitySizeSequence (std::vector< count > communitySizeSequence)
 Set the given community size sequence. More...
 
void setPartition (Partition zeta)
 Set the partition, this replaces the community size sequence and the random assignment of the nodes to communities. More...
 
void generatePowerlawCommunitySizeSequence (count minCommunitySize, count maxCommunitySize, double communitySizeExp)
 Generate a powerlaw community size sequence with the given minimum and maximum size and the given exponent. More...
 
void setMu (double mu)
 Set the mixing parameter, this is the fraction of neighbors of each node that do not belong to the node's own community. More...
 
void setMu (const std::vector< double > &mu)
 Set the mixing parameter separately for each node. More...
 
void setMuWithBinomialDistribution (double mu)
 Set the internal degree of each node using a binomial distribution such that the expected mixing parameter is the given mu. More...
 
virtual void run () override
 Generates the graph and the community structure. More...
 
virtual Graph generate () override
 Generates and returns the graph. More...
 
Graph getGraph () const
 Returns (a copy of) the generated graph. More...
 
Graph && getMoveGraph ()
 Returns the generated graph using move semantics. More...
 
Partition getPartition () const
 Returns (a copy of) the generated partition. More...
 
Partition && getMovePartition ()
 Returns the generated partition using move semantics. More...
 
virtual std::string toString () const override
 The name and parameters of the generator. More...
 
virtual bool isParallel () const override
 If the algorithm uses parallelism (no) More...
 
- Public Member Functions inherited from NetworKit::Algorithm
 Algorithm ()
 Constructor to the algorithm base class. More...
 
virtual ~Algorithm ()=default
 Virtual default destructor. More...
 
bool hasFinished () const
 Indicates whether an algorithm has completed computation or not. More...
 
void assureFinished () const
 Assure that the algorithm has been run, throws a std::runtime_error otherwise. More...
 
- Public Member Functions inherited from NetworKit::StaticGraphGenerator
virtual ~StaticGraphGenerator ()=default
 Default destructor. More...
 

Protected Member Functions

virtual std::vector
< std::vector< node > > 
assignNodesToCommunities ()
 
virtual Graph generateIntraClusterGraph (std::vector< NetworKit::count > intraDegreeSequence, const std::vector< NetworKit::node > &localToGlobalNode)
 
virtual Graph generateInterClusterGraph (const std::vector< count > &externalDegreeSequence)
 

Protected Attributes

count n
 
bool hasDegreeSequence
 
std::vector< countdegreeSequence
 
bool hasCommunitySizeSequence
 
std::vector< countcommunitySizeSequence
 
bool hasInternalDegreeSequence
 
std::vector< countinternalDegreeSequence
 
bool hasGraph
 
Graph G
 
bool hasPartition
 
Partition zeta
 
- Protected Attributes inherited from NetworKit::Algorithm
bool hasRun
 A boolean variable indicating whether an algorithm has finished its computation or not. More...
 

Detailed Description

The LFR clustered graph generator as introduced by Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi.

The community assignment follows the algorithm described in "Benchmark graphs for testing community detection algorithms". The edge generation is however taken from their follow-up publication "Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities". Parts of the implementation follow the choices made in their implementation which is available at https://sites.google.com/site/andrealancichinetti/software but other parts differ, for example some more checks for the realizability of the community and degree size distributions are done instead of heavily modifying the distributions.

The edge-switching markov-chain algorithm implementation in NetworKit is used which is different from the implementation in the original LFR benchmark.

Constructor & Destructor Documentation

NetworKit::LFRGenerator::LFRGenerator ( NetworKit::count  n)

Initialize the LFR generator for n nodes.

Note
You need to set a degree sequence, a community size sequence and a mu using the additionally provided set- or generate-methods.
Parameters
nThe number of nodes.

Member Function Documentation

std::vector< std::vector< NetworKit::node > > NetworKit::LFRGenerator::assignNodesToCommunities ( )
protectedvirtual
NetworKit::Graph NetworKit::LFRGenerator::generate ( )
overridevirtual

Generates and returns the graph.

Returns
The generated graph.

Implements NetworKit::StaticGraphGenerator.

NetworKit::Graph NetworKit::LFRGenerator::generateInterClusterGraph ( const std::vector< count > &  externalDegreeSequence)
protectedvirtual
NetworKit::Graph NetworKit::LFRGenerator::generateIntraClusterGraph ( std::vector< NetworKit::count intraDegreeSequence,
const std::vector< NetworKit::node > &  localToGlobalNode 
)
protectedvirtual
void NetworKit::LFRGenerator::generatePowerlawCommunitySizeSequence ( NetworKit::count  minCommunitySize,
NetworKit::count  maxCommunitySize,
double  communitySizeExp 
)

Generate a powerlaw community size sequence with the given minimum and maximum size and the given exponent.

Parameters
minCommunitySizeThe minimum community size to generate
maxCommunitySizeThe maximum community size to generate
communitySizeExpThe (negative) exponent of the power law community size sequence
void NetworKit::LFRGenerator::generatePowerlawDegreeSequence ( NetworKit::count  avgDegree,
NetworKit::count  maxDegree,
double  nodeDegreeExp 
)

Generate and set a power law degree sequence using the given average and maximum degree with the given exponent.

Parameters
avgDegreeThe average degree that shall be reached.
maxDegreeThe maximum degree that shall be generated.
nodeDegreeExpThe (negative) exponent of the powerlaw degree sequence.
NetworKit::Graph NetworKit::LFRGenerator::getGraph ( ) const

Returns (a copy of) the generated graph.

Returns
The generated graph.
NetworKit::Graph && NetworKit::LFRGenerator::getMoveGraph ( )

Returns the generated graph using move semantics.

Returns
The generated graph.
NetworKit::Partition && NetworKit::LFRGenerator::getMovePartition ( )

Returns the generated partition using move semantics.

Returns
The generated partition.
NetworKit::Partition NetworKit::LFRGenerator::getPartition ( ) const

Returns (a copy of) the generated partition.

Returns
The generated graph.
bool NetworKit::LFRGenerator::isParallel ( ) const
overridevirtual

If the algorithm uses parallelism (no)

Returns
false, only minor parts are parallelized

Reimplemented from NetworKit::Algorithm.

void NetworKit::LFRGenerator::run ( )
overridevirtual

Generates the graph and the community structure.

Implements NetworKit::Algorithm.

void NetworKit::LFRGenerator::setCommunitySizeSequence ( std::vector< count communitySizeSequence)

Set the given community size sequence.

Parameters
communitySizeSequenceThe community sizes that shall be used.
void NetworKit::LFRGenerator::setDegreeSequence ( std::vector< count degreeSequence)

Set the given degree sequence.

Parameters
degreeSequenceThe degree sequence that shall be used by the generator
void NetworKit::LFRGenerator::setMu ( double  mu)

Set the mixing parameter, this is the fraction of neighbors of each node that do not belong to the node's own community.

Parameters
muThe mixing parameter that shall be set.
void NetworKit::LFRGenerator::setMu ( const std::vector< double > &  mu)

Set the mixing parameter separately for each node.

This is for each node the fraction of neighbors that do not belong to the node's own community.

Parameters
muThe mixing parameter for each node.
void NetworKit::LFRGenerator::setMuWithBinomialDistribution ( double  mu)

Set the internal degree of each node using a binomial distribution such that the expected mixing parameter is the given mu.

The mixing parameter is for each node the fraction of neighbors that do not belong to the node's own community.

Parameters
muThe expected mu that shall be used.
void NetworKit::LFRGenerator::setPartition ( NetworKit::Partition  zeta)

Set the partition, this replaces the community size sequence and the random assignment of the nodes to communities.

Parameters
zetaThe partition to use
std::string NetworKit::LFRGenerator::toString ( ) const
overridevirtual

The name and parameters of the generator.

Reimplemented from NetworKit::Algorithm.

Member Data Documentation

std::vector<count> NetworKit::LFRGenerator::communitySizeSequence
protected
std::vector<count> NetworKit::LFRGenerator::degreeSequence
protected
Graph NetworKit::LFRGenerator::G
protected
bool NetworKit::LFRGenerator::hasCommunitySizeSequence
protected
bool NetworKit::LFRGenerator::hasDegreeSequence
protected
bool NetworKit::LFRGenerator::hasGraph
protected
bool NetworKit::LFRGenerator::hasInternalDegreeSequence
protected
bool NetworKit::LFRGenerator::hasPartition
protected
std::vector<count> NetworKit::LFRGenerator::internalDegreeSequence
protected
count NetworKit::LFRGenerator::n
protected
Partition NetworKit::LFRGenerator::zeta
protected

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