Defined in File DynTopHarmonicCloseness.hpp
public NetworKit::Algorithm
(Class Algorithm)
public NetworKit::DynAlgorithm
(Class DynAlgorithm)
Manages the list of the k nodes with the highest closeness centrality in a dynamic graph.
Public Functions
Constructs the DynTopHarmonicCloseness class. This class implements dynamic algorithms for harmonic top-k closeness centrality. The implementation is based on the static algorithms by Borassi et al. (complex networks) and Bergamini et al. (large-diameter networks).
G – The graph.
k – The number of top nodes.
useBFSbound – Whether to use the algorithm for networks with large diameter
Computes the k most central nodes on the initial graph.
Returns a list with the k most central nodes. WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those nodes but consider that the resulting vector could be longer than k.
includeTrail – Whether or not to include trail nodes.
The list of the top-k nodes.
Returns a list with the k highest closeness centralities. WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those centrality values but consider that the resulting vector could be longer than k.
includeTrail – Whether or not to include trail centrality value.
The closeness centralities of the k most central nodes.
Returns the ranking of the k most central nodes in the graph. WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those nodes but consider that the resulting vector could be longer than k.
includeTrail – Whether or not to include trail nodes.
The ranking.
Updates the list of the k nodes with the highest closeness in G.
event – The edge modification event.
Updates the list of k nodes with the highest closeness in G after a batch of updates.
batch – A vector of edge modification events.
Protected Functions
Runs a pruned BFS from the node u. The search is aborted once the closeness centrality of u must be smaller than x.
v – The start node.
x – The closeness centrality of the k-th most central node.
n – The number of nodes in the graph.
r – The number of reachable nodes (or an upper bound in directed graphs) for each node.
visited – The vector containing the visited status.
distances – The vector containing the distances.
pred – The vector containing the predecessor of each node.
visitedEdges – The number of visited edges.
Computes the exact closeness centrality of the node x and stores upper bounds for all other nodes in S2.
x – The start node.
S2 – The upper bounds for all other nodes.
visEdges – The number of visited edges.
Handles an edge insertion.
event – The graph event.
Handles an edge removal.
event – The graph event.
Computes the number of reachable nodes or an upper bound in directed graphs.
Computes an upper bound for the number of reachable nodes for each node in a directed graph.
Computes the number of reachable nodes in an undirected graph.
Recomputes the number of reachable nodes in an undirected graph after inserting an edge between u and v.
u – The first node.
v – The second node.
Recomputes the number of reachable nodes in an undirected graph after removing an edge between u and v.
u – The first node.
v – The second node.
Protected Attributes