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

#include <HopPlotApproximation.h>

Public Member Functions

 HopPlotApproximation (const Graph &G, const count maxDistance=0, const count k=64, const count r=7)
 Computes an approxmation 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. More...
 
void run () override
 The generic run method which calls runImpl() and takes care of setting to the appropriate value. More...
 
std::map< count, double > getHopPlot () const
 Returns the approximated hop-plot of the graph. 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...
 
virtual std::string toString () const
 Returns a string with the algorithm's name and its parameters, if there are any. More...
 
virtual bool isParallel () const
 

Additional Inherited Members

- Protected Attributes inherited from NetworKit::Algorithm
bool hasRun
 A boolean variable indicating whether an algorithm has finished its computation or not. More...
 

Constructor & Destructor Documentation

NetworKit::HopPlotApproximation::HopPlotApproximation ( const Graph G,
const count  maxDistance = 0,
const count  k = 64,
const count  r = 7 
)

Computes an approxmation 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
Gthe given graph
maxDistancethe maximum path length that shall be considered. set 0 for infinity/diameter of the graph
kthe number of parallel approximations to get a more robust result; default = 64
rthe 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

Member Function Documentation

std::map< count, double > NetworKit::HopPlotApproximation::getHopPlot ( ) const

Returns the approximated hop-plot of the graph.

Returns
the approximated hop-plot of the graph
void NetworKit::HopPlotApproximation::run ( )
overridevirtual

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

Implements NetworKit::Algorithm.


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