Class HopPlotApproximation¶

Inheritance Relationships¶

Class Documentation¶

class HopPlotApproximation : public NetworKit::Algorithm¶

Public Functions

HopPlotApproximation(const Graph &G, count maxDistance = 0, count k = 64, count r = 7)¶

Computes an approximation of the hop-plot of a given graph The hop-plot is the set of pairs (d, g(g)) for each natural number d and where g(d) is the fraction of connected node pairs whose shortest connecting path has length at most d. 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

• maxDistance – the maximum path length that shall be considered. set 0 for infinity/diameter of the graph

• 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

Returns:

the approximated hop-plot of the graph

virtual void run() override¶

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

const std::map<count, double> &getHopPlot() const¶

Returns the approximated hop-plot of the graph.

Returns:

the approximated hop-plot of the graph