Class DynKatzCentrality¶

Inheritance Relationships¶

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.

Parameters:

• 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.

Parameters:

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¶