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

Approximation of closeness centrality according to algorithm described in Cohen et al., Computing Classic Closeness Centrality, at Scale. More...

#include <ApproxCloseness.h>

Public Types

enum  CLOSENESS_TYPE { INBOUND, OUTBOUND, SUM }
 

Public Member Functions

 ApproxCloseness (const Graph &G, count nSamples, double epsilon=0.1, bool normalized=false, CLOSENESS_TYPE type=OUTBOUND)
 Constructs an instance of the ApproxCloseness class for graph using nSamples during the run() method. More...
 
void run () override
 Computes closeness approximation on the graph passed in constructor. More...
 
double maximum () override
 Returns the maximum possible Closeness a node can have in a graph with the same amount of nodes (=a star) More...
 
std::vector< double > getSquareErrorEstimates ()
 
- Public Member Functions inherited from NetworKit::Centrality
 Centrality (const Graph &G, bool normalized=false, bool computeEdgeCentrality=false)
 Constructs the Centrality class for the given Graph G. More...
 
virtual ~Centrality ()=default
 Default destructor. More...
 
virtual std::vector< double > scores (bool moveOut=false)
 Get a vector containing the centrality score for each node in the graph. More...
 
virtual std::vector< double > edgeScores ()
 Get a vector containing the edge centrality score for each edge in the graph (where applicable). More...
 
virtual std::vector< std::pair
< node, double > > 
ranking ()
 Get a vector of pairs sorted into descending order. More...
 
virtual double score (node v)
 Get the centrality score of node v calculated by run(). More...
 
virtual double centralization ()
 Compute the centralization of a network with respect to some centrality measure. 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::Centrality
const GraphG
 
std::vector< double > scoreData
 
std::vector< double > edgeScoreData
 
bool normalized
 
bool computeEdgeCentrality
 
- Protected Attributes inherited from NetworKit::Algorithm
bool hasRun
 A boolean variable indicating whether an algorithm has finished its computation or not. More...
 

Detailed Description

Approximation of closeness centrality according to algorithm described in Cohen et al., Computing Classic Closeness Centrality, at Scale.

Member Enumeration Documentation

Enumerator
INBOUND 
OUTBOUND 
SUM 

Constructor & Destructor Documentation

NetworKit::ApproxCloseness::ApproxCloseness ( const Graph G,
count  nSamples,
double  epsilon = 0.1,
bool  normalized = false,
CLOSENESS_TYPE  type = OUTBOUND 
)

Constructs an instance of the ApproxCloseness class for graph using nSamples during the run() method.

The epsilon parameter (standard = 0.1) is used to control the switch between sampling and pivoting. Using epsilon = 0, the algorithm only uses sampling. (see Cohen, Edith, et al. "Computing classic closeness centrality, at scale." Proceedings of the second ACM conference on Online social networks. ACM, 2014.). The running time is proportional to nSamples * m, where m is the number of edges. Notice: the input graph has to be connected.

Parameters
graphinput graph
nSamplesuser defined number of samples
epsilonValue in [0, infty) controlling the switch between sampling and pivoting. When using 0, only sampling is used. Standard is 0.1.
normalizednormalize centrality values in interval [0,1]
typeuse in- or outbound centrality or the sum of both (see paper) for computing closeness on directed graph. If G is undirected, this can be ignored.

Member Function Documentation

std::vector< double > NetworKit::ApproxCloseness::getSquareErrorEstimates ( )
Returns
The square error when closeness centrality has been computed for an undirected graph.
double NetworKit::ApproxCloseness::maximum ( )
overridevirtual

Returns the maximum possible Closeness a node can have in a graph with the same amount of nodes (=a star)

Reimplemented from NetworKit::Centrality.

void NetworKit::ApproxCloseness::run ( )
overridevirtual

Computes closeness approximation on the graph passed in constructor.

Implements NetworKit::Centrality.


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