Class DynKatzCentrality

Inheritance Relationships

Base Types

Class Documentation

class DynKatzCentrality : public NetworKit::Centrality, public NetworKit::DynAlgorithm

Finds the top-k nodes with highest Katz centrality

Public Functions

DynKatzCentrality(const Graph &G, count k, bool groupOnly = false, double tolerance = 1e-9)

Constructs a DynKatzCentrality object for the given Graph G. The damping factor is set to 1/(maxdeg + 1), where maxdeg is the maxmum degree in the graph.

  • G[in] The graph.

  • k[in] The number k for which we want to find the top-k nodes with highest Katz centrality

  • groupOnly[in] Set whether the update will only update top-k nodes.

  • tolerance[in] The tolerance for convergence.

virtual void run() override

Computes centrality scores on the graph passed in constructor.

virtual void updateBatch(const std::vector<GraphEvent> &events) override

Updates the katz centralities after an edge insertion or deletion on the graph.


event – The edge insertions or deletion.

inline virtual void update(GraphEvent singleEvent) override

The generic update method for updating data structure after an update.

inline node top(count n = 0)
double bound(node v)

Returns the (upper) bound of the centrality of each node

bool areDistinguished(node u, node v)

Returns true if the bounds are sharp enough to rank two nodes against each other.

Public Members

bool useQueue = false
std::vector<std::vector<count>> nPaths
count levelReached = 0

Protected Attributes

double alpha
count k
count maxdeg
bool groupOnly
double rankTolerance