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

Computes the Katz centrality of the graph. More...

#include <KatzCentrality.h>

Public Member Functions

 KatzCentrality (const Graph &G, double alpha=5e-4, double beta=0.1, double tol=1e-8)
 Constructs a KatzCentrality object for the given Graph G. More...
 
virtual void run ()
 Computes katz centrality on the graph passed in constructor. 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 alpha
 
double beta
 
double tol
 
- 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

Computes the Katz centrality of the graph.

NOTE: There is an inconsistency in the definition in Newman's book (Ch. 7) regarding directed graphs; we follow the verbal description, which requires to sum over the incoming edges (as opposed to outgoing ones).

Constructor & Destructor Documentation

NetworKit::KatzCentrality::KatzCentrality ( const Graph G,
double  alpha = 5e-4,
double  beta = 0.1,
double  tol = 1e-8 
)

Constructs a KatzCentrality object for the given Graph G.

tol defines the tolerance for convergence. Each iteration of the algorithm requires O(m) time. The number of iterations depends on how long it takes to reach the convergence.

Parameters
[in]GThe graph.
[in]alphaDamping of the matrix vector product result
[in]betaConstant value added to the centrality of each vertex
[in]tolThe tolerance for convergence.

Member Function Documentation

void NetworKit::KatzCentrality::run ( )
virtual

Computes katz centrality on the graph passed in constructor.

Implements NetworKit::Centrality.

Member Data Documentation

double NetworKit::KatzCentrality::alpha
protected
double NetworKit::KatzCentrality::beta
protected
double NetworKit::KatzCentrality::tol
protected

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