Class EffectiveDiameterApproximation

Inheritance Relationships

Base Type

Class Documentation

class EffectiveDiameterApproximation : public NetworKit::Algorithm

Public Functions

EffectiveDiameterApproximation(const Graph &G, double ratio = 0.9, count k = 64, count r = 7)

Approximates the effective diameter of a given graph. The effective diameter is defined as the number of edges on average to reach ratio

of all other nodes. Implementation after the ANF algorithm presented in the paper “A Fast and

Scalable Tool for Data Mining in Massive Graphs”[1]

[1] by Palmer, Gibbons and Faloutsos which can be found here: http://www.cs.cmu.edu/~christos/PUBLICATIONS/kdd02-anf.pdf

Parameters:
  • G – the given graph

  • ratio – the ratio of nodes that should be connected (0,1]; default = 0.9

  • k – the number of parallel approximations to get a more robust result; default = 64

  • r – the amount of bits that are added to the length of the bitmask to improve the accuracy; default = 7

virtual void run() override

The generic run method which calls runImpl() and takes care of setting hasRun to the appropriate value.

double getEffectiveDiameter() const

Returns the exact effective diameter of the graph.

Returns:

the exact effective diameter of the graph