Approximation of betweenness centrality according to algorithm described in Matteo Riondato and Evgenios M. More...
#include <ApproxBetweenness.h>
Public Member Functions  
ApproxBetweenness (const Graph &G, const double epsilon=0.01, const double delta=0.1, 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 
Computes betweenness approximation on the graph passed in constructor. More...  
count  numberOfSamples () 
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 
Additional Inherited Members  
Protected Attributes inherited from NetworKit::Centrality  
const Graph &  G 
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...  
Approximation of betweenness centrality according to algorithm described in Matteo Riondato and Evgenios M.
Kornaropoulos: Fast Approximation of Betweenness Centrality through Sampling
NetworKit::ApproxBetweenness::ApproxBetweenness  (  const Graph &  G, 
const double  epsilon = 0.01 , 

const double  delta = 0.1 , 

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. The run() method takes O(m) time per sample, where m is the number of edges of the graph. The number of samples is proportional to universalConstant/epsilon^2. Although this algorithm has a theoretical guarantee, the algorithm implemented in Estimate Betweenness usually performs better in practice Therefore, we recommend to use EstimateBetweenness if no theoretical guarantee is needed.
G  the graph 
epsilon  maximum additive error 
delta  probability that the values are within the error guarantee 
universalConstant  the 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. 
count NetworKit::ApproxBetweenness::numberOfSamples  (  ) 

overridevirtual 
Computes betweenness approximation on the graph passed in constructor.
Implements NetworKit::Centrality.