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

SpanningEdgeCentrality edge centrality. More...

#include <SpanningEdgeCentrality.h>

Public Member Functions

 SpanningEdgeCentrality (const Graph &G, double tol=0.1)
 Constructs the SpanningEdgeCentrality class for the given Graph G. More...
 
virtual ~SpanningEdgeCentrality ()=default
 Destructor. More...
 
void run () override
 Compute spanning edge centrality scores exactly for all edges. More...
 
void runApproximation ()
 Compute approximation by JL projection. More...
 
void runParallelApproximation ()
 Compute approximation by JL projection in parallel. More...
 
uint64_t runApproximationAndWriteVectors (const std::string &graphPath)
 Only used by benchmarking. More...
 
uint64_t getSetupTime () const
 
double runForEdge (node u, node v)
 Compute value for one edge only. 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
 

Protected Attributes

double tol
 
Lamg< CSRMatrixlamg
 
uint64_t setupTime
 
- 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

SpanningEdgeCentrality edge centrality.

Constructor & Destructor Documentation

NetworKit::SpanningEdgeCentrality::SpanningEdgeCentrality ( const Graph G,
double  tol = 0.1 
)

Constructs the SpanningEdgeCentrality class for the given Graph G.

Parameters
GThe graph.
tolconstant used for the approximation: with probability at least 1-1/n, the approximated scores are within a factor 1+tol from the exact scores
virtual NetworKit::SpanningEdgeCentrality::~SpanningEdgeCentrality ( )
virtualdefault

Destructor.

Member Function Documentation

uint64_t NetworKit::SpanningEdgeCentrality::getSetupTime ( ) const
Returns
The elapsed time to setup the solver in milliseconds.
void NetworKit::SpanningEdgeCentrality::run ( )
overridevirtual

Compute spanning edge centrality scores exactly for all edges.

This solves a linear system for each edge, so the empirical running time is O(m^2), where m is the number of edges in the graph.

Implements NetworKit::Centrality.

void NetworKit::SpanningEdgeCentrality::runApproximation ( )

Compute approximation by JL projection.

This solves k linear systems, where k is log(n)/(tol^2). The empirical running time is O(km), where n is the number of nodes and m is the number of edges.

uint64_t NetworKit::SpanningEdgeCentrality::runApproximationAndWriteVectors ( const std::string &  graphPath)

Only used by benchmarking.

Computes an approximation by projection and solving Laplacian systems. Measures the time needed to compute the approximation and writes the problem vectors to the directory of the graph specified by graphPath.

Parameters
directory
Returns
Elapsed time in milliseconds.
double NetworKit::SpanningEdgeCentrality::runForEdge ( node  u,
node  v 
)

Compute value for one edge only.

This requires a single linear system, so the empricial running time is O(m).

Parameters
[in]uEndpoint of edge.
[in]vEndpoint of edge.
void NetworKit::SpanningEdgeCentrality::runParallelApproximation ( )

Compute approximation by JL projection in parallel.

This solves k linear systems in parallel, where k is log(n)/(tol^2).

Member Data Documentation

Lamg<CSRMatrix> NetworKit::SpanningEdgeCentrality::lamg
protected
uint64_t NetworKit::SpanningEdgeCentrality::setupTime
protected
double NetworKit::SpanningEdgeCentrality::tol
protected

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