Class LFRGenerator¶

Inheritance Relationships¶

Class Documentation¶

class LFRGenerator : public NetworKit::Algorithm, public NetworKit::StaticGraphGenerator¶

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.

Public Functions

LFRGenerator(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:

n – The number of nodes.

void setDegreeSequence(std::vector<count> degreeSequence)¶

Set the given degree sequence.

Parameters:

degreeSequence – The degree sequence that shall be used by the generator

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.

Parameters:

• avgDegree – The average degree that shall be reached.

• maxDegree – The maximum degree that shall be generated.

• nodeDegreeExp – The (negative) exponent of the powerlaw degree sequence.

void setCommunitySizeSequence(std::vector<count> communitySizeSequence)¶

Set the given community size sequence.

Parameters:

communitySizeSequence – The community sizes that shall be used.

void setPartition(Partition zeta)¶

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

Parameters:

zeta – The partition to use

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.

Parameters:

• minCommunitySize – The minimum community size to generate

• maxCommunitySize – The maximum community size to generate

• communitySizeExp – The (negative) exponent of the power law community size sequence

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.

Parameters:

mu – The mixing parameter that shall be set.

void 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:

mu – The mixing parameter for each node.

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.

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

Parameters:

mu – The expected mu that shall be used.

virtual void run() override¶

Generates the graph and the community structure. The algorithm is not parallel.

virtual Graph generate() override¶

Generates and returns the graph.

Returns:

The generated graph.

Graph getGraph() const¶

Returns (a copy of) the generated graph.

Returns:

The generated graph.

Graph &&getMoveGraph()¶

Returns the generated graph using move semantics.

Returns:

The generated graph.

Partition getPartition() const¶

Returns (a copy of) the generated partition

Returns:

The generated graph.

Partition &&getMovePartition()¶

Returns the generated partition using move semantics.

Returns:

The generated partition.