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

Interface for dynamic approximated betweenness centrality algorithm. More...

#include <DynApproxBetweenness.h>

Public Member Functions

 DynApproxBetweenness (const Graph &G, const double epsilon=0.01, const double delta=0.1, const bool storePredecessors=true, const double universalConstant=1.0)
 The algorithm approximates the betweenness of all vertices so that the scores are within an additive error epsilon with probability at least (1- delta). More...
 
void run () override
 Runs the static approximated betweenness centrality algorithm on the initial graph. More...
 
void update (GraphEvent e) override
 Updates the betweenness centralities after an edge insertions on the graph. More...
 
void updateBatch (const std::vector< GraphEvent > &batch) override
 Updates the betweenness centralities after a batch of edge insertions on the graph. More...
 
count getNumberOfSamples ()
 Get number of path samples used for last calculation. More...
 
- 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 maximum ()
 Get the theoretical maximum of centrality score in the given graph. 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
 
- Public Member Functions inherited from NetworKit::DynAlgorithm
virtual ~DynAlgorithm ()=default
 Virtual default destructor. More...
 

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

Interface for dynamic approximated betweenness centrality algorithm.

Constructor & Destructor Documentation

NetworKit::DynApproxBetweenness::DynApproxBetweenness ( const Graph G,
const double  epsilon = 0.01,
const double  delta = 0.1,
const bool  storePredecessors = true,
const double  universalConstant = 1.0 
)

The algorithm approximates the betweenness of all vertices so that the scores are within an additive error epsilon with probability at least (1- delta).

The values are normalized by default.

Parameters
Gthe graph
storePredecessorskeep track of the lists of predecessors?
epsilonmaximum additive error
deltaprobability that the values are within the error guarantee
universalConstantthe universal constant to be used in computing the sample size. It is 1 by default. Some references suggest using 0.5, but there is no guarantee in this case.

Member Function Documentation

count NetworKit::DynApproxBetweenness::getNumberOfSamples ( )

Get number of path samples used for last calculation.

void NetworKit::DynApproxBetweenness::run ( )
overridevirtual

Runs the static approximated betweenness centrality algorithm on the initial graph.

Implements NetworKit::Centrality.

void NetworKit::DynApproxBetweenness::update ( GraphEvent  e)
overridevirtual

Updates the betweenness centralities after an edge insertions on the graph.

Notice: it works only with edge insertions and the graph has to be connected.

Parameters
eThe edge insertions.

Implements NetworKit::DynAlgorithm.

void NetworKit::DynApproxBetweenness::updateBatch ( const std::vector< GraphEvent > &  batch)
overridevirtual

Updates the betweenness centralities after a batch of edge insertions on the graph.

Notice: it works only with edge insertions and the graph has to be connected.

Parameters
batchThe batch of edge insertions.

Implements NetworKit::DynAlgorithm.


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