Class NeighborhoodFunctionApproximation¶

Inheritance Relationships¶

Class Documentation¶

class NeighborhoodFunctionApproximation : public NetworKit::Algorithm¶

Public Functions

NeighborhoodFunctionApproximation(const Graph &G, count k = 64, count r = 7)¶

Computes an approximation of the neighborhood function. The neighborhood function N of a graph G for a given distance t is defined as the number of node pairs (u,v) that can be reached within distance t. 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

• 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.

const std::vector<count> &getNeighborhoodFunction() const¶

Returns the approximated neighborhood function of the graph.

Returns:

the approximated neighborhood function of the graph